[백준] 6087 레이저 통신 - Java

 

문제 출저

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

6087번: 레이저 통신

 

 

문제 풀이

높이 h, 넓이 w 인 격자판이 주어집니다. 격자판 안에는 레이저를 이어야 하는 지점인 C 2개와 벽인 *, 레이저가 지나가는 . 으로 이루어져 있습니다. 이 때 거울을 설치하면 레이저의 방향을 90도 바꿀 수 있습니다. C끼리 레이저로 연결하기 위해 최소한의 거울 갯수를 구하는 것이 문제의 요구사항 입니다.

 

다익스트라 알고리즘으로 풀었습니다. 

int[h][w][4] dp 인 3차원 배열을 선언합니다. 이 배열은 4방향으로 들어온 최솟값을 저장하게 됩니다.

 

C 중 하나의 값을 탐색으로 진행합니다. 

BFS 방식을 사용했고 Queue 를 만들어 4방향을 탐색했습니다. 

이 때, 빛은 반대방향으로 꺾을 수 없으므로 반대 방향은 탐색에서 제외했습니다.

90도로 꺾을 때 마다 +1을 해주었습니다. 다음 지점을 탐색할 때 dp에 저장된 값과 비교하여 작은 경우 탐색을 진행합니다. 이 때, 작은 값은 dp에 저장하여 그 지점은 항상 최소값으로 유지되게 했습니다. 

 

 

소스 코드

package baekjoon.backjoon9.day27;

import java.util.*;
import java.lang.*;
import java.io.*;

/*
레이저 통신
https://www.acmicpc.net/problem/6087
 */

public class B6087 {

    static int w,h;
    static char[][] board;
    static int[] start;
    static int[] end;

    static int[][][] dp;
    static int INF = Integer.MAX_VALUE;

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


    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());

        board = new char[h][w];
        start = new int[2];
        end = new int[2];
        boolean flag = false;

        for(int i = 0; i < h; i++) {
            String str = br.readLine();
            for(int j = 0; j < w; j++) {
                board[i][j] = str.charAt(j);

                if(board[i][j] == 'C') {
                    if(flag == false) {
                        start[0] = i;
                        start[1] = j;
                        flag = true;
                    }
                    else {
                        end[0] = i;
                        end[1] = j;
                    }
                }
            }
        }

        dp = new int[h][w][4];
        for(int i = 0; i < h; i++) {
            for(int j = 0; j < w; j++) {
                Arrays.fill(dp[i][j], INF);
            }
        }

        Queue<dot> que = new LinkedList<>();
        for(int i = 0; i < 4; i++) {
            que.add(new dot(start[0], start[1], i, 0));
            dp[start[0]][start[1]][i] = 0;
        }



        while (!que.isEmpty()) {

            dot d = que.poll();

            for(int i = 0; i < 4; i++) {

                // 뒤로 쏘는 방향은 없다
                if(Math.abs(d.dir - i) == 2) {
                    continue;
                }

                int ny = d.y + dy[i];
                int nx = d.x + dx[i];

                if(check(ny,nx)) {

                    int newCount = d.count;

                    // 거울을 설치할 경우
                    if(Math.abs(d.dir - i) == 1 || Math.abs(d.dir - i) == 3) {
                        newCount += 1;
                    }

                    if(dp[ny][nx][i] > newCount) {
                        dp[ny][nx][i] = newCount;
                        que.add(new dot(ny, nx, i, newCount));
                    }

                }
            }
        }

        int answer = INF;
        for(int i = 0; i < 4; i++) {
            answer = Math.min(answer, dp[end[0]][end[1]][i]);
        }
        System.out.println(answer);



    }

    public static boolean check(int y, int x) {
        if(y >= 0 && y < h && x >= 0 && x < w && board[y][x] != '*') {
            return true;
        }
        else {
            return false;
        }
    }

    public static class dot {
        int y;
        int x;
        int dir;
        int count;

        dot(int y, int x, int dir, int count) {
            this.y = y;
            this.x = x;
            this.dir = dir;
            this.count = count;
        }
    }
}