[JAVA] 백준 2151 거울 설치

오늘의 문제  :https://www.acmicpc.net/problem/2151

 

거울을 좋아하는 채영이를 위해 문 앞에서 다른 문이 보이도록 거울을 설치해줘야 합니다. 부자인가 봐요. 

 

BFS 탐색을 통해 풀었습니다. 

 

1. 입력 받은 문 하나에서 보이는 거울의 좌표를 우선순위 큐에 넣기

 

- 4방향으로 볼 수 있고, 만약 하나의 거울의 좌표를 발견 하더라도 탐색은 계속 진행되어야 합니다. 

 

- 넣어준 거울의 좌표에 대해 visit[][] 값을 1로 넣어줬습니다. 

이를 통해서 '거울 순환 상황' 체크 및 효율적인 탐색을 수행하였습니다. 

 

거울 순환 상황은 예로

5
***** 
*!.!#
*!.!*
*.!.*
*#***

 

위 와 같은 경우 (1,1),(1,3),(2,3),(2,1)로 다시 시작 문으로 돌아오는 경우는 올바르지 못한 경우입니다. 

 

- 넣어주는 탐색은 좌표, 방향, 현재 거울 수 입니다. 

 

2. 큐에서 하나씩 꺼내서 탐색하기. 

 

- 큐에서 하나씩 꺼내서 방향에 적절한 경우를 나눠 따라 탐색을 수행하였습니다. 

 

- 특정 방향의 탐색이 종료되는 경우는 2가지 입니다. 

  1. 벽을 만났을 때

  2. 방문 할 좌표의 visit의 값이 작거나 같을 때

 

- 정답이 안되는 경우는 없다고 문제 명시되어 정답을 발견했을 때 탐색 종료 말고 다른 종료조건을 넣어주지 않았습니다. 

 

코드

public class Num2151_거울설치 {
    private static class Pair{
        int x;
        int y;
        int direction;
        int number;

        Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
        Pair(int x, int y,int direction,int number){
            this.direction = direction;
            this.x = x;
            this.y = y;
            this.number = number;
        }
    }
    static List<Pair> door;
    static List<Pair> mirror;
    static char[][] map;
    static int n;
    static int[] dx = {-1,0,1,0}, dy={0,1,0,-1};
    static int[][] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        door = new ArrayList<>();
        mirror = new ArrayList<>();
        map = new char[n][n];
        visit = new int[n][n];
        for(int i=0;i<n;i++){
            Arrays.fill(visit[i],Integer.MAX_VALUE);
            String input = br.readLine();
            for(int j=0;j<n;j++){
                map[i][j] = input.charAt(j);
                if(input.charAt(j) == '!'){
                    mirror.add(new Pair(i,j));
                }
                if(input.charAt(j) == '#'){
                    door.add(new Pair(i,j));
                }
            }
        }
        PriorityQueue<Pair> que = new PriorityQueue<>(new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                return o1.number - o2.number;
            }
        });
        // 첫 문에서 보이는 거울을 탐색
        for(int i=0;i<4;i++){
            int  cnt = 1;
            while (checkMap(door.get(0),i,cnt)){
                if(map[door.get(0).x+dx[i]*cnt][door.get(0).y+dy[i]*cnt] == '!'){
                    visit[door.get(0).x+dx[i]*cnt][door.get(0).y+dy[i]*cnt] = 1;
                    que.add(new Pair(door.get(0).x+dx[i]*cnt,door.get(0).y+dy[i]*cnt,i,1));
                }
                if(map[door.get(0).x+dx[i]*cnt][door.get(0).y+dy[i]*cnt] == '#'){
                    System.out.println(0);
                    return;
                }
                cnt++;
            }
        }
