백준 - 거울 설치(2151)

오늘 풀어볼 문제는 ⭐거울 설치 라는 문제이다.

반 년 전에 풀어보려고 시도했는데, 오랫동안 풀지 못해서 오기가 생긴 문제다.. 실력 키워서 다음에 꼭 풀어주마 하고 넘긴 문젠데 결국 풀었다!

1. 문제요약

• 집의 크기 N*N이 주어지고, 문이 2개 있다.
• 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 거울을 설치한다.
• 거울은 45도 기울어진 대각선 방향으로 설치한다. (즉 90도 꺾인채 빛이 굴절됨)
• 거울은 양면이기에 양 쪽 모두에서 반사가 생긴다. (거울은 무제한)

2. 입출력

[입력]

• 집의 크기 N (2 <= N <= 50)
• #은 문 설치 위치, .은 빈 공간, !은 거울 설치 가능 위치, *은 벽

[출력]

• 설치해야 하는 거울의 최소 개수

3. 테스트케이스

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

4. 알고리즘

이 문제는 다익스트라와 3차원 배열을 활용하는 문제이다.

3차원 배열은, [x 위치][y 위치][현재 방향]으로 인덱스를 잡아 해당 위치의 해당 방향에 도달했을 때 설치될 수 있는 최소 거울의 개수를 계속 갱신해주는 용도이다.

다익스트라는, PriorityQueue를 설치된 거울의 개수로 잡는다. 그러면 현재 최소로 설치된 거울이 있는 곳의 위치를 우선으로 뽑으며 도착지점까지 가도록 유도한다.

이 2가지만 유의해준다면 코드는 금방 짤 수 있었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Info {
    int x;
    int y;
    int mirror;
    int dir;

    public Info(int x, int y, int mirror, int dir) {
        this.x=x;
        this.y=y;
        this.mirror=mirror;
        this.dir=dir;
    }
}


public class Main {

    static boolean in(int x, int y, int n) {
        return 0 <= x && x < n && 0 <= y && y < n;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int [] dirX = {0,1,0,-1}; //방향 : 우,하,좌,상
        int [] dirY = {1,0,-1,0};

        int n = Integer.parseInt(br.readLine());
        char [][] map = new char[n][n];

        // dist[x][y][dir] = (x,y,dir)로 도달할 때 최소 거울 수
        final int INF = 1_000_000_000;
        int [][][] dist = new int[n][n][4];
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) Arrays.fill(dist[i][j], INF);

        Queue<Info> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.mirror));

        boolean flag = false;
        for(int i=0; i<n; i++) {
            map[i] = br.readLine().toCharArray();
            for(int j=0; j<n; j++){
                if(map[i][j]=='#'&&!flag) {
                    map[i][j] = '*';
                    flag=true;
                    for(int k=0; k<4; k++){
                        int nextX = i+dirX[k];
                        int nextY = j+dirY[k];
                        if(in(nextX, nextY, n) && map[nextX][nextY]!='*') {
                            queue.add(new Info(nextX, nextY, 0, k));
                            dist[nextX][nextY][k] = 0;
                        }
                    }
                }
            }
        }

        int answer=0;
        while (!queue.isEmpty()){
            Info now = queue.poll();

            // 도착이면 최소 거울 수 보장
            if (map[now.x][now.y] == '#') {
                answer = now.mirror;
                break;
            }
            if (map[now.x][now.y] == '*') continue;

            int nextX = now.x+dirX[now.dir];
            int nextY = now.y+dirY[now.dir];
            if(in(nextX, nextY, n) && map[nextX][nextY]!='*' && dist[nextX][nextY][now.dir] > now.mirror) {
                queue.add(new Info(nextX, nextY, now.mirror, now.dir));
                dist[nextX][nextY][now.dir] = now.mirror;
            }

            if(map[now.x][now.y]=='!') {
                //거울 설치가 가능한 경우2 : 현재 방향에서 90도 방향
                int nextDir = (now.dir+1)%4; 
                nextX = now.x+dirX[nextDir];
                nextY = now.y+dirY[nextDir];

                if(in(nextX, nextY, n) && map[nextX][nextY]!='*' && dist[nextX][nextY][nextDir] > now.mirror+1) {
                    queue.add(new Info(nextX, nextY, now.mirror+1, nextDir));
                    dist[nextX][nextY][nextDir] = now.mirror+1;
                }

                //거울 설치가 가능한 경우3 : 경우2에서 꺾은 90도의 반대 방향
                nextDir = (now.dir + 3) % 4;
                nextX = now.x+dirX[nextDir];
                nextY = now.y+dirY[nextDir];

                if(in(nextX, nextY, n) && map[nextX][nextY]!='*' && dist[nextX][nextY][nextDir] > now.mirror+1) {
                    queue.add(new Info(nextX, nextY, now.mirror+1, nextDir));
                    dist[nextX][nextY][nextDir] = now.mirror+1;
                }
            }


        }

        System.out.println(answer);

    }

}