31. SW_Test 연습 백준 6087 레이저 통신

문제

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

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

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

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

입력

첫째 줄에 W와 H가 주어진다. (1 ≤ W, H ≤ 100)

둘째 줄부터 H개의 줄에 지도가 주어진다. 지도의 각 문자가 의미하는 것은 다음과 같다.

• .: 빈 칸
• *: 벽
• C: 레이저로 연결해야 하는 칸

'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.

출력

첫째 줄에 C를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.

 

#pragma warning (disable :4996)
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
char cMap[100][100];
int N, M;
int ans = 999999;
int vMap[100][100][2];
int dir[4][2] = { {-1,0} ,{1,0}, {0,-1}, {0,1} };
struct point {
	int y, x;
	int condir = -1;
	int move = 0;
};
queue<point> q;
void BFS() {
	while (!q.empty()) {
		int cuny = q.front().y;
		int cunx = q.front().x;
		int cundir = q.front().condir; // 0 이면 가로 방향 // 1 이면 세로방향 // -1 이면 최초
		int cunmove = q.front().move;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nextY = cuny + dir[i][0];
			int nextX = cunx + dir[i][1];
			int nextdir;
			if (nextY == cuny) {
				nextdir = 0;
			}
			else {
				nextdir = 1;
			}
			if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M || cMap[nextY][nextX] == '*') continue;
			if (vMap[nextY][nextX][nextdir] <= cunmove) continue;
			point p;
			p.y = nextY;
			p.x = nextX;
			p.condir = nextdir;
			if (cundir == -1 || nextdir == cundir) {
				p.move = cunmove;
			}
			else {
				p.move = cunmove + 1;
			}
			q.push(p);
			vMap[nextY][nextX][nextdir] = p.move;
			if (cMap[nextY][nextX] == 'C') {
				ans = min(ans, p.move);
			}
		}
	}
}
int main() {
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &M, &N);
	memset(vMap, 999999, sizeof(vMap));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1s", &cMap[i][j]);
			if (cMap[i][j] == 'C') {
				if (q.empty()) {
					point p;
					p.y = i;
					p.x = j;
					q.push(p);
					vMap[i][j][0] = 0;
					vMap[i][j][1] = 0;
				}
			}
		}
	}
	BFS();
	printf("%d", ans);
	return 0;
}