백준 6087번 - 레이저 통신 (Java)

https://www.acmicpc.net/problem/6087

6087번: 레이저 통신

 

코드 :

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

public class Main {
    static int W;
    static int H;
    static int[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        List<int[]> projector = new ArrayList<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        visited = new int[W][H];
        char[][] board = new char[W][H];

        for (int i = 0; i < W; i++) {
            String input = br.readLine();
            for (int j = 0; j < H; j++) {
                visited[i][j] = Integer.MAX_VALUE;

                char curr = input.charAt(j);
                board[i][j] = curr;

                if (curr == 'C') {
	            // x,y, 방향,거울  -> 방향이 처음에 다르므로 거울 -1 시작
                    projector.add(new int[]{i, j, -1, -1});                 
                }
            }
        }

        bw.write(bfs(projector, board) + "");
        bw.flush();
        bw.close();
    }

    private static int bfs(List<int[]> projector, char[][] board) {
        // 우선순위큐, 거울개수 기준으로 오름차순 정렬
        Queue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[3] - o2[3];
            }
        });


        // 시작부분, 'C' 정보 둘중 하나 넣기
        int[] start = projector.get(0);
        queue.offer(start);

        // 시작부분 'C' -> '.'로 변경,
        board[start[0]][start[1]] = '.';

        // 방문여부(거울 수) 0으로 설정
        visited[start[0]][start[1]] = 0;

        int[][] mapper = {{1, -1, 0, 0}, {0, 0, 1, -1}};

        while (!queue.isEmpty()) {

                int[] curr = queue.poll();
                int x = curr[0];
                int y = curr[1];
                int dir = curr[2];
                int mirror = curr[3];

                if (board[x][y] == 'C') {
                    return mirror;
                }

                for (int i = 0; i < 4; i++) {
                    int nx = x + mapper[0][i];
                    int ny = y + mapper[1][i];
                    int nm = curr[3];

                    // 인덱스 초과 || 다음이 벽인 경우
                    if (nx < 0 || ny < 0 || nx >= W || ny >= H
                            || board[nx][ny] == '*') continue;

                    // 방향이 바뀌었다면 거울 수 추가
                    if (i != dir) {
                        nm++;
                    }
                    
                    // 방문하려는 곳의 거울 수가 크거나 같은 경우만 탐색
                    if (visited[nx][ny] < nm) {
                        continue;
                    }

                    visited[nx][ny] = nm;
                    queue.offer(new int[]{nx, ny, i, nm});
                }
        }
        return 0;
    }
}

 

풀이 :

시간복잡도
BFS :  V + E => N제곱 + a * N 제곱 -> O(N^2) 

 

bfs를 활용한다. queue에 진행방향을 넣고, 이전과 진행방향이 다른 경우 거울의 개수를 추가해준다.

 

쓸데없이 구불구불하게 이동하는 경우를 제한하기 위해 PriorityQueue를 여태 설치한 거울의 개수로 정렬시키고, 거울의 수가 적은 것부터 처리한다.

 

사실 우선순위 큐를 사용하지 않아도 거울수만 잘 체크해주면 별 이상없이 통과가 된다. 어떤 것이 더 효율이 좋은지, 차이가 큰지는 솔직히 잘 모르겠다. 아직 공부가 더 필요하다.

 

반례 1

벽의 모양에 따라 멀리 돌아서 도착하는 길이 거울수가 더 적을수도 있다. 그 점을 유의해야한다. 그래서 우선순위 큐를 활용해 거울 수가 적은것부터 처리했다.

 

반례 2

이때 주의할 점은 현재 거울의 수와 방문하려는 곳의 거울 수가 같을때도 탐색해야한다는 것이다. 89라인에 부등호를 "<="로 바꾸면 오답처리된다. 이게 이해가 안가서 몇일동안 짬내서 다시보곤했다.

 

코드를 잘 보면 꺾이는 지점(거울이 설치된 곳)의 좌표에서 거울 개수가 추가되는게 아니라, 꺾은 후 이동한 위치부터 거울 개수가 추가된다.

아래 두 케이스를 살펴보자. case1경로로 먼저 탐색이 이뤄지고 그 다음 case2의 경로로 탐색이 이뤄진다고 가정하자.

case 1
   0 1 2 3 4 5
 1 . . . . /-C
 0 C ------/ *

case 2
   0 1 2 3 4 5
 1 /---------C
 0 C . . . . *

 

단순하게 왼쪽의 숫자가 행 번호, 위에 숫자가 열 번호라고 생각해보자. 거울 개수를 오름차순 정렬한 우선순위 큐를 사용하고 있음을 기억하고 살펴보자.

 

1) 먼저 case 1의 경로로 탐색하기

visited[0][4]의 값은 0일 것이며, visited[1][4]의 값은 1이다. [1,4]의 시점에서 queue에 [1,5]위치에 대한 정보를 넣을 것이며, 거울의 개수가 2일 것이다.

 

우선순위 큐를 사용하므로, 거울의 개수가 2보다 작은 경우를 모두 탐색하고 정답이 나오지 않았다면 넣었던 해당 정보([1,5], 거울2개)를 poll()해서 정답처리 할 것이다.

 

2) 직후 case 2의 경로로 탐색하기

[1,3]에서 다음 칸인 [1,4]을 탐색할때, [1,3]시점에서 설치된 거울 개수는 1이다. 그리고 방금 전 case1을 탐색했기 때문에 visited[1][4]도 1이다.

 

결론

즉, 거울 수가 같은 경우를 continue 해버리면 case2의 경로가 최소경로임에도 스킵해버린다. 같은 경우를 포함하는 경우 최소경로를 무시할 가능성이 생기는 것이다.

 

아마 다음턴에 큐에서 대기하고 있던 "[1,5], 거울2" 정보를 가진 객체가 poll()되고 2가 정답이 될 것이다.

 

다른 예시

case 1
   0 1 2 3 4 5 6
 1 . . . . /---C
 0 C ------/ * .

case 2
   0 1 2 3 4 5
 1 /-----------C
 0 C . . . . * .

아마 이런식으로 주어졌다면, 우선순위 큐 덕분에 정답이 제대로 나왔을 것이다. case2에서 [1,5]를 탐색하는 시점에 설치한 거울 수는 1이고 visited[1][5]는 2이기 때문이다.

 

우선순위큐를 사용했음에도 방향을 바꾸자마자 도착했기때문에 정답이 거울 2개로 나올 수 있다.

 

 

참고 :

https://toload.tistory.com/entry/JAVA-%EB%B0%B1%EC%A4%80-6087-%EB%A0%88%EC%9D%B4%EC%A0%80-%ED%86%B5%EC%8B%A0 

[JAVA] 백준 6087 : 레이저 통신

우선순위 큐를 사용하는 것을 이분 덕분에 알게 되었다.

 

마무리

나름대로 열심히 찾은 반례라 정리해보았는데, 이걸 정말 의도한 문제인지, 이게 맞는 반례인지는 모르겠다. 틀린게 있으면 백태클 부탁드립니다.