[백준] 2151 - 거울 설치

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

2151번: 거울 설치

 

문제를 잘 이해하지 못해 애먹었던 문제이다.

처음에는 문이 가장자리에만 존재하는 줄 알았고, 그다음에는 양면거울이란 게 뭘 의미하는지 몰랐다.

 

일단 문제 풀이는 다음과 같다.

문제의 조건에서 항상 문끼리는 빛이 서로 도달할 수 있다고 했으므로, 아무 문에서 출발해 bfs를 수행한다.

여기서 주의해야 할 점은 방문 배열의 정의이다.

 

단순히 x, y 좌표만 저장하게 되면 어떤 방향으로 빛이 왔는지 몰라서 다음 탐색 시에 더 이상 진행할 수 없게 된다.

따라서 visit[i][j][k] = k방향으로 i행, j열에 도착했을 때 설치한 최소 거울 개수로 정의하였다.

 

그런데 여기서 주의할 점이 하나 더 있다.

보통 가중치가 없는 bfs에서는 방문 순서가 항상 최단 거리이다. 그래서 한 번 방문한 곳은 다시 방문하지 않아도 된다.

하지만 이 문제는 최단 거리를 구하는 것이 아니라 해당 좌표로 이동할 때 설치한 최소 거울의 개수를 구하는 것이므로 더 적은 개수의 거울로 해당 좌표를 방문할 수 있을 때, 갱신할 필요가 있다.

 

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

char map[50][50];
int visit[50][50][4], n;

int x[4] = { 0,1,0,-1 };
int y[4] = { 1,0,-1,0 };

int main() {

	cin >> n;

	int sx = -1, sy, dx, dy;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (map[i][j] == '#') {
				if (sx == -1) {
					sx = i; sy = j;
				}
				else {
					dx = i; dy = j;
				}
			}
			visit[i][j][0] = visit[i][j][1] = visit[i][j][2] = visit[i][j][3] = 2500;
		}
	}

	queue<pair<pair<int, int>, int>> q; //i, j, dir

	for (int i = 0; i <= 3; i++) {
		q.push({ {sx,sy},i });
		visit[sx][sy][i] = 0;
	}

	while (!q.empty()) {

		int a = q.front().first.first;
		int b = q.front().first.second;
		int dir = q.front().second;
		q.pop();

		int nx = a + x[dir];
		int ny = b + y[dir];

		if (nx >= 0 && nx < n && ny >= 0 && ny < n && map[nx][ny] != '*') {

			if (map[nx][ny] == '!') {
				for (int i = 1; i <= 3; i += 2) {
					if (visit[nx][ny][(dir + i) % 4] > visit[a][b][dir] + 1) {
						visit[nx][ny][(dir + i) % 4] = visit[a][b][dir] + 1;
						q.push({ {nx,ny},(dir + i) % 4 });
					}
				}
			}

			if (visit[nx][ny][dir] > visit[a][b][dir]) {
				q.push({ {nx,ny},dir });
				visit[nx][ny][dir] = visit[a][b][dir];
			}
		}
	}

	int ans = -1;
	for (int i = 0; i < 4; i++) {
		if (visit[dx][dy][i] == -1)continue;
		if (ans == -1 || visit[dx][dy][i] < ans)ans = visit[dx][dy][i];
	}
	cout << ans;
}