거울 설치 (feat. 백준, 2151번)

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

2151번: 거울 설치

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, x, y, dist[51][51][4], dx[4]{0, 1, 0, -1}, dy[4]{-1, 0, 1, 0};		// 0 ~ 3, 북동남서
	char arr[51][51];
	vector<pair<int, int>> doors;
	cin >> N;
	for (register int i = 1, j, k; i <= N; ++i)
		for (j = 1; j <= N; ++j) {
			cin >> arr[i][j];
			if (arr[i][j] == '#')
				doors.push_back(make_pair(i, j));
			for (k = 0; k < 4; ++k)
				dist[i][j][k] = static_cast<int>(1e8);
		}
	queue<tuple<int, int, int>> q;
	for (register int d = 0; d < 4; ++d) {
		q.push(make_tuple(doors[0].first, doors[0].second, d));
		dist[doors[0].first][doors[0].second][d] = -1;
	}
	while (!q.empty()) {
		auto p = q.front(); q.pop();
		register int x = std::get<0>(p), y = std::get<1>(p), d = std::get<2>(p);
		register int nx = x + dx[d], ny = y + dy[d];
		while (1) {
			if (nx < 1 || nx > N || ny < 1 || ny > N)
				break;
			if (arr[nx][ny] == '*')
				break;
			if (dist[nx][ny][d] < dist[x][y][d] + 1)		// 이미 지났고 현재가 거울 설치가 더 많으므로 종료
				break;
			dist[nx][ny][d] = dist[x][y][d] + 1;
			if (arr[nx][ny] == '!') {
				if (d == 0 || d == 2) {		// 북,남에서 들어온 빛인 경우
					dist[nx][ny][1] = dist[nx][ny][3] = dist[nx][ny][d];
					q.push(make_tuple(nx, ny, 1)), q.push(make_tuple(nx, ny, 3));
				}
				else {					// 동,서에서 들어온 빛인 경우
					dist[nx][ny][0] = dist[nx][ny][2] = dist[nx][ny][d];
					q.push(make_tuple(nx, ny, 0)), q.push(make_tuple(nx, ny, 2));
				}
			}
			nx += dx[d], ny += dy[d];
		}
	}
	cout << *min_element(dist[doors[1].first][doors[1].second], dist[doors[1].first][doors[1].second] + 4);		// 도착점 4방향중 최소값
	return 0;
}
// *&)*@*

1. 거울을 설치할 수 있는 지점 ('!') 은 문제의 조건과 같이 북or남쪽으로부터 빛이 들어오는 경우
   - 그대로 지나감
   - 동and서쪽으로 빛이 나감
   위의 두 가지의 행동을 취할 수 있습니다.
2. 그대로 지나가는 경우는 북or남으로부터 이어져오는 거울 개수를 그대로 가져갑니다. 또한 bfs를 종료하지 않고 계속 진행합니다.
3. 동and서쪽으로 빛이 나가는 경우는 북or남으로부터 이어져오는 거울 개수 + 1을 가져갑니다. 이후 bfs의 queue에 거울을 설치할 수 있는 지점 ('!')을 기록합니다. (다음 bfs에서 수행해야 하니까요.)
4. 이렇게 도착문 ('#') 까지 모든 bfs를 진행하면 도착점은 다음과 같은 결과값을 갖게 될겁니다.
   - 북쪽으로부터 빛이 들어온 경우 총 거울 개수
   - 동쪽으로부터 빛이 들어온 경우 총 거울 개수
   - 남쪽으로부터 빛이 들어온 경우 총 거울 개수
   - 서쪽으로부터 빛이 들어온 경우 총 거울 개수
   따라서 이중 최소값을 출력하면 정답이 됩니다.