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

문제 링크

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

알고리즘: BFS, 다익스트라

문제

크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.

'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.

레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다.

아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.

7 . . . . . . . 7 . . . . . . .
6 . . . . . . C 6 . . . . . /-C
5 . . . . . . 5 . . . . . |
4 * * * * . 4 * * * * |
3 . . . . . . 3 . . . . | .
2 . . . . . . 2 . . . . | .
1 . C . . . . 1 . C . . | .
0 . . . . . . . 0 . -------/ .
0 1 2 3 4 5 6 0 1 2 3 4 5 6

풀이

거울의 카운터는 방향 전환을 했을시 +1 해준다.
ex) y축에서 => x축으로, x축에서 => y축으로

map에는 더 적은 거울의 개수를 저장해준다.
단 같은 거울의 개수는 y축 방향의 값과 x축 방향의 값을 따로 처리해준다.
같은 값이라도 더 적은 거울의 개수로 업데이트해 줄 수 있기 때문이다.
ex)
4 5
C..
...
...*
*.**
...C

답: 2
=> 길이 하나고 이전 노드의 방향이 여러개인 경우

이 포인트만 알면 올바른 값을 출력할 수 있다.

소스 코드

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

class Node {
    int x,y,cm,dir;
    //dir => 초기 0, x축 1, y축 2
    Node(int x, int y, int cm, int dir) {
        this.x = x;
        this.y = y;
        this.cm = cm;
        this.dir = dir;
    }
}

class Coordinate {
    int x,y;
    Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class MapInfo {
    int v;
    boolean col,row;
    MapInfo(int v, boolean col, boolean row) {
        this.v = v;
        this.col = col;
        this.row = row;
    }
}

public class Main {
    static final int dx[] = {0,0,-1,1}; // ind 0,1 => y축 움직임, ind 1,2 => x축 움직임
    static final int dy[] = {-1,1,0,0};
    static final int INFINITY = Integer.MAX_VALUE;
    static MapInfo map[][];
    static Coordinate end;
    static Node start;
    static int W,H;
    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 MapInfo[H][W];
      for(int i=0; i<H; i++) {
          String s = br.readLine();
          for(int j=0; j<W; j++) {
              if(s.charAt(j) == '*') {
                  map[i][j] = new MapInfo(-2,false,false); //벽은 -2로 표현
              } else if(s.charAt(j) == 'C') {
                  if(start == null) {
                      map[i][j] = new MapInfo(-2,false,false);
                      start = new Node(j,i,0,0);
                  } else {
                      map[i][j] = new MapInfo(INFINITY,false,false);
                      end = new Coordinate(j,i);
                  }
              } else {
                  map[i][j] = new MapInfo(INFINITY,false,false);
              }
          }
      }
      BFS();
      System.out.println(map[end.y][end.x].v);
    }
    
    static void BFS() {
        Queue<Node> que = new LinkedList<>();
        que.add(start);
        while(!que.isEmpty()) {
            Node n = que.poll();
            for(int i=0; i<dx.length; i++) {
                int nx = n.x + dx[i];
                int ny = n.y + dy[i];
                if((nx>=0 && nx<=W-1) && (ny>=0 && ny<=H-1)) {
                    if(map[ny][nx].v != -2) {
                        //벽이 아니라면
                        if(i==0 || i==1) {
                            //y축 움직임
                            if(n.dir == 1) {
                                if(map[ny][nx].v > n.cm+1) {
                                    map[ny][nx].v = n.cm+1;
                                    map[ny][nx].col = true;
                                    que.add(new Node(nx,ny,n.cm+1,2));
                                } else if(map[ny][nx].v == n.cm+1 && !map[ny][nx].col) {
                                    map[ny][nx].col = true;
                                    que.add(new Node(nx,ny,n.cm+1,2));
                                }
                            } else {
                                if(map[ny][nx].v > n.cm) {
                                    map[ny][nx].v = n.cm;
                                    map[ny][nx].col = true;
                                    que.add(new Node(nx,ny,n.cm,2));
                                } else if(map[ny][nx].v == n.cm && !map[ny][nx].col) {
                                    map[ny][nx].col = true;
                                    que.add(new Node(nx,ny,n.cm,2));
                                }
                            } 
                        } else {
                            //x축 움직임
                            if(n.dir == 2) {
                                if(map[ny][nx].v > n.cm+1) {
                                    map[ny][nx].v = n.cm+1;
                                    map[ny][nx].row = true;
                                    que.add(new Node(nx,ny,n.cm+1,1));
                                } else if(map[ny][nx].v == n.cm+1 && !map[ny][nx].row) {
                                    map[ny][nx].row = true;
                                    que.add(new Node(nx,ny,n.cm+1,1));
                                }
                                
                            } else {
                                if(map[ny][nx].v > n.cm) {
                                    map[ny][nx].v = n.cm;
                                    map[ny][nx].row = true;
                                    que.add(new Node(nx,ny,n.cm,1));
                                } else if(map[ny][nx].v == n.cm && !map[ny][nx].row) {
                                    map[ny][nx].row = true;
                                    que.add(new Node(nx,ny,n.cm,1));
                                }
                            } 
                        }
                    }
                }
            }
        }
    }
}