BOJ 6084 - Laserphones (레이저 통신)

* BOJ 6084 - Laserphones (레이저 통신)

  [ 분류 - BFS ]

이 문제는 비슷한 문제가 있긴하다. 어떤걸 먼저 풀어도 상관은 없다.

(거울설치 - https://www.acmicpc.net/problem/2151)

 

  문제에서 요구하는 것은 C에서 C로, 레이저를 쏠 때 필요한 거울의 수다. 단 90도 로만 반사된다.

  가령 d방향으로 레이저가 진행하고 있다고 가정해보자. 그렇다면 현재 바라보는 방향을 기준으로 직진, 좌우 밖에 갈 수 없다(180를 반사, 즉 오던 방향으로 쏠 순 없음).

	↑
→	/

→	＼
	↓

→	→	→

  * 접근 방법

  1. 두 개의 C 중 하나를 Source로 두고, 4 방향으로 레이저를 쏘는 것으로 시작한다. (시작할 때는 어느 방향이라도 가능하기 때문.

  2. 막상 발사가 되면 이 레이저는 되돌아올 수 없다(Source로 돌아온다는 것은 비효율적이기 때문).

  3. 따라서 현재 지점을 (y, x)라고할 때 여기에 방향(벡터)가 들어가기 때문에 해당 방문점을 3차원 배열로 둬야한다.

  4. 마지막에 Source가 아닌 다른 C의 4 방향을 조사하여 가장 적게 사용한 거울 수를 답으로 선택한다.

- 코드

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
struct _d { int y, x, d; };
int main() {
	char board[51][51];
	int N, i, j, sy = -1, sx, ey, ex, dy[] = { 0,0,1,-1 }, dx[] = { 1,-1,0,0 }, visit[51][51][4] = {}, ty, tx;
	bool mir;
	scanf("%d\n", &N);
	for (i = 0; i < N; i++) {
		scanf("%s", board[i]);
		for (j = 0; j < N; j++) {
			if (board[i][j] == '#') {
				if (sy == -1) sy = i, sx = j;
				else ey = i, ex = j;
			}
		}
	}
	memset(visit, 0x7F, sizeof(visit));
	queue<_d> q;
	for(i=0;i<4;i++) visit[sy][sx][4] = 0;
	for (i = 0; i < 4; i++) {
		ty = sy + dy[i], tx = sx + dx[i];
		if (0 <= ty && ty < N && 0 <= tx && tx < N && board[ty][tx] != '*') {
			visit[ty][tx][i] = 0;
			q.push(_d{ ty,tx,i });
		}
	}
	while (!q.empty()) {
		_d u = q.front(); q.pop();
		if (board[u.y][u.x] == '!') {
			for (i = 0; i < 4; i++) {
				ty = u.y + dy[i], tx = u.x + dx[i];
				if (0 <= ty && ty < N && 0 <= tx && tx < N && board[ty][tx] != '*') {
					mir = (u.d != i);
					if (visit[ty][tx][i] > visit[u.y][u.x][u.d] + mir) {
						visit[ty][tx][i] = visit[u.y][u.x][u.d] + mir;
						q.push(_d{ ty,tx,i });
					}
				}
			}
		}
		else {
			ty = u.y + dy[u.d], tx = u.x + dx[u.d];
			if (0 <= ty && ty < N && 0 <= tx && tx < N && board[ty][tx] != '*') {
				if (visit[ty][tx][u.d] > visit[u.y][u.x][u.d]) {
					visit[ty][tx][u.d] = visit[u.y][u.x][u.d];
					q.push(_d{ ty,tx,u.d });
				}
			}
		}
	}
	int ans = 1e9;
	for (i = 0; i < 4; i++) ans = ans > visit[ey][ex][i] ? visit[ey][ex][i] : ans;
	printf("%d", ans);
	return 0;
}