//        System.out.println(que.size());
        int answer = 0;
        Loop1 :
        while(true){
            int queSize = que.size();
            answer++;
            Loop2 :
            for(int i=0;i<queSize;i++){
                Pair now = que.poll();
                if(now.direction %2 ==0){
                    int cnt = 1;
                    while (checkMap(now,1,cnt)){
                        if(map[now.x+dx[1]*cnt][now.y+dy[1]*cnt] == '!') {
                            if(visit[now.x+dx[1]*cnt][now.y+dy[1]*cnt] <= now.number) break;
                            visit[now.x+dx[1]*cnt][now.y+dy[1]*cnt] = now.number+1;
                            que.add(new Pair(now.x + dx[1] * cnt, now.y + dy[1] * cnt, 1,now.number+1));
                        }else if(map[now.x+dx[1]*cnt][now.y+dy[1]*cnt] == '#'){
                            break Loop1;
                        }
                        cnt++;
                    }
                    cnt = 1;
                    while (checkMap(now,3,cnt)){
                        if(map[now.x+dx[3]*cnt][now.y+dy[3]*cnt] == '!') {
                            if(visit[now.x+dx[3]*cnt][now.y+dy[3]*cnt] <= now.number) break;
                            visit[now.x+dx[3]*cnt][now.y+dy[3]*cnt] = now.number+1;
                            que.add(new Pair(now.x + dx[3] * cnt, now.y + dy[3] * cnt, 3, now.number+1));
                        }else if(map[now.x+dx[3]*cnt][now.y+dy[3]*cnt] == '#'){
                            break Loop1;
                        }
                        cnt++;
                    }
                }else{
                    int cnt = 1;
                    while (checkMap(now,0,cnt)){
                        if(map[now.x+dx[0]*cnt][now.y+dy[0]*cnt] == '!') {
                            if(visit[now.x+dx[0]*cnt][now.y+dy[0]*cnt] <= now.number) break;
                            visit[now.x+dx[0]*cnt][now.y+dy[0]*cnt] = now.number+1;
                            que.add(new Pair(now.x + dx[0] * cnt, now.y + dy[0] * cnt, 0, now.number+1));
                        }else if(map[now.x+dx[0]*cnt][now.y+dy[0]*cnt] == '#'){
                            break Loop1;
                        }
                        cnt++;
                    }
                    cnt = 1;
                    while (checkMap(now,2,cnt)){
                        if(map[now.x+dx[2]*cnt][now.y+dy[2]*cnt] == '!') {
                            if(visit[now.x+dx[2]*cnt][now.y+dy[2]*cnt] <= now.number) break;
                            visit[now.x+dx[2]*cnt][now.y+dy[2]*cnt] = now.number+1;
                            que.add(new Pair(now.x + dx[2] * cnt, now.y + dy[2] * cnt, 2,now.number+1));
                        }else if(map[now.x+dx[2]*cnt][now.y+dy[2]*cnt] == '#'){
                            break Loop1;
                        }
                        cnt++;
                    }
                }
            }
        }
        System.out.println(answer);
    }
    public static boolean checkMap(Pair pair, int index, int cnt){
        if(pair.x+dx[index]*cnt<n && pair.x+dx[index]*cnt>=0 &&
                pair.y+dy[index]*cnt<n && pair.y+dy[index]*cnt>=0 &&
                map[pair.x+dx[index]*cnt][pair.y+dy[index]*cnt] != '*'){
            return true;
        }
        return false;
    }
}

 

 

후기

- 우선순위 큐를 구지구지 사용할 이유가 있을까?

  제가 우선순위 큐를 굉장히 아끼지만.. 그래도 생각해보겠습니다. 우선순위 큐를 사용한 의도는 "큐에 넣어주는 탐색 중 최소의 값부터 탐색"을 위해서입니다. 그럼 일반 큐를 사용하였을 때 이전의 탐색보다 더 적은 값을 가지게 되는 상황이 있을까용? 그럼 탐색 과정에 대해 생각해 보겠습니다.

 

  1. 탐색 경로의 1개의 거울이 존재 및 그 거울을 선택. 

  2. k개의 거울을 지난 후 거울을 선택.

 

2개의 경우 모두 " 이전의 탐색보다 더 적은 정답을 가지게 되는 상황"이 나오지 않는 것 같습니다. BFS인걸 생각해 보면 당연한 조건 같네요.

 

- 시간 복잡도 계산해보기. 

 이 문제를 백트래킹으로 풀어 보려했습니다. 2의 2500 승 이죠?