문제에서 요구하는 것은 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;
}