백준 2151. 거울 설치 :: 돼지개발자

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

"다른 조건을 최소화 하는 경우를 찾으려면 우선순위 큐 혹은 다익스트라!"

해당 문제와 비슷한 유형의 문제들이 많다. 목적지 까지 가는 길에 무엇을 한 최소 횟수를 구하는 등의 문제들이 있다.

다익스트라로 풀거나 우선순위 큐로 풀 수 있다. 나는 우선순위 큐를 사용해서 풀었다. 맨 처음에는 우선순위를 그냥 '-1' 과 '0' 으로만 주어서제대로 탐색이 되지 않았다. 비교 대상과의 차이를 우선순위로 두어서 내가 원하는대로 탐색하게 할 수 있었다. 우선순위 큐를 쓸 때는 디버깅이 힘든 것 같다. 우선순위 체크를 할 때 매우 신중히 해야 할것.

더해서 목적지 까지 찾아가는 문제의 경우 어떻게 하면 중복되는 부분을 체크하고 줄일 수 있는지가 관건인 것 같다.

또 하나 배치할 수 있는 거울은 '/' 과 '＼' 이므로 주의해야 한다. 각 거울 모양에 따라 d1 과 d2 배열을 두어서 거울에 반사 됐을 때, index 가 변하게 되는 방향을 배열에 저장해 두었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
 
public class Main {
 
    static int N;
    static char[][] map;
    static PriorityQueue<Node> q = new PriorityQueue<>();
    static int sx,sy,ex,ey;
    static boolean[][][] visited;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static int[] d1 = {3,2,1,0};
    static int[] d2 = {2,3,0,1};
    
    static int min;
    
    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];
        visited = new boolean[N][N][4];
        
        int idx = 0;
        for (int i = 0; i < N; i++) {
            char[] temp = br.readLine().toCharArray();
            for (int j = 0; j < N; j++) {
                map[i][j] = temp[j];
                if(temp[j] == '#') {
                    if(idx == 0) {
                        sx = i;
                        sy = j;
                    }
                    else {
                        ex = i;
                        ey = j;
                    }
                    idx++;
                }
            }
        }
        
        for (int i = 0; i < 4; i++) {
            q.add(new Node(sx, sy, i, 0));
        }
        
        while(!q.isEmpty()) {
            
            Node cur = q.poll();
            
            int x = cur.x;
            int y = cur.y;
            int d = cur.d;
            int c = cur.c;
            
            if(visited[x][y][d]) continue;
            
            visited[x][y][d] = true;
            
            if(cur.x == ex && cur.y == ey ) {
                min = cur.c;
                break;
            }
            
            int nx = x + dx[d];
            int ny = y + dy[d];
            
            if(!isRange(nx, ny) || map[nx][ny] == '*')
                continue;
 
            if(map[nx][ny] == '!') {
                q.add(new Node(nx, ny, d1[d], c+1));
                q.add(new Node(nx, ny, d2[d], c+1));
            }
            q.add(new Node(nx, ny, d, c));
        }
        System.out.println(min);
    }
    
    static boolean isRange(int x, int y) {
        if(x < 0 || x >= N || y < 0 || y >= N) return false;
        return true;
    }
}
 
class Node implements Comparable<Node> {
    int x;
    int y;
    int d;
    int c;
    
    Node ( int x, int y , int d, int c) {
        this.x = x;
        this.y = y;
        this.d = d;
        this.c = c;
    }
    
    @Override
    public int compareTo(Node o) {
        return this.c - o.c;
    }
}