[백준(자바/Java)] 6087_레이저 통신(BFS, 우선순위 큐)

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

6087번: 레이저 통신

 

BFS와 우선순위 큐를 사용하여 풀 수 있는 문제입니다. 카카오 2020 인턴십 "경주로 건설"과 비슷한 느낌의 문제라고 생각해서, 혹시 풀어보시지 않은 분이 계시면 풀어보면 좋을 것 같습니다.

코딩테스트 연습 - 경주로 건설

 

본론으로 돌아와서, 이 문제를 풀 때 중요한 것은 우선순위의 기준을 어떻게 잡는가입니다.

 

저는 현 위치까지 오는 데 필요한 거울의 개수를 우선순위를 적용했습니다. 각 지점을 방문할 때, 거울을 최소한으로만 사용해서 방법을 고려하겠다는 것이죠.

 

따라서 visited 배열을 단순히 True, False로 체크하지 않고 해당 지점까지 필요했던 거울의 개수를 입력하기로 했습니다.

 

다른 경로에서 해당 지점을 재방문했을 때 기존에 필요했던 거울의 개수보다 더 적은 갯수의 거울이 필요하다면 해당 지점을 재방문하고 갱신하겠다는 뜻이죠.

 

이를 구현한 코드는 아래와 같습니다. 

 

[풀이 - 자바]

package PS;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class B_6087 {
    static int w, h;
    static char[][] graph;
    static int[][] visited;
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};
    static Point start, end;

    public static class Point{
        int x,y;
        Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    public static class Node implements Comparable<Node>{
        int mirrors, x, y, direction;

        Node(int mirrors, int x, int y, int direction){
            this.mirrors = mirrors;
            this.x = x;
            this.y = y;
            this.direction = direction;
        }

        @Override
        public int compareTo(Node other){
            return this.mirrors - other.mirrors;
        }
    }

    public static int bfs(Point start, Point end){
        visited = new int[h][w];
        for (int i = 0; i < h; i++) {
            Arrays.fill(visited[i], Integer.MAX_VALUE);
            // 최대 값으로 초기화
        }
        Queue<Node> q = new PriorityQueue<>();
        q.add(new Node(0, start.x, start.y, -1));
        visited[start.x][start.y] = 0;

        while(!q.isEmpty()){
            // 거울을 설치해야 하는 횟수 구하기
            Node node = q.poll();
            int mirrors = node.mirrors;
            int curr_x = node.x;
            int curr_y = node.y;
            int curr_dir = node.direction;
            if (curr_x == end.x && curr_y == end.y){
                return mirrors;
            }

            for(int i = 0; i < 4; i++){
                int next_x = curr_x + dx[i];
                int next_y = curr_y + dy[i];

                if(0 <= next_x && next_x < h && 0 <= next_y && next_y < w){
                    if(graph[next_x][next_y] != '*'){

                        int temp = mirrors;
                        if(curr_dir != -1 && curr_dir != i){
                            temp++;
                        }
                        if (visited[next_x][next_y] < temp) continue;
                        visited[next_x][next_y] = temp;
                        q.offer(new Node(temp, next_x, next_y, i));
                    }
                }
            }
        }
        return -1;
    }


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        w = Integer.parseInt(st.nextToken());
        h = Integer.parseInt(st.nextToken());
        graph = new char[h+1][w+1];
        for(int i = 0; i < h; i++){
            String s = br.readLine();
            for(int j =0; j < w; j++){
                graph[i][j] = s.charAt(j);
                if(graph[i][j] == 'C'){
                    if(start == null) start = new Point(i,j);
                    else end = new Point(i,j);
                }
            }
        }
        System.out.println(bfs(start, end));
    }
}