[백준] 6087번 레이저 통신 (Java)

백준 6087번 레이저 통신 : https://www.acmicpc.net/problem/6087

6087번: 레이저 통신

 

 

생각보다 오래 걸렸던 문제이다.

최소 개수의 거울을 사용해서 두 'C'를 연결하면 된다.

 

bfs를 사용하기 위해 Node라는 클래스와 PriorityQueue를 사용했다.

Node에는 좌표를 나타내는 x, y와 해당 위치까지 사용된 거울의 개수인 cost, 방향을 나타내는 dir을 필드로 갖고 있다.

Queue에서 cost가 낮은 것들을 먼저 꺼내기 위해 PriorityQueue를 사용했다.

 

2차원 int 배열인 visit에 해당 위치까지 필요한 거울의 개수를 저장한다.

dx, dy 배열을 사용해서 다음 위치에서의 방향과 현재 위치에서의 방향이 다르면 cost를 1 증가시키고, 같다면 cost를 그대로 가져간다.

또한 중복을 제거하기 위하여 visit에 저장된 값보다 cost가 적거나 같을 경우에만 Queue에 추가했다.

 

 

코드

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 Main {
    private static int w, h;
    private static char[][] map;
    private static int[][] visit;
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, 1, 0, -1};
    private static Node start, end;

    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());
        map = new char[h][w];
        visit = new int[h][w];

        for (int i = 0; i < h; i++) {
            Arrays.fill(visit[i], w * h);
        }

        boolean flag = false;
        for (int i = 0; i < h; i++) { // 입력
            map[i] = br.readLine().toCharArray();
            for (int j = 0; j < w; j++) {
                if (map[i][j] == 'C') {
                    if (flag) end = new Node(i, j, 0, 4);
                    else {
                        start = new Node(i, j, 0, 4);
                        flag = true;
                    }
                }
            }
        }

        int answer = bfs();
        System.out.println(answer);
    }

    private static int bfs() {
        Queue<Node> queue = new PriorityQueue<>();

        visit[start.x][start.y] = 0;
        queue.add(start);

        Node node;
        while (!queue.isEmpty()) {
            node = queue.poll();
            if (node.x == end.x && node.y == end.y) return node.cost; // 도착

            for (int i = 0; i < 4; i++) { // 동서남북 
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];

                if (!isValid(nx, ny) || map[nx][ny] == '*') continue; // 맵 밖으로 나갔는지, 벽인지

                if (node.dir == i || node.dir == 4) { // 방향이 같으면
                    if (visit[nx][ny] >= node.cost) {
                        visit[nx][ny] = node.cost;
                        queue.add(new Node(nx, ny, node.cost, i));
                    }
                } else { // 방향이 다르면
                    if (visit[nx][ny] >= node.cost + 1) {
                        visit[nx][ny] = node.cost + 1;
                        queue.add(new Node(nx, ny, node.cost + 1, i));
                    }
                }
            }
        }
        return -1;
    }

    private static boolean isValid(int x, int y) {
        if (x < 0 || y < 0 || x >= h || y >= w) return false;
        return true;
    }
}

class Node implements Comparable<Node> {
    int x;
    int y;
    int cost;
    int dir;

    public Node(int x, int y, int cost, int dir) {
        this.x = x;
        this.y = y;
        this.cost = cost;
        this.dir = dir;
    }

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