[BOJ] 백준 6097 레이저통신 (JAVA/자바)

레이저 통신 - 골드3

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

15648

2941

2045

26.394%

문제

크기가 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

---

풀이 

내가 좋아하는 bfs...

탐색하면서 레이저가 지나간 직선 방향 개수를 visit 배열에 저장.

처음 시작에 visit = 1을 해놨기 때문에 -1

거울 개수는 직선 개수 -1 이므로 -1 해서 -2를 한 값이 정답.

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

public class BOJ_6087_레이저통신 {
	static class Point {
		int i, j;

		Point(int i, int j) {
			this.i = i;
			this.j = j;
		}
	}

	static int H, W, visit[][];
	static char[][] map;
	static int[] di = { 1, -1, 0, 0 };
	static int[] dj = { 0, 0, 1, -1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int si = 0, sj = 0, gi = 0, gj = 0;
		W = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());
		map = new char[H][W];
		visit = new int[H][W];
		int temp = 0;
		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 (temp == 0) {
						si = i;
						sj = j;
						temp++;
					} else {
						gi = i;
						gj = j;
					}
				}
			}
		}

		bfs(si, sj, gi, gj);
//		for(int i=0; i<H; i++) {
//			for(int j=0; j<W; j++) {
//				System.out.print(visit[i][j]);
//			}
//			System.out.println();
//		}
		System.out.print(visit[gi][gj]-2);
	}

	public static void bfs(int si, int sj, int gi, int gj) {
		Queue<Point> Q = new LinkedList<>();
		Q.add(new Point(si, sj));
		visit[si][sj] = 1;

		while (!Q.isEmpty()) {
			Point cur = Q.poll();
			if(cur.i==gi && cur.j==gj) return;
			for (int d = 0; d < 4; d++) {
				int ni = cur.i + di[d];
				int nj = cur.j + dj[d];
				while (ni >= 0 && nj >= 0 && ni < H && nj < W && map[ni][nj] != '*') {
					if (visit[ni][nj] != 0) {
						ni += di[d];
						nj += dj[d];
						continue;
					}
					visit[ni][nj] = visit[cur.i][cur.j] + 1;
					Q.add(new Point(ni, nj));
					ni += di[d];
					nj += dj[d];
				}
			}
		}
	}
}