[BOJ/Gold 1] 백준 18224 미로에 갇힌 건우(C++)

문제 링크

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

18224번: 미로에 갇힌 건우

문제

평소 탱자탱자 놀던 건우가 마지막 날에 과제를 시작했다. 건우는 피곤이 몰려왔는지, 그만 잠이 들고 말았다! 그러고는 꿈을 꿨다. 그곳은 미로였는데 너무 현실성이 없었던 탓에 건우는 꿈이란 걸 알아챘다. 얼른 꿈에서 깨려고 노력했지만 깰 수 없었다. 왜냐하면 건우가 꿈에서 깨어나려면 반드시 미로를 탈출해야만 했기 때문이다. 미로의 특징은 다음과 같다.

• n×n미로이며 가장 왼쪽 위가 출발지, 가장 오른쪽 아래가 도착지이다. 출발지와 도착지에는 벽이 없음이 보장된다.
• 건우는 상하좌우로만 움직일 수 있으며, 벽을 넘는 것을 제외하면 한 번 이동할 때 벽이 없는 인접한 칸으로 이동한다.
• 초기 상태는 첫 번째 날 낮으로 시작하고, 건우가 m번 이동할 때 마다 낮에서 밤 또는 밤에서 낮으로 바뀐다.
• 밤에는 낮과 달리 추가로 벽을 넘을 수 있다. 벽을 넘을 때는 가려는 방향의 인접한 칸에 벽이 있어야 하며, 건우가 서 있을 수 있는 칸이 나올때까지 연속된 벽을 넘는다.
• 벽을 넘는 도중에 방향을 바꿀 순 없으며, 벽을 넘으면 1번 이동한 것으로 간주한다.

다음은 벽을 넘는 것에 대한 예시다. 주황색은 건우가 있는 곳 파란색은 벽이다.

위 경우는 벽을 넘을 수 있다.

위 경우처럼 벽을 넘었을 때 미로를 벗어날 경우에는 이동할 수 없다.

건우가 가장 빨리 탈출할 수 있는 날이 몇 번째 날의 낮 혹은 밤인지를 구해서 건우가 잠에서 깨도록 만들자!

입력

첫 번째 줄에 n, m이 주어진다. (1 ≤ n ≤ 500, 1 ≤ m ≤ 10)

두 번째 줄부터 n개의 각 줄에 0 또는 1이 공백을 사이에 두고 n개씩 주어진다.
이 때 0 은 벽이 없어 건우가 설 수 있는 곳, 1 은 벽이 있어 건우가 설 수 없는 곳을 의미한다.

출력

건우가 가장 빨리 탈출할 수 있는 날이 몇번째 날인지, 그리고 낮이면 "sun", 밤이면 "moon"을 공백으로 구분하여 함께 출력한다.
예를 들어, 2번째 날 밤일 경우, "2 moon" 을 출력하고, 3번째 날 낮일 경우, "3 sun" 을 출력한다. 만약 탈출할 수 없을 경우 -1을 출력한다.

예제 입력 1

5 2
0 0 0 0 0
0 0 1 0 0
0 0 1 0 0
0 0 1 0 0
0 0 0 0 0

예제 출력 1

2 sun

가장 빨리 탈출하는 경로는 (0,0)→(0,1)→(0,2)→(4,2)→(4,3)→(4,4) 이며

시간의 흐름은 (1 sun)→(1 sun)→(1 moon)→(1 moon)→(2 sun)→(2 sun) 이다.

예제 입력 2

3 1
0 1 0
1 0 0
0 0 0

예제 출력 2

-1

(0,0)에서 가만히 있으면 시간이 흐르지 않으므로 탈출할 수 없다.

알고리즘 분류

• 구현
• 그래프 탐색

풀이

길을 건널 때 사용되는 정보(좌표, 일 수, 건넌 횟수, 낮/밤)를 구조체로 선언하고 방문 표시에 쓰일 visited[A][B][C][D] 4차원 배열을 선언해준다. A, B는 좌표, C는 낮/밤, D는 낮/밤에 건넌 횟수를 의미한다.

