[자바] 백준 18224 - 미로에 갇힌 건우 (java)

목차

문제 : boj18224

 

 

필요 알고리즘

• 너비 우선 탐색 (BFS)
  
  • 좀 어려운 BFS 문제이다. 근본은 동일하다. 방문체크와 탐색만 잘 하면 된다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  BFS에 대해 모른다면 '이 글'을 참고해보자. 특히 '방문체크에 대해 좀 더 써봄' 부분을 이해해야 풀 수 있다.

결국 이 문제도 방문체크를 모든 경우를 표현할 수 있으면서도 최소한으로 할 수 있고, 문제에서 주어진 대로 탐색을 구현할 수만 있으면 풀 수 있다.

 

중요한건 방문체크

  탐색 시 시간초과를 막기 위해 방문체크는 대부분의 경우 필수이다. 우선 방문체크를 어떻게 해야할지 생각해보자. 이하의 예시를 생각해보자.

3 2
0 0 1
1 1 1
0 1 0

 

 

  이동과 낮, 밤을 적어보면 다음과 같다. 답은 "2 sun"이 된다.

 

  여기서 알 수 있는 점은

1. 왔던 곳으로 되돌아올 수 있어야 한다 (첫번째와 세번째는 동일한 위치이다)

2. 이동이 끝난 후 밤과 낮이 바뀐다고 보면 편하다. (네번째에서 밤이므로 벽을 넘어 다섯번째로 이동 가능했다. 그리고 낮이 됬다.)

 

  여기서 특히 '1'에 따라 단순히 NxN 방문체크로는 체크가 불가함을 알 수 있다.

그럼 밤과 낮으로 나누어 2개의 NxN 방문체크로 가능할까? BFS에서 방문체크는 '모든 경우' 중 '동일한 경우'에 더 나중에 도달하는걸 막는다. 밤과 낮만 체크하는건 '모든 경우'를 체크하기엔 부족해보인다. 이 문제에서 중요한건 '언제' 낮과 밤이 바뀌는지이다. 이건 결국 m번 내에서 현재 몇 걸음 걸었냐에 따라서도 달라진다. (만약 현재 낮이나 밤이 된 이후 2걸음 걸었다면, m-2 번 더 걸으면 다시 낮과 밤이 바뀐다)

 

  따라서 내 경우엔 v[dn][n][n][m] 처럼 4차원 방문체크를 했다. dn은 낮(0), 밤(1)을 나타낸다. 그 뒤 2차원과 3차원은 NxN 크기의 맵을 나타내고, 4차원의 m은 현재 m걸음 이내에서 몇 걸음 걸었냐를 나타낸다(낮과 밤이 바뀌면 초기화). 말로 설명해보면 "m이 동일하고, 낮과 밤이 동일할 때 맵의 특정 위치에 대해 다시 도달하는건 '동일한 경우'로 친다." 라고 보면 된다.

 

 

방문체크를 정했다면 문제에 나온대로 구현하면 된다.

  이건 코드를 보며 설명하는게 더 이해하기 편할 것 같다. 우선 코드만 봐서는 이해하기 힘들만한 코드부터 설명하겠다.

 

1. 이하의 코드는 현재 낮(0)인지 밤(1)인지 확인하는 코드이다. cur.dist는 현재까지 위치를 이동한 횟수이다. 이걸 m으로 나눈 몫은 현재까지 이동하면서 낮, 밤이 총 몇 번 바뀌었는지를 나타낸다. 그리고 그걸 %2 해주면 결국 낮인지 밤인지를 나타내게 된다.

int curDayOrNight = (cur.dist/m)%2;

 

2. 이하의 코드도 dayOrNight는 '1'과 동일하다. cnt는 현재까지 위치를 이동한 횟수를 m으로 나눈 나머지로, 낮과 밤이 바뀔 때 마다 m이 0으로 초기화된다고 할 때, 현재 m을 나타낸다.

int cnt = next.dist%m;
int dayOrNight = (next.dist/m)%2;

 

3. 목적지를 찾았을 때 출력해주는 부분 중 일부이다. '몇번째 날'인지 구하기 위한 식이다. 시작부터 1일이어야 하므로 +1이 들어갔고, 낮과 밤이 세트로 하루를 나타내므로 2m 으로 나눈 몫은 몇번째 날인지를 뜻하게 된다. 

cur.dist/(2*m)+1

 

4. 나머지 구현 로직은 주석에 쓰겠다.

Pos cur = q.poll();
int curDayOrNight = (cur.dist/m)%2;	// 이동하기 전이 낮인지 밤인지 나타낸다.

if (cur.r == n-1 && cur.c == n-1) {	// 목적지에 도달했다면 출력해준다.
    System.out.printf("%d %s\n", cur.dist/(2*m)+1, curDayOrNight==0 ? "sun" : "moon");
    return;
}

for (int d = 0; d < 4; d++) {	// 상하좌우 방향
    Pos next = new Pos(cur.r+DR[d], cur.c+DC[d], cur.dist+1);
    int cnt = next.dist%m;	// 다음 이동할곳의 m값에 해당한다.
    int dayOrNight = (next.dist/m)%2;	// 다음 이동할곳이 밤인지 낮인지

    if (next.r<0 || next.r>=n || next.c<0 || next.c>=n) continue;
    if (curDayOrNight == 0 && map[next.r][next.c]) continue;	
    //이동하기 전이 낮(0)인데 막힌곳이면 무시한다.

    if (curDayOrNight == 1 && map[next.r][next.c]) {	// 이동하기 전이 밤이고 막힌곳이라면
        while (!(next.r < 0 || next.r >= n || next.c < 0 || next.c >= n) && map[next.r][next.c]) {
            next.r += DR[d];
            next.c += DC[d];	//막힌곳을 넘어간다.
        }
        if (next.r<0 || next.r>=n || next.c<0 || next.c>=n) continue;
    }

    if (v[dayOrNight][next.r][next.c][cnt]) continue;	//방문체크
    v[dayOrNight][next.r][next.c][cnt] = true;
    q.add(next);
}

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);
    private static final int[] DR = {-1, 0, 0, 1};
    private static final int[] DC = {0, -1, 1, 0};

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        boolean[][] map = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = st.nextToken().charAt(0) == '1';
            }
        }

        boolean[][][][] v = new boolean[2][n][n][m];
        Queue<Pos> q = new ArrayDeque<>();
        v[0][0][0][0] = true;
        q.add(new Pos(0, 0, 0));
        while (!q.isEmpty()) {
            Pos cur = q.poll();
            int curDayOrNight = (cur.dist/m)%2;

            if (cur.r == n-1 && cur.c == n-1) {
                System.out.printf("%d %s\n", cur.dist/(2*m)+1, curDayOrNight==0 ? "sun" : "moon");
                return;
            }

            for (int d = 0; d < 4; d++) {
                Pos next = new Pos(cur.r+DR[d], cur.c+DC[d], cur.dist+1);
                int cnt = next.dist%m;
                int dayOrNight = (next.dist/m)%2;

                if (next.r<0 || next.r>=n || next.c<0 || next.c>=n) continue;
                if (curDayOrNight == 0 && map[next.r][next.c]) continue;

                if (curDayOrNight == 1 && map[next.r][next.c]) {
                    while (!(next.r < 0 || next.r >= n || next.c < 0 || next.c >= n) && map[next.r][next.c]) {
                        next.r += DR[d];
                        next.c += DC[d];
                    }
                    if (next.r<0 || next.r>=n || next.c<0 || next.c>=n) continue;
                }

                if (v[dayOrNight][next.r][next.c][cnt]) continue;
                v[dayOrNight][next.r][next.c][cnt] = true;
                q.add(next);
            }
        }
        System.out.println(-1);
    }
}

class Pos {
    int r, c, dist;

    public Pos(final int r, final int c, final int dist) {
        this.r = r;
        this.c = c;
        this.dist = dist;
    }
}