[백준] 6087번 : 레이저 통신

6087번: 레이저 통신

---

[BFS]

바로 본론부터 얘기하자면, 일반적인 BFS와 다른 점이 존재한다. 바로 각 정점은 방향을 갖는다는 것이다. 여기서 방향이란 상하좌우를 의미한다. 방향이 존재하므로 배열도 3차원이 되어야한다. 예를 들어 방문했는지에 대한 체크하는 배열 visit[ ][ ][4], 각 정점에서 해당 방향으로 도착했을 때의 거울이 몇개 필요했는지에 대한 배열 mir[ ][ ][4].

 

이뿐만이 아니다. 레이저와 거울의 특성을 고려해보면, 레이저를 거울에 비추었을 때 레이저 광선은 일직선으로 쭉 반사된다. 여기서도 동일하게 적용해주어야 한다.

 

.	/	C
.	|	.
C	|	.

(1, 3)에서 레이저를 쏴서 (1, 2)에 거울을 설치한다 했을 때, 레이저는 아래방향으로 꺾이게 된다. 이때 (2, 2), (3, 2)를 모두 Q에 넣어주어야 한다. (단, 벽을 만나거나 이미 해당 방향으로 방문했던 정점이면 continue)

 

그리고 거울을 추가하는 조건은 0, 1, 2, 3이 방향일 때

0 : 상

1 : 좌

2 : 하

3 : 우

이다. 즉 방향 % 2 == 0일 때는 상/하이고 아닐 때는 좌/우 이다. 따라서 현재 방향과 다음 방향이 무엇인지에 따라 거울이 추가되고 안되고가 결정된다.

 

           for(int a=0; a<4; a++){
                int ny = y+Y[a];
                int nx = x+X[a];
                int nMirror = mirror;

                if(ny < 1 || nx < 1 || ny > h || nx > w || visit[ny][nx][a] || map[ny][nx] == '*') continue;

                if(dir % 2 == 0 && a % 2 != 0 && dir >= 0)
                    nMirror++;
                else if(dir % 2 != 0 && a % 2 == 0 && dir >= 0)
                    nMirror++;
                    
                    ...

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static class Point{
        int y, x, dir, mirror;
        public Point(int yy, int xx, int d, int mirror){
            y=yy;
            x=xx;
            dir=d;
            this.mirror = mirror;
        }
    }
    static final int INF = 1000000000;
    
    static int[] Y = {-1, 0, 1, 0}, X = {0, -1, 0, 1}; //0:상  1:좌  2:하  3:우
    static char[][] map = new char[101][101];
    static int w, h;

    static int[][][] mir = new int[101][101][4];
    static boolean[][][] visit = new boolean[101][101][4];
    static void BFS(Point start){

        Queue<Point> Q = new LinkedList<>();

        for(int a=0; a<4; a++)
            mir[start.y][start.x][a] = 0;

        Q.add(new Point(start.y, start.x, -1, 0));

        while(!Q.isEmpty()){
            Point p = Q.poll();
            int y = p.y;
            int x = p.x;
            int dir = p.dir;
            int mirror = p.mirror;

            for(int a=0; a<4; a++){
                int ny = y+Y[a];
                int nx = x+X[a];
                int nMirror = mirror;

                if(ny < 1 || nx < 1 || ny > h || nx > w || visit[ny][nx][a] || map[ny][nx] == '*') continue;

                if(dir % 2 == 0 && a % 2 != 0 && dir >= 0)
                    nMirror++;
                else if(dir % 2 != 0 && a % 2 == 0 && dir >= 0)
                    nMirror++;

                visit[ny][nx][a] = true;
                mir[ny][nx][a] = nMirror;
                Q.add(new Point(ny, nx, a, nMirror));

                while(true){
                    ny = ny+Y[a];
                    nx = nx+X[a];

                    if(ny < 1 || nx < 1 || ny > h || nx > w || visit[ny][nx][a] || map[ny][nx] == '*') break;

                    visit[ny][nx][a] = true;
                    mir[ny][nx][a] = nMirror;
                    Q.add(new Point(ny, nx, a, nMirror));
                }
            }
        }
    }

    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());
        Point[] p = new Point[2];

        for(int i=1, idx=0; i<=h; i++){
            char[] str = br.readLine().toCharArray();
            for(int j=1; j<=w; j++){
                map[i][j] = str[j-1];

                if(map[i][j] == 'C')
                    p[idx++] = new Point(i, j, -1, 0);

                for(int a=0; a<4; a++)
                    mir[i][j][a] = INF;
            }
        }
        BFS(p[0]);

        int min = INF;
        for(int a=0; a<4; a++)
            min = Math.min(min, mir[p[1].y][p[1].x][a]);

        System.out.println(min);
    }
}

# Reference

반례 모음