벽이 없을 때는 그냥 건너면 되고, 벽이 있다면 밤인지 확인하고 밤이라면 벽이 없는 칸이 나올 때까지 벽을 뛰어넘는다.

목적지에 도착했을 때 현재 몇일인지, 낮인지 밤인지를 출력하고, 목적지에 도착할 수 없다면 -1을 출력한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 505
#define LL long long
#define INF 2e9

using namespace std;
struct INFO {
	int Y, X, Day, M;
	bool isSun;
};

int N, M;
int MAP[MAX][MAX];
bool visited[MAX][MAX][2][10];
int moveY[4] = { -1,0,1,0 };
int moveX[4] = { 0,-1,0,1 };
int answer = -1;
bool isSun = true;

void BFS() {
	queue<INFO> Q;
	INFO Info = { 0,0,1,M,true };
	visited[0][0][1][M] = true;
	Q.push(Info);

	while (!Q.empty()) {
		INFO CurInfo = Q.front();
		Q.pop();

		if ((CurInfo.Y == (N - 1)) && (CurInfo.X == (N - 1))) {
			answer = CurInfo.Day;
			isSun = CurInfo.isSun;
			return;
		}

		for (int i = 0; i < 4; i++) {
			int nextY = CurInfo.Y + moveY[i];
			int nextX = CurInfo.X + moveX[i];
			bool nextisSun = ((CurInfo.M > 0) ? CurInfo.isSun : !CurInfo.isSun);
			int nextM = ((CurInfo.M > 0) ? CurInfo.M - 1 : M);
			int nextDay = CurInfo.Day;
			if (!CurInfo.isSun && (CurInfo.M == 0)) {
				nextDay++;
			}
			INFO nextInfo;
			if ((nextY >= 0) && (nextY < N) && (nextX >= 0) && (nextX < N) && (!visited[nextY][nextX][nextisSun][nextM])) {
				// 벽이 없을 때
				if (MAP[nextY][nextX] == 0) {
					visited[nextY][nextX][nextisSun][nextM] = true;
					nextInfo = { nextY,nextX,nextDay,nextM,nextisSun };
					Q.push(nextInfo);
				}
				// 벽이 있을 때
				if (MAP[nextY][nextX] == 1) {
					if (!CurInfo.isSun) {
						if (i == 0) {
							for (int j = nextY; j >= 0; j--) {
								if (MAP[j][nextX] == 0) {
									nextY = j;
									visited[nextY][nextX][nextisSun][nextM] = true;
									nextInfo = { nextY,nextX,nextDay,nextM,nextisSun };
									Q.push(nextInfo);
									break;
								}
							}
						}
						else if (i == 1) {
							for (int j = nextX; j >= 0; j--) {
								if (MAP[nextY][j] == 0) {
									nextX = j;
									visited[nextY][nextX][nextisSun][nextM] = true;
									nextInfo = { nextY,nextX,nextDay,nextM,nextisSun };
									Q.push(nextInfo);
									break;
								}
							}
						}
						else if (i == 2) {
							for (int j = nextY; j < N; j++) {
								if (MAP[j][nextX] == 0) {
									nextY = j;
									visited[nextY][nextX][nextisSun][nextM] = true;
									nextInfo = { nextY,nextX,nextDay,nextM,nextisSun };
									Q.push(nextInfo);
									break;
								}
							}
						}
						else if (i == 3) {
							for (int j = nextX; j < N; j++) {
								if (MAP[nextY][j] == 0) {
									nextX = j;
									visited[nextY][nextX][nextisSun][nextM] = true;
									nextInfo = { nextY,nextX,nextDay,nextM,nextisSun };
									Q.push(nextInfo);
									break;
								}
							}
						}
					}
				}
			}
		}
	};
}

int main() {
	FIRST
	cin >> N >> M;
	M--;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> MAP[i][j];
		}
	}
	BFS();
	if (answer == -1) {
		cout << -1 << "\n";
	}
	else {
		cout << answer << " " << (isSun ? "sun" : "moon") << "\n";
	}

	return 0;
}