[PS] 백준2151 : 거울 설치(Java)

문제

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

2151번: 거울 설치

---

풀이

3차원 방문체크를 활용한 Dijkstra 풀이

문제이해

문제를 읽고 예제를 보고 이해를 하려는데 개인적으로 상당히 난해했음.

일단 동작과정은 아래와 같음.

1. #이라는 문에 대해서 어느 방향에서든 출발해도 상관없음.
2. 빈칸 ‘.’에 대해 진행방향 그대로 직진만 가능.
3. ‘!’ 칸은 거울 설치 가능한 곳으로써 해당 자리에 거울을 45도 설치 가능.
4. 거울을 설치하게 되면 빛은 직진이 아닌 90도, 180도로 이동 가능.
5. 예를 들어 아래로 내려가다가 !를 만나면 왼쪽 또는 오른쪽으로 굴절이 가능. 물론 거울을 설치하지 않는다고 하면 그대로 직진.

주어지는 조건으로 하나의 문(#)에서 다른 문으로 가는 길은 무조건 존재. ( == 어디서 출발해도 상관없다.)

---

접근법

처음 접근해보는 문제라면 방문체크 어떻게 할지 엄청 고민을 하게 될 문제.

해당 문제와 같은 경우 방문체크를 3차원으로 선언하여 현재 좌표 (i,j)에 대해 4방향에 대한 체크를 통해 백트래킹을 할 수 있음.

또한 최소 개수를 구하는 문제로써 PriorityQueue를 거울 설치 개수로 정렬을 재정의하여 사용하는 것으로 처음으로 도착하는 경우에 대해 최적해를 보장해줄 수 있음.

주의할 점으로는

1. 거울을 설치안할 경우도 있기 때문에 ‘!’에 대해서 3방향 탐색을 진행해야함.
2. 다음 좌표에 대해 방문체크를 하는 것이 아닌 큐에서 꺼낸 현재 좌표에 대해 방문체크를 진행해야함. (다음 좌표에 대해 진행할 시 82% 틀렸습니다.)

 

---

소스코드

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

//BOJ_2151 거울 설치
public class Main {
    static int N, res;
    static int[] dx = new int[]{0,0,1,-1};
    static int[] dy = new int[]{1,-1,0,0};
    static char[][] map;
    static int[] start = new int[2];
    static int[] dest = new int[2];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb;

        N = Integer.parseInt(br.readLine());

        map = new char[N][N];
        boolean flag = true;
        for(int i=0; i<N; i++) {    //맵 입력
            String input = br.readLine();
            for(int j=0; j<N; j++) {
                char idx = input.charAt(j);
                map[i][j] = idx;
                //임의의 시작위치와 도착위치를 설정
                if(idx == '#') {
                    if(flag) {
                        start[0] = i;
                        start[1] = j;
                        map[i][j] = '@';
                        flag = false;
                    }
                    else {
                        dest[0] = i;
                        dest[1] = j;
                        map[i][j] = '$';
                    }
                }
            }
        }

        res = Integer.MAX_VALUE;
        Dijkstra();

        System.out.println(res);
    }

    private static void Dijkstra() {
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];   //거울 설치 개수를 기준
            }
        });

        boolean[][][] v = new boolean[4][N][N];
        for(int i=0; i<4; i++) {
            v[i][start[0]][start[1]] = true;
        }

        //시작위치에서 갈 수 있는 곳들에 대해 큐 추가
        for(int i=0; i<4; i++) {
            int nx = start[0] + dx[i];
            int ny = start[1] + dy[i];
            if(nx<0 || ny<0 || nx>=N || ny>=N || map[nx][ny] == '*') continue;
            pq.offer(new int[]{nx, ny, 0, i});
        }

        while(!pq.isEmpty()) {
            int[] cur = pq.poll();

            int x = cur[0];
            int y = cur[1];

            v[cur[3]][x][y] = true;

            if(map[x][y] == '$') {  //도착했을 경우
                res = cur[2];
                return;
            }

            if(map[x][y] == '!') {      //현재 위치가 거울 설치 가능한 곳일 경우
                if(cur[3] == 2 || cur[3] == 3) {    //좌우
                    for(int i=0; i<2; i++) {
                        int nx = x + dx[i];
                        int ny = y + dy[i];
                        if (nx < 0 || ny < 0 || nx >= N || ny >= N || v[i][nx][ny] || map[nx][ny] == '*') continue;
                        pq.offer(new int[]{nx, ny, cur[2] + 1, i});
                    }
                }
                else {
                    for(int i=2; i<4; i++) {
                        int nx = x + dx[i];
                        int ny = y + dy[i];
                        if (nx < 0 || ny < 0 || nx >= N || ny >= N || v[i][nx][ny] || map[nx][ny] == '*') continue;
                        pq.offer(new int[]{nx, ny, cur[2] + 1, i});
                    }
                }
            }

            //직진 Case
            int nx = x + dx[cur[3]];
            int ny = y + dy[cur[3]];
            if(nx<0 || ny<0 || nx>=N || ny>=N || v[cur[3]][nx][ny] || map[nx][ny] == '*') continue;
            pq.offer(new int[]{nx, ny, cur[2], cur[3]});
        }
    }
}

 

 

---

정리

BOJ_30894 유령의 집 탈출하기나 BOJ_2206 벽 부수고 이동하기와 같이 3차원 방문체크를 해야하는 문제들이 종종 있는 것 같음.

다음 좌표에 대해 방문체크를 진행할 시 왜 틀리게 나오는지에 대한 반례를 찾아서 추가해야할 것 같음.