[백준2151] 거울 설치

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

2151번: 거울 설치

 

백준 2151 거울 설치 문제입니다.

 

다익스트라를 활용해서 풀었습니다.

 

---

문제 풀이

 

먼저 알아야 할 것

• 거울을 둘 수 있는 곳과 빛이 통과할 수 있는 곳의 가중치를 다르게 둔다.
• 거울을 둘 수  있는 곳은 빛이 들어온 방향의 직선, 왼쪽, 오른쪽으로 빛을 보낼 수있다.
• 거울을 둘 수 없는 곳은 빛이 들어온 같은 방향으로만 빛을 보낼 수 있다.

 

중요한 개념

• 다른 다익스트라 문제와 마찬가지로 방문 여부를 체크하기 위해 visit이 필요합니다. 다만, 이 문제는 어디서 빛이 들어왔는지 알아야 하기 때문에 boolean[][][] visit으로 만듭니다.
• 보통  dx = {-1,1,0,0}, dy = {0,0,-1,1} 이렇게 다음 x,y의 값을 구하기 위해서 배열을 사용합니다. 여기서 dx[0]과 dy[0]은 -1,0 임을 확인할 수 있고 그림 상에서는 위로 간 것을 알 수  있습니다. 따라서, 위로 올라갔는데 거울을 둘 수 있는 지점이면 위, 오른쪽, 왼쪽으로 빛을 또 보낼 수 있는 것입니다. 여기서 오른쪽으로 보내기 위해서는 3번째 인덱스를 넣어줘야 하고 왼쪽으로 보내기 위해서는 2번째 인덱스를 넣어야 합니다. (코드로 확인해보시면 더 이해하기 쉬울겁니다!)

---

코드

package codingtest.baek2151;

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

public class Main {

    static char[][] map;
    static boolean[][][] visit;
    static int sx, sy, ex, ey, N;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int[] d1 = {2,3,1,0};
    static int[] d2 = {3,2,0,1};

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

        map = new char[N][N];
        visit = new boolean[N][N][4];

        int index = 0;
        for(int i = 0; i<N;i++) {
            char[] charArray = br.readLine().toCharArray();
            for(int j = 0; j<N;j++) {
                map[i][j] = charArray[j];
                if(map[i][j] == '#' && index == 0) {
                    index++;
                    sx = i;
                    sy = j;
                }
                if(map[i][j] == '#' && index == 1) {
                    ex = i;
                    ey = j;
                }
            }
        }

        dijkstra();
    }

    private static void dijkstra() {
        PriorityQueue<Node> p = new PriorityQueue<>((o1,o2) -> o1.cnt - o2.cnt);

        // 0 : 왼, 1 : 오, 2 : 아래, 3 : 위
        for(int i = 0; i<4; i++) {
            p.add(new Node(sx, sy, i,0));
        }

        int min = 0;
        while (!p.isEmpty()) {
            Node now = p.poll();

            if(!visit[now.x][now.y][now.d]) {
                visit[now.x][now.y][now.d] = true;

                if(now.x == ex && now.y == ey) {
                    min = now.cnt;
                    break;
                }

                int nx = now.x + dx[now.d];
                int ny = now.y + dy[now.d];

                if(nx >= 0 && ny >=0 && nx <N && ny < N && map[nx][ny] != '*') {
                    if(map[nx][ny] == '!') {
                        int tmp = now.cnt;
                        p.add(new Node(nx,ny,d1[now.d], tmp+1));
                        p.add(new Node(nx,ny,d2[now.d], tmp+1));
                    }
                    p.add(new Node(nx,ny, now.d, now.cnt));
                }
            }
        }
        System.out.println(min);
    }

    static class Node{
        int x;
        int y;
        int d;
        int cnt;

        public Node(int x, int y, int d, int cnt) {
            this.x = x;
            this.y = y;
            this.d = d;
            this.cnt = cnt;
        }
    }
}