백준 2151 거울 설치 C++

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

2151번: 거울 설치

거울을 설치하여 문 2개를 이을 때 최소 거울 개수를 구하는 문제입니다.

 

처음에 거울 설치 가능 위치에 따라 해당 경로의 방문 여부를 따로 판단하기에는 (bfs 돌면서 visited 배열 초기화 후 재계산 or 큐에 visited 배열 넣기) 너무 사이즈가 클 거 같아서 우선순위 큐를 이용해 풀어보려했습니다.

하지만 반례가 있었기에 (거울 위치가 계속 돌 수 있음, 그럼 결국 visited 배열 없이 가는 것이므로 뱅글뱅글 도는 거울 위치면 그 위치들이 계속 큐에 들어감) 다른 방법으로 풀었습니다.

 

아이디어 : bfs로 돌면서 빛이 들어오는 방향에 따라 최소 설치 거울 개수가 갱신될 때만 큐에 넣자

cnt[y][x][dir] 이 y,x 위치에서 dir 방향으로 빛이 들어올 때 최소 거울 설치 개수입니다.

처음에는 모두 inf로 초기화 후, 출입문부터 거울 설치를 진행하면 됩니다. 이 때 거울이 2가지 갈래로 나뉠 수 있으므로 경우를 잘 나누어주면 됩니다. 

 

코드는 다음과 같습니다.

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

int n;
char house[51][51];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 }; // dir 0,1,2,3 : 상하좌우
pair<int, int>door1 = { -1,-1 }; // 입구
pair<int, int>door2 = { -1,-1 }; // 출구
int cnt[51][51][4]; // [y][x][dir]에 따른 최소 개수
int result;

#define INF 987654321

void init()
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> house[i][j];
			if (house[i][j] == '#' && door1.first == -1) {
				door1.first = i;
				door1.second = j;
			}
			else if (house[i][j] == '#' && door1.first != -1) {
				door2.first = i;
				door2.second = j;
			}

			for (int k = 0; k < 4; k++) {
				cnt[i][j][k] = INF;
			}
		}
	}
}

void bfs()
{
	// bfs 돌면서 [y][x][dir] 값이 최소 될 수 있으면 업데이트
	
	// <y, x>, dir 
	queue<pair<pair<int, int>, int>> q;

	for (int dir = 0; dir < 4; dir++) {
		int y = door1.first;
		int x = door1.second;
		q.push({ {y, x}, dir });
		cnt[y][x][dir] = 0;
	}

	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int dir = q.front().second;

		q.pop();

		int ny = y + dy[dir];
		int nx = x + dx[dir];

		// 맵 밖
		if (ny < 0 || ny >= n || nx < 0 || nx >= n)
			continue;

		// 벽
		if (house[ny][nx] == '*')
			continue;

		// 거울 가능 위치 
		// 더 작은 값으로 업데이트 되는 경우만 큐에 넣기
		else if (house[ny][nx] == '!') {
			// 거울 x (지나침)
			if (cnt[ny][nx][dir] > cnt[y][x][dir]) {
				cnt[ny][nx][dir] = cnt[y][x][dir];
				q.push({ {ny, nx}, dir });
			}

			// 거울로 방향 꺾이는 경우
			int ndir1, ndir2;

			if (dir == 0 || dir == 1) {
				ndir1 = 2;
				ndir2 = 3;
			}
			else if (dir == 2 || dir == 3) {
				ndir1 = 0;
				ndir2 = 1;
			}

			if (cnt[ny][nx][ndir1] > cnt[y][x][dir] + 1) {
				cnt[ny][nx][ndir1] = cnt[y][x][dir] + 1;
				q.push({ {ny, nx}, ndir1 });
			}

			if (cnt[ny][nx][ndir2] > cnt[y][x][dir] + 1) {
				cnt[ny][nx][ndir2] = cnt[y][x][dir] + 1;
				q.push({ {ny, nx}, ndir2 });
			}
		}
		// 그냥 길, 지나가는 거이므로 큐에 넣기
		else if (house[ny][nx] == '.') {
			if (cnt[ny][nx][dir] > cnt[y][x][dir]) {
				cnt[ny][nx][dir] = cnt[y][x][dir];
				q.push({ {ny, nx}, dir });
			}
		}
		// 출구 (door2), 도착지점이므로 큐에 넣을 필요 없음
		else if (house[ny][nx] == '#' && ny == door2.first && nx == door2.second) {
			if (cnt[ny][nx][dir] > cnt[y][x][dir]) {
				cnt[ny][nx][dir] = cnt[y][x][dir];
			}
		}
	}
}

void getResult()
{
	result = INF;
	for (int dir = 0; dir < 4; dir++) {
		result = min(result, cnt[door2.first][door2.second][dir]);
	}

	cout << result;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	init();
	bfs();
	getResult();
}