[JAVA] 코드트리 : 2개의 사탕

문제

코드트리

문제가 보이지 않으면 https://www.codetree.ai/frequent-problems 여기서 찾아볼 수 있다.

이번 문제는 따로 코드를 모듈화 하지 않고 일자로 나열해서 작성해서 가독성이 매우 좋지 않지만 코드 트리에서 자바 풀이를 따로 제공하지 않아 도움이 될까 하여 업로드한다.

 

해결방법

옛날에 필통으로 하던 구슬 미로 찾기 게임이 생각나는 문제였다.

카카오 쇼핑하우에서 검색한 구슬 미로 게임

구슬 대신 사탕을 기울여서 EXIT라고 적힌 밖으로 빨간색 사탕만 빼내야하는데 밖으로 빼내기 위한 최소 횟수를 찾는 문제이다.

문제에서 주어진 예시 사진

전형적인 시뮬레이션 문제라고 할 수 있는데 시뮬레이션 문제는 주어진 조건을 하나하나 잘 확인해야 한다.

문제에서 확인할 수 있는 조건은 다음과 같다.

 

조건

1. 빨간색 사탕을 밖으로 빼야 하지만, 파란색 사탕이 밖으로 나와서는 안됨.

2. 빨간색 사탕이 나올 때 파란색 사탕이 동시에 나오는 것도 안됨.

3. 예시 사진 3번 때를 보면 사탕이 겹칠 수 없고 순서대로 쌓이게 된다.

4. 10번 이내 빨간색 사탕을 밖으로 빼내는 것이 불가능하면 -1을 출력

 

구현 순서

코드의 위에서부터 아래로 가면서 설명을 작성하였다.

방문 체크 배열은 빨간색의 위치와 파란색의 위치를 모두 저장한 4차원 배열을 사용하였다. [rr][rc][br][bc]

 

먼저 입력을 받을 때 현재 빨간 사탕과 파란 사탕의 위치를 저장하고 빈칸으로 변경하였다. 추가적으로 탈출 지점도 저장해두었다.

저장한 변수는 우측과 같다. -> (rr = Red Row, rc = Red Col, br = Blue Row, bc = Blue Col)

 

입력이 완료된 후 탐색을 통해 최소 횟수를 찾는다.

큐를 통해서 탐색을 진행하는데 큐에는 빨간 사탕과 파란 사탕 그리고 진행된 횟수를 객체로 만들어 담아서 사용하였다.

 

큐 내부에서는 먼저 목적지에 도착한 값이 있으면 값을 출력하고 프로그램을 종료해주었다.

(BFS는 가장 먼저 목적지에 도착한 값이 최소 횟수이기 때문)

 

조건 4에 따라 10회가 넘어가는 경우는 추가 탐색을 하지 않고 continue로 넘겨주었다.

종료가 아닌 continue를 사용한 것은 10회에 해당하는 경우 중 성공하는 값이 있는지 모두 확인해봐야 하기 때문이다.

 

본격적으로 탐색에 해당하는 코드인데 기울일 때 이동할 위치와 기존 위치를 둘 다 저장해놓고 사용하였다.

저장한 변수 이름은 우측과 같이 작성하였다. -> (nrr = New Red Row, crr = Current Red Row)

 

while을 사용해서 기울인 방향으로 더 이상 진행이 불가능할 때까지 사탕을 움직여주었다.

이때 한 칸씩 빨간 사탕과 파란 사탕을 움직이는데 더 이상 움직일 수 없다면 기존 위치로 다시 옮겨 주었다.

 

조건 2에 따라 두 사탕이 모두 밖으로 빠지게 되면 빠졌다는 표시를 위해 -1로 변경해주고 while문을 탈출해주었다.

조건 3에 따라 두 사탕이 겹쳐졌을 때 그러지 않도록 이전 위치로 바꿔주고 기울이기를 종료해주었다.

 

조건 1에 따라 빨간색 사탕이 빠진 후에도 계속 탐색을 진행하여 파란색 사탕이 빠지는지를 체크해준다.

만약 빠졌다면 실패이기 때문에 -1로 표시해주었다.

조건 1에 따라 파란색 사탕이 빠지면 절대 안 되기 때문에 빠졌다면 -1로 표시하고 바로 기울이기를 종료해주었다.

 

사이클이 진행돼도 이전 위치와 바뀐 위치가 동일하다면 더 이상 이동이 불가한 것이므로 현재 방향으로 기울이기를 종료한다.

 

현재 방향으로 기울였을 때 실패한 경우면 제거

빨간색 사탕만 탈출한 경우이면 방문 체크 후 큐에 추가 후 아래 코드가 실행되지 않게 continue로 넘겨주었다.

 

이미 방문했었던 값이면 넘김

아니라면 큐에 추가하고 방문 체크를 해준다.

 

큐를 통해 탐색을 진행할 동안 목적지에 도착하지 못했다면 -1을 출력하고 프로그램을 종료한다.

 

---

시뮬레이션 문제는 항상 조건을 정확히 파악하지 않고 구현을 시작하면 자주 틀리게 되어서 꼼꼼히 조건을 확인하는 습관을 가져야 할 것 같다.

 

코드의 주석과 구현 순서에 적어둔 설명을 비교하면서 확인하면 되고,

더러운 코드지만 조금이라도 풀이에 도움이 되면 좋겠다.

 

코드

import java.util.*;
import java.io.*;

public class Main {
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    static char[][] map;
    static boolean[][][][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader breader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(breader.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // 빨간 사탕과 파란 사탕의 위치
        int rr = 0;
        int rc = 0;

        int br = 0;
        int bc = 0;

        int exitR = 0;
        int exitC = 0;

        map = new char[n][m];
        visited = new boolean[n][m][n][m];
        for (int i = 0; i < n; i++) {
            String temp = breader.readLine();
            for (int j = 0; j < m; j++) {
                map[i][j] = temp.charAt(j);
                if (map[i][j] == 'R') {
                    rr = i;
                    rc = j;
                    map[i][j] = '.';
                } else if (map[i][j] == 'B') {
                    br = i;
                    bc = j;
                    map[i][j] = '.';
                } else if (map[i][j] == 'O') {
                    exitR = i;
                    exitC = j;
                }
            }
        }

        // 탐색 시작
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(rr, rc, br, bc, 0));
        visited[rr][rc][br][bc] = true;

        while (!q.isEmpty()) {
            Node cur = q.poll();

            // 목적지에 도착하였으면 종료
            if (map[cur.rr][cur.rc] == 'O') {
                System.out.println(cur.cnt);
                return;
            }

            if (cur.cnt == 10) continue;

            // 상하좌우로 기울이기
            for (int d = 0; d < 4; d++) {
                // 이동할 위치
                int nrr = cur.rr;
                int nrc = cur.rc;
                int nbr = cur.br;
                int nbc = cur.bc;

                // 현재 위치
                int crr = cur.rr;
                int crc = cur.rc;
                int cbr = cur.br;
                int cbc = cur.bc;

                while (true) {
                    // 이동할 때마다 현재 위치를 바꿔준다.
                    crr = nrr;
                    crc = nrc;
                    cbr = nbr;
                    cbc = nbc;

                    // 빨간 사탕 이동
                    nrr += dr[d];
                    nrc += dc[d];
                    if (nrr < 0 || nrc < 0 || nrr >= n || nrc >= m || map[nrr][nrc] == '#') { // 이동 불가면 이전 위치로 바꿈
                        nrr = crr;
                        nrc = crc;
                    }

                    // 파란 사탕 이동
                    nbr += dr[d];
                    nbc += dc[d];
                    if (nbr < 0 || nbc < 0 || nbr >= n || nbc >= m || map[nbr][nbc] == '#') { // 이동 불가면 이전 위치로 바꿈
                        nbr = cbr;
                        nbc = cbc;
                    }

                    if (nrr == nbr && nrc == nbc) {
                        // 두 사탕이 모두 빠지면 실패
                        if (map[nrr][nbc] == 'O') {
                            nrr = -1;
                            nrc = -1;
                            nbr = -1;
                            nbc = -1;
                            break;
                        }
                        // 두 사탕의 위치가 같아지면 이전 위치로 바꾸고 이동 종료
                        nrr = crr;
                        nrc = crc;
                        nbr = cbr;
                        nbc = cbc;
                        break;
                    } else {
                        // 빨간색 사탕이 빠진 상태에서 기울이기를 계속 진행해서 파란색도 빠지면 안되기때문에 계속 돌림
                        if (nrr != -1 && map[nrr][nrc] == 'O') {
                            nrr = -1;
                            nrc = -1;
                        }

                        // 파란색 사탕이 빠지면 무조건 안되므로 종료
                        if (map[nbr][nbc] == 'O') {
                            nrr = -1;
                            nrc = -1;
                            nbr = -1;
                            nbc = -1;
                            break;
                        }
                    }

                    // 두 사탕의 위치가 변하지 않으면 더 이상 이동이 불가한 것이므로 종료
                    if (nrr == crr && nrc == crc && nbr == cbr && nbc == cbc) break;
                }
                if (nrr == -1 && nrc == -1 && nbr == -1 && nbc == -1) continue; // 실패한 경우 제거
                if (nrr == -1 && nrc == -1) { // 빨간색 사탕만 탈출한 경우
                    q.offer(new Node(exitR, exitC, nbr, nbc, cur.cnt + 1));
                    visited[exitR][exitC][nbr][nbc] = true;
                    continue;
                }
                
                if (visited[nrr][nrc][nbr][nbc]) continue;

                q.offer(new Node(nrr, nrc, nbr, nbc, cur.cnt + 1));
                visited[nrr][nrc][nbr][nbc] = true;
            }
        }
        System.out.println("-1");
    }

    static class Node {
        int rr;
        int rc;
        int br;
        int bc;
        int cnt;

        Node (int rr, int rc, int br, int bc, int cnt) {
            this.rr = rr;
            this.rc = rc;
            this.br = br;
            this.bc = bc;
            this.cnt = cnt;
        }
    }
}