[JAVA] 백준 2151 - 거울 설치

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

 

집 안에 거울을 설치해서 한쪽 문에서 다른 쪽 문을 거울을 통해 바라볼 수 있게 되는 거울 설치 개수의 최솟값을 구하는 문제이다.

처음에는 거울이 45도 기울어졌대서 대각선 이동인줄알고 그렇게 작성했는데 보니까 거울이 45도로 기울어져 있으면 빛의 진행방향이 90도 꺾이는 구조였다. 빈 공간을 만난 경우 진행했던 방향으로 계속 직진을 해야하고, 거울을 설치할 수 있는 공간을 만나면 설치하지 않고 빈 공간처럼 진행하거나, 입장 방향의 수직방향으로 꺾어서 진행할 수 있다.

따라서 진행 방향을 저장해야했고, 진행 방향별 방문체크와 가중치를 저장하면서 진행했다.

도착지점은 최대 4방향에서 접근 가능하므로 dist배열에 4방향의 최소 가중치를 저장한 뒤 우선순위큐를 탈출하고 해당 지점의 진행방향별 가중치의 최솟값을 구해서 출력했다.

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

public class Main {

    static class Location implements Comparable<Location> {
        int value;
        int i;
        int j;
        int direction = 0;
        int dist = 0;

        Location(int v, int i, int j, int direction) {
            this.value = v;
            this.i = i;
            this.j = j;
            this.direction = direction;
        }

        @Override
        public int compareTo(Location o) {
            return this.dist - o.dist;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = par(br.readLine());
        int[][] map = new int[n][n];
        int[][][] dist = new int[4][n][n];
        boolean[][][] visited = new boolean[4][n][n];
        int si = -1;
        int sj = -1;
        for (int i = 0; i < n; i++) {
            char[] arr = br.readLine().toCharArray();
            for (int j = 0; j < arr.length; j++) {
                map[i][j] = arr[j] == '*' ? -1 : arr[j] == '#' ? 2 : arr[j] == '.' ? 0 : 1;
                if (map[i][j] == 2) {
                    si = i;
                    sj = j;
                }
            }
        }
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < n; j++) {
                Arrays.fill(dist[i][j],Integer.MAX_VALUE);
            }
        }
        map[si][sj] = -1;
        PriorityQueue<Location> pq = new PriorityQueue<>();
        for (int i = 0; i < 4; i++) {
            if (check(si + dx[i], sj + dy[i], map,visited,i)) {
                Location start = new Location(-1, si, sj, i);
                dist[i][si][sj] = 0;
                pq.offer(start);
            }
        }


        while (!pq.isEmpty()) {
            Location t = pq.poll();
            int value = t.value;
            int i = t.i;
            int j = t.j;
            int direction = t.direction;
            if (value == 2) {
                continue;
            }
            if(dist[direction][i][j]<t.dist) continue;
            visited[direction][i][j] = true;
            //일단 진행방향으로 진행할 수 있으면 직진(거울도 .취급)
            int tx = i + dx[direction];
            int ty = j + dy[direction];
            if (check(tx, ty, map,visited,direction)) {
                dist[direction][tx][ty] = dist[direction][i][j];
                Location c = new Location(map[tx][ty], tx, ty, direction);
                c.dist = dist[direction][tx][ty];
                pq.offer(c);
            }
            if (value == 1) { //거울 설치장소를 만난 경우
                switch (direction) {
                    case 0: //상승
                    case 3:
                        int[] targetD = {1, 2};
                        for (int k = 0; k < 2; k++) {
                            tx = i + dx[targetD[k]];
                            ty = j + dy[targetD[k]];
                            if (check(tx, ty, map,visited,targetD[k])) {
                                int weight = 1;
                                if( dist[targetD[k]][tx][ty]>dist[direction][i][j] + weight) {
                                    dist[targetD[k]][tx][ty] = dist[direction][i][j] + weight;
                                    Location c = new Location(map[tx][ty], tx, ty, targetD[k]);
                                    c.dist = dist[targetD[k]][tx][ty];
                                    pq.offer(c);
                                }
                            }
                        }
                        break;
                    case 1:
                    case 2:
                        int[] tD = {3, 0};
                        for (int k = 0; k < 2; k++) {
                            tx = i + dx[tD[k]];
                            ty = j + dy[tD[k]];
                            if (check(tx, ty, map,visited,tD[k])) {
                                int weight = 1;
                                if( dist[tD[k]][tx][ty]>dist[direction][i][j] + weight){
                                    dist[tD[k]][tx][ty] = dist[direction][i][j] + weight;
                                    Location c = new Location(map[tx][ty], tx, ty, tD[k]);
                                    c.dist = dist[tD[k]][tx][ty];
                                    pq.offer(c);
                                }

                            }
                        }
                        break;
                }
            }
        }int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(map[i][j]==2){
                    for (int k = 0; k < 4; k++) {
                        min = Math.min(dist[k][i][j], min);
                    }
                }
            }
        }
        System.out.println(min);
    }

    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, 1, -1, 0};

    static boolean check(int i, int j, int[][] map, boolean[][][] visited, int direction) {
        if (i < 0 || i >= map.length) return false;
        if (j < 0 || j >= map.length) return false;
        if (map[i][j] == -1) return false;
        if(visited[direction][i][j]) return false;
        return true;
    }

    static int par(String s) {
        return Integer.parseInt(s);
    }
}