백준 - 거울 설치하기 (JAVA)

 

거울의 반사되는 조건과 기존에 자주 풀던 최단 경로가 아닌 도달할 수 있을 때 '거울의 최소 수'를 구하는 문제라서 더욱 어렵게 느껴졌다.

문제를 읽고 구현을 BFS로 할지, DFS로 할지 고민했는데 BFS로 하게될 경우 거울의 개수를 어떻게 관리하고, 그에 따른 visited 배열을 관리하는 것이 어려울 것 같아서 바로 DFS로 노선을 틀었다.

 

최소 거울의 개수를 구하면 되니깐 거울을 1개 이용했을 때 반대편 문제 도달하는지 확인하고, 도달 못하는 경우 거울의 수를 늘려서 다시 2개, 3개,, N개가 될 때까지 DFS를 반복했다. 그러니 당연하게도 시간초과가 났다. 

 

이 문제는 BFS로 풀어야되는 문제였다. 다른 사람의 BFS 풀이를 보면서 내가 잘못 접근한 부분을 찾아봤다.

 

1. 거울의 개수를 어떻게 관리하냐?

나는 DFS와 마찬가지로 거울의 개수를 늘려가면서 거울 1개일 때, 2개일 때.. N개일 때로 최대 N번의 BFS를 돌릴려고 했다. 하지만 이는 우선순위큐를 이용해서 정렬 조건을 거울의 개수가 작을 것은 우선순위로 해서 큐에서 꺼내는 방법으로 해결할 수 있었다. 이를 통해 BFS 1번만 돌려서 답을 얻을 수 있었고 중요한 것은 거울을 만났을 때도 거울을 배치하지 않았을 때의 값을 넣어줘야 했다.

 

2. visited 배열을 어떻게 관리하냐?

3차원의 배열로 visited[r][c][dir]로 관리한다. 여기서 체크해야할 것은 거울의 개수가 아닌 방향이었다. 해당 방향으로 r,c 좌표를 방문한다면 그때의 값이 최소인 것이다. 

 

해당 내용을 이해하고 다시 구현해봤다. 알고 풀어도 구현하는 것이 꽤 시간이 걸렸다. 이유를 찾아보니 나는 현재 노드를 꺼내 방향을 바꿔서 다음 노드를 큐에 넣어줬고, 다른 답안 풀이들은 큐에 넣기전에 이미 방향을 돌려서 넣어줬었다. 둘 다 비슷한 것 같지만 구현해야하는 코드의 양은 거의 2배 차이가 난다... 아직 내 머릿속에서는 미리 방향을 돌린 상태로 넣어준다는 것이 생소하다.

 

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;


class Main {

    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static int N;
    static int mirrorCount = 0;
    static int sr, sc = -1;
    static int er, ec;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());

        char [][] map = initMap();

        int result = bfs(map);
        System.out.println(result);
    }

    public static int bfs(char [][] map){
        int [] dr = {-1, 1, 0,0,};
        int [] dc = {0, 0, 1, -1};
        PriorityQueue<Mirror>  que = new PriorityQueue<>();
        boolean [][][] visited = new boolean[N][N][4];

        // 처음 좌표에 대해서 네 방향 모두 검사
        for(int i=0; i<4; i++){
            int nextR = sr + dr[i];
            int nextC = sc + dc[i];

            if(nextR >=0 && nextR < N && nextC >=0 && nextC < N && map[nextR][nextC] != '*'){

                que.add(new Mirror(nextR, nextC, i, 0));
            }
        }

        while(!que.isEmpty()){
            Mirror cur = que.poll();
            visited[cur.r][cur.c][cur.dir] = true;

            if(cur.r == er && cur.c == ec){
                return cur.cnt;
            }

            // 직선 방향 넣기
            int nextR = cur.r + dr[cur.dir];
            int nextC = cur.c+ dc[cur.dir];

            if(nextR >=0 && nextR < N && nextC >=0 && nextC < N && map[nextR][nextC] != '*' && !visited[nextR][nextC][cur.dir]){
                que.add(new Mirror(nextR, nextC, cur.dir, cur.cnt));
                visited[nextR][nextC][cur.dir] = true;
            }

            // 거울이 있는 경우
            if(map[cur.r][cur.c] == '!'){
                int [] idxs = new int[2];
                if(cur.cnt >= mirrorCount){
                    continue;
                }
                // 방향 확인
                if(cur.dir == 0 || cur.dir == 1){   // 위, 아래에서 온 빛
                    // 왼쪽, 오른쪽으로 빛이 반사
                    idxs[0] = 2; idxs[1] = 3;
                }
                else{   // 왼쪽, 오른쪽에서 온 빛
                    // 위쪽, 오른쪽으로 빛이 반사
                    idxs[0] = 0; idxs[1] = 1;
                }

                for(int i=0; i<2; i++){
                    nextR = cur.r + dr[idxs[i]];
                    nextC = cur.c+ dc[idxs[i]];

                    if(nextR >=0 && nextR < N && nextC >=0 && nextC < N && map[nextR][nextC] != '*' && !visited[nextR][nextC][idxs[i]]){
                        que.add(new Mirror(nextR, nextC, idxs[i], cur.cnt + 1));
                    }
                }

            }
        }
        return mirrorCount;
    }

    public static char [][] initMap() throws IOException {
        char [][] map = new char[N][N];
        for(int i=0; i<N; i++){
            String str = br.readLine();

            for(int j=0; j<N; j++){
                char ch = str.charAt(j);
                map[i][j] = ch;

                if(ch == '#'){
                    if(sc == -1){
                        sr = i; sc = j;
                    }
                    else{
                        er = i; ec = j;
                    }
                }
                else if(ch == '!'){
                    mirrorCount++;
                }
            }
        }
        return map;
    }
}

class Mirror implements Comparable<Mirror> {
    int r;
    int c;
    int dir;
    int cnt;

    public Mirror(int r, int c, int dir, int cnt) {
        this.r = r;
        this.c = c;
        this.dir = dir;
        this.cnt = cnt;
    }

    @Override
    public int compareTo(Mirror o){
        return this.cnt - o.cnt;
    }

}