[백준 2151] 거울 설치 (C++)

문제 링크: https://www.acmicpc.net/problem/2151

2151번: 거울 설치

 

1. 주의할 점

- BFS로 풀지만 어느 방향에서 왔는지 기억하지 않으면 답을 도출할 수 없다.

- 시작점을 기준으로 반대지점까지 도착하도록 설계하면 된다

- 거울을 놓을 수 있지만 놓지 않는 경우도 처리해야한다.

 

2. 구현

- 한 방향에서 시작해서 끝까지 가면 되므로, '#'중에 1개를 골라서 Queue에 넣고 해당 값을 벽인 '*'로 바꾼다.

- 어떤 방향에서 얼마만큼의 거울을 사용하고 왔는지 기억하기 위해 Check[][][] = K(단, K는 정수)을 사용했다. K만큼의 거울을 사용하여 해당 Index에 도착했다고 볼 수 있으며, Check배열의 값이 MAX가 아닐 경우, 현재 값과 비교해서 현재가 거울을 더 적게 사용하고 왔으면 Check배열을 교체하고 해당 정보는 Queue에 넣는다.

- 다음 칸이 거울일 때 거울을 설치하지 않고 그냥 가는 경우, 거울을 설치하여 양옆으로 뻗쳐가는 경우 총 3가지를 고려한다.

 

#define MAX 987654321
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int num, sx, sy;
char arr[50][50];
int check[50][50][4];
struct info {
	int x, y, dir;
};
info tmp;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> num;
	queue<info> q;
	for (int i = 0; i < num; i++)
		for (int j = 0; j < num; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == '#') {
				sx = j;
				sy = i;
			}
			for (int k = 0; k < 4; k++)
				check[i][j][k] = MAX;
		}
	tmp.x = sx;
	tmp.y = sy;
	for (int k = 0; k < 4; k++) {
		int nx = sx + dx[k];
		int ny = sy + dy[k];
		if (nx >= 0 && ny >= 0 && nx < num && ny < num && arr[ny][nx] != '*') {
			tmp.dir = k;
			q.push(tmp);
			check[sy][sx][k] = 0;
		}
	}
	arr[sy][sx] = '*';
	int result = MAX;
	while (!q.empty()) {
		int cx = q.front().x;
		int cy = q.front().y;
		int cd = q.front().dir;
		q.pop();
		if (arr[cy][cx] == '#')
			result = min(result, check[cy][cx][cd]);
		if (result <= check[cy][cx][cd]) continue;
		int nx = cx + dx[cd];
		int ny = cy + dy[cd];
		if (nx >= 0 && ny >= 0 && nx < num && ny < num && arr[ny][nx] != '*') {
			if (arr[ny][nx] == '!') {
				if (check[ny][nx][cd] > check[cy][cx][cd]) {
					check[ny][nx][cd] = check[cy][cx][cd];
					tmp.x = nx;
					tmp.y = ny;
					tmp.dir = cd;
					q.push(tmp);
				}
				int nd;
				nd = (cd + 1) % 4;
				if (nx >= 0 && ny >= 0 && nx < num && ny < num && arr[ny][nx] != '*' && check[ny][nx][nd]>check[cy][cx][cd] + 1) {		//거울 사용
					check[ny][nx][nd] = check[cy][cx][cd] + 1;
					tmp.x = nx;
					tmp.y = ny;
					tmp.dir = nd;
					q.push(tmp);
				}
				nd = (cd + 3) % 4;
				if (nx >= 0 && ny >= 0 && nx < num && ny < num && arr[ny][nx] != '*' && check[ny][nx][nd]>check[cy][cx][cd] + 1) {		//거울 사용
					check[ny][nx][nd] = check[cy][cx][cd] + 1;
					tmp.x = nx;
					tmp.y = ny;
					tmp.dir = nd;
					q.push(tmp);
				}
			}
			else if (arr[ny][nx] == '.' || arr[ny][nx] == '#') {
				if (check[ny][nx][cd] > check[cy][cx][cd]) {
					check[ny][nx][cd] = check[cy][cx][cd];
					tmp.x = nx;
					tmp.y = ny;
					tmp.dir = cd;
					q.push(tmp);
				}
			}
		}
	}
	cout << result;
	system("pause");
	return 0;
}