백준 6087. 레이저 통신 :: 돼지개발자

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

"BFS는 갈수 있냐 없냐, 어떻게 중복을 제거할 것이냐가 중요."

거울 설치(https://www.acmicpc.net/problem/2151) 와 같은 문제이다. 

다른 조건을 최소화하는 경우를 구할 때는, 다익스트라 혹은 우선순위 큐를 사용한다. 더해서 BFS는 항상 갈 수 있냐 없냐, 어떻게 중복을 제거할 것이냐가 중요하다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
class Main {
 
    static int W,H;
    static char[][] map;
    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 sx,sy,ex,ey;
    static PriorityQueue<Node> q = new PriorityQueue<>();
    
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        
        map = new char[H][W];
        visited = new boolean[H][W][4];
        
        int idx = 0;
        for (int i = 0; i < H; i++) {
            char[] temp = br.readLine().toCharArray();
            for (int j = 0; j < W; j++) {
                map[i][j] = temp[j];
                
                if(temp[j] == 'C') {
                    map[i][j] = '.';
                    if(idx++ == 0)  {
                        sx = i;
                        sy = j;
                    }
                    else {
                        ex = i;
                        ey = j;
                    }
                }
            }
        }
        
        for (int i = 0; i < 4; i++) {
            visited[sx][sy][i] = true;
            q.add(new Node(sx, sy, i, 0));
        }
        while(!q.isEmpty()) {
            
            Node cur = q.poll();
            
            if(cur.x == ex && cur.y == ey) {
                System.out.println(cur.c);
                break;
            }
            
            int nx = cur.x + dx[cur.d];
            int ny = cur.y + dy[cur.d];
            
            if(!isRange(nx, ny) || visited[nx][ny][cur.d] || map[nx][ny] == '*')
                continue;
            
            visited[nx][ny][cur.d] = true;
            q.add(new Node(nx, ny, d1[cur.d], cur.c+1));
            q.add(new Node(nx, ny, d2[cur.d], cur.c+1));
            q.add(new Node(nx, ny, cur.d, cur.c));
        }
    }
 
    static boolean isRange(int x, int y) {
        if(x < 0 || x >= H || y < 0 || y >= W) 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;
    }
}