[백준] 2151 거울설치 풀이

알고리즘

BFS

풀이 과정

1. 조합 개수로 반복 DFS를 돌리면서 해볼까 생각했는데, 이는 N ≤ 10 정도 일때만 통과한다. 지금은 1≤ N ≤ 50 이므로 시간 초과 또는 메모리 초과가 난다.
2. 다른 풀이 방법을 생각했어야 했는데, 한쪽 문을 start 지점으로 정하고, 다른 문을 만날때까지 BFS를 진행한다. PriorityQueue는 거울의 최소 개수로 정렬되게 한다.
   1. ! 를 만나면, 방향을 바꿀 수 있다. 즉 90도 방향을 바꾸고 PriorityQueue에다가 넣어준다.
   2. ‘*’ 를 만나면 벽이므로 이동할 수 없다.
   3. 그 외 다른 것들은 방향을 직진해서 갈 수 있다.

이를 코드에 옮겼고, 다음과 같이 같다.

트러블 슈팅

원래는 코드를 다음과 같이 짰었다. 이 조건을 통해 90도 체크가 되는 지 확인했었다.

  if ((i + poll[2]) % 2 == 0) {
			continue;
  }

잘못된 풀이

  private static int BFS(int n, int startX, int startY, int endX, int endY) {
        boolean[][][] visit = new boolean[n][n][4];
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> (a[3] - b[3]));

        for (int i = 0; i < 4; i++) {
            q.add(new int[]{startX, startY, i, 0});
            visit[startX][startY][i] = true;
        }

        while (!q.isEmpty()) {
            int[] poll = q.poll();

            if (poll[0] == endX && poll[1] == endY) {
                return poll[3];
            }

            int nextX = poll[0] + dx[poll[2]];
            int nextY = poll[1] + dy[poll[2]];
            if (nextX < 0 || nextX >= map.length || nextY < 0 || nextY >= map.length) {
                continue;
            }

            if (map[nextX][nextY] == '*') {
                continue;
            }

            if (visit[nextX][nextY][poll[2]]) {
                continue;
            }

            visit[nextX][nextY][poll[2]] = true;
            q.add(new int[]{nextX, nextY, poll[2], poll[3]});

            if (map[nextX][nextY] == '!') {
                for (int i = 0; i < 4; i++) {	
                    if ((i + poll[2]) % 2 == 0) {
                        continue;
                    }
                    if (visit[nextX][nextY][i]) {
                        continue;
                    }
                    visit[nextX][nextY][i] = true;
                    q.add(new int[]{nextX, nextY, i, poll[3] + 1});
                }
            }

        }
        return Integer.MAX_VALUE;
    }

그런데 한 82 퍼센트 쯤 틀렸습니다가 떴다.

그런데 조건을 바꾸는 곳을 이렇게 바꾸면 올바른 코드가 되었다. 그래서 아무리 생각해도 의문점이 가시질 않아, 싸피 알고도사님께 여쭈어 보았다.

if (map[nextX][nextY] == '!') {
         for (int i = 0; i < 4; i++) {
                    if (i % 2 == 0) {
                        continue;
                    }
                    int dir = (poll[2] + i) % 4;

                    if (visit[nextX][nextY][dir]) {
                        continue;
                    }
                    visit[nextX][nextY][dir] = true;
                    q.add(new int[]{nextX, nextY, dir, poll[3] + 1});
                }
}

도사님이 보시자마자, 맞는 코드도 방향을 반대로 돌리면 틀렸습니다가 뜬다고 알려주시고, 방향을 체크하는 부분에서 문제가 있음을 알려주셨다. 따라서 방문체크를 boolean이 아닌, int 로 하여 더 작을 때 갱신하게끔 바꾸니 맞는 코드가 되었다.

private static int BFS(int n, int startX, int startY, int endX, int endY) {
        boolean[][][] visit = new boolean[n][n][4];
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> (a[3] - b[3]));

        for (int i = 0; i < 4; i++) {
            q.add(new int[]{startX, startY, i, 0});
            visit[startX][startY][i] = true;
        }

        while (!q.isEmpty()) {
            int[] poll = q.poll();

            if (poll[0] == endX && poll[1] == endY) {
                return poll[3];
            }

            int nextX = poll[0] + dx[poll[2]];
            int nextY = poll[1] + dy[poll[2]];
            if (nextX < 0 || nextX >= map.length || nextY < 0 || nextY >= map.length) {
                continue;
            }

            if (map[nextX][nextY] == '*') {
                continue;
            }

            if (visit[nextX][nextY][poll[2]]) {
                continue;
            }
            visit[nextX][nextY][poll[2]] = true;
            q.add(new int[]{nextX, nextY, poll[2], poll[3]});

            if (map[nextX][nextY] == '!') {
                for (int i = 0; i < 4; i++) {
                    if (i % 2 == 0) {
                        continue;
                    }
                    int dir = (poll[2] + i) % 4;

                    if (visit[nextX][nextY][dir]) {
                        continue;
                    }
                    visit[nextX][nextY][dir] = true;
                    q.add(new int[]{nextX, nextY, dir, poll[3] + 1});
                }
            }

        }
        return Integer.MAX_VALUE;
    }

즉 다음과 같이, !를 만날 때, 꺾는 방향을 PQ를 넣고 방문 처리를 해버리면,

해당 부분에 대해서 직진하는 코드가 있을 때, 이미 방문 처리를 했기 때문에 직진하지 못하는 것이다.

따라서 다음과 같은 코드를 위해 !를 만날때는 따로 방문처리를 하지 않고, pq에다가 넣어주는 방식으로 바꾸었다.

 

if (map[nextX][nextY] == '!') {
         for (int i = 0; i < 4; i++) {
                    if (i== poll[2]) continue;
                    if ((i + poll[2]) % 2 == 0) {
                        continue;
                    }
                    if (visit[nextX][nextY][i]) {
                        continue;
                    }
                    q.add(new int[]{nextX, nextY, i, poll[3] + 1});
                }
}

느낀 점

• BFS 시, 억까를 당하면, 방문체크를 잘 하고 있는 지 확인하자! 무조건 방문하고 체크하는게 맞는게 아니다
• (결론은 우리반 알고도사 곽민규 짱..)