[BOJ/Gold 1] 백준 20158 사장님 달려가고 있습니다(C++)

문제 링크

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

20158번: 사장님 달려가고 있습니다

문제

알바 첫날인 정훈이는 늦잠을 잤다. 다행히도 정훈이는 달리기가 정말 빨라서 괜찮다고 생각했지만, 오늘은 공사로 인해 길을 통제하는 중이었다. 첫날부터 늦을 수 없는 정훈이는 가장 빠른 경로를 생각하며 달린다.

• 공사 지도 N x N가 있다.
• 정훈이는 0초에 맨 왼쪽 위(1, 1)에서 출발하고 맨 오른쪽 아래(N, N)에 도착해야 한다.
• 달리는 방향은 상,하,좌,우로 달릴 수 있다.
• 매초 1칸을 갈 수 있고 전과 같은 방향으로 달린다면 가속도가 붙어 1초 안에 전보다 1칸을 더 갈 수 있다. (전에 오른쪽으로 1칸을 갔다면 오른쪽으로 2칸을 1초에 갈 수 있다.)
• 가속도를 주체할 수 없으므로 방향전환을 해야만 다시 1초에 1칸을 갈 수 있다.
• 정훈이는 현재 위치에서 달려갈 때 1초 후 지도 밖에 서 있다면 갈 수 없다고 판단한다.

공사로 인해 통제하는 구역은 N x N 지도에 통제 시작시각이 초 단위로 주어지며 통제를 시작하기 전까지만 그 구역을 들어갈 수 있다. 통제 시작시각과 그 구역에 도착시각이 같은 시간일 경우에는 구역에 들어갈 수 없다.

입력

정수 N (1 ≤ N ≤ 100)이 주어진다.

둘째 줄부터 N개의 줄에 공사 지도의 정보가 주어진다. 지도에는 각 구역 통제 시작 시각 X (0 ≤ X ≤ 100)이 정수로 주어진다. X가 0이라면 통제를 하지 않는다.

출력

정훈이가 (N, N)에 도착할 수 있는 최소 시간을 출력한다.

(N, N)에 도착할 수 없다면 "Fired"를 출력한다.

예제 입력 1

5
0 0 0 2 0
0 1 0 0 0
0 0 0 3 0
5 0 0 0 0
0 0 6 0 0

예제 출력 1

6

예제 입력 2

2
0 1
1 1

예제 출력 2

Fired

예제 입력 3

4
0 0 2 0
1 1 1 0
1 1 1 0
1 1 1 0

예제 출력 3

4

(1,1)에서 (1,2)로 이동한다. 다시 한 번 오른쪽으로 이동할 때 (1,2)에서 (1,4)로 1초안에 달려갈 수 있다.

(1,3)에서 통제 시작 시간이 2초지만 현재 2초가 되지 않았기 때문에 이동할 수 있고 (1,4)에서 2초가 되는데 통제하지 않는 구역이라 이동할 수 있다.

0초 (1,1) -> 1초 (1,2) -> 2초 (1,3), (1,4) -> 3초 (2,4) -> 4초 (3,4), (4,4) 경로로 4초 만에 도착할 수 있다.

알고리즘 분류

• 그래프 탐색

풀이

방문 표시를 3차원 배열로 하고 풀었으나 계속 틀려서 이 형님이 쓰신 글을 참고하였다.

[BOJ 20158, Python 3] 사장님 달려가고 있습니다

방문 표시를 4차원 배열(visited[A][B][C][D], A, B는 좌표, C는 방향, D는 가속도)로 다시 하고 풀었다.

그리고 큐에 담을 정보(좌표, 방향, 가속도, 시간) 중 시간을 구조체에서 빼고 4차원 배열로 선언하여 풀었는데, 다시 구조체에 넣고 풀 수 있을 것 같은데 자고 일어나서 다시 해봐야겠다.

코드

#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 101
#define LL long long
#define INF 2e9

using namespace std;
struct INFO {
	int Y, X, Dir, Len;
};

int N;
int MAP[MAX][MAX];
int Len[MAX][MAX][4][MAX];
bool visited[MAX][MAX][4][MAX];
int moveY[4] = { -1,0,1,0 };
int moveX[4] = { 0,-1,0,1 };
int answer = INF;

void init() {
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			for (int k = 0; k < 4; k++) {
				for (int l = 0; l < MAX; l++) {
					Len[i][j][k][l] = -1;
				}
			}
		}
	}
	Len[1][1][0][0] = 0;
	Len[1][1][1][0] = 0;
	Len[1][1][2][0] = 0;
	Len[1][1][3][0] = 0;
}

void BFS() {
	queue<INFO> Q;
	INFO Info = { 1,1,2,0 };
	Q.push(Info);
	Info = { 1,1,3,0 };
	Q.push(Info);

	while (!Q.empty()) {
		INFO CurInfo = Q.front();
		Q.pop();
		visited[CurInfo.Y][CurInfo.X][CurInfo.Dir][CurInfo.Len] = false;

		if ((CurInfo.Y == N) && (CurInfo.X == N)) {
			answer = min(answer, Len[CurInfo.Y][CurInfo.X][CurInfo.Dir][CurInfo.Len]);
			return;
		}

		for (int i = 0; i < 4; i++) {
			int nextY = CurInfo.Y;
			int nextX = CurInfo.X;
			if (CurInfo.Dir == i) { // 방향을 틀지 않으면 가속도가 붙는다.
				bool Flag = true; // Flag가 true라면 가속도가 붙은 채 움직일 수 있다.
				for (int j = 1; j <= (CurInfo.Len + 1); j++) {
					nextY = CurInfo.Y + (moveY[CurInfo.Dir] * j);
					nextX = CurInfo.X + (moveX[CurInfo.Dir] * j);
					if ((nextY < 1) || (nextY > N) || (nextX < 1) || (nextX > N) 
						|| !((MAP[nextY][nextX] == 0) || (Len[CurInfo.Y][CurInfo.X][CurInfo.Dir][CurInfo.Len] <= MAP[nextY][nextX]))) {
						// 가속도가 붙어 달리는 도중 격자 밖을 벗어난 경우
						Flag = false;
						break;
					}
				}
				if (Flag) {
					if (((MAP[nextY][nextX] == 0) || (Len[CurInfo.Y][CurInfo.X][CurInfo.Dir][CurInfo.Len] + 1 < MAP[nextY][nextX])) 
						&& (Len[nextY][nextX][CurInfo.Dir][CurInfo.Len + 1] == -1) && (!visited[nextY][nextX][CurInfo.Dir][CurInfo.Len + 1])) {
						visited[nextY][nextX][CurInfo.Dir][CurInfo.Len + 1] = true;
						Len[nextY][nextX][CurInfo.Dir][CurInfo.Len + 1] = Len[CurInfo.Y][CurInfo.X][CurInfo.Dir][CurInfo.Len] + 1;
						INFO newInfo = { nextY,nextX,CurInfo.Dir,CurInfo.Len + 1 };
						Q.push(newInfo);
					}
				}
			}
			else { // 방향을 틀었을 경우
				nextY = CurInfo.Y + moveY[i];
				nextX = CurInfo.X + moveX[i];
				if ((nextY >= 1) && (nextY <= N) && (nextX >= 1) && (nextX <= N) && (!visited[nextY][nextX][CurInfo.Dir][CurInfo.Len + 1])
					&& (Len[nextY][nextX][i][1] == -1) 
					&& ((MAP[nextY][nextX] == 0) || (Len[CurInfo.Y][CurInfo.X][CurInfo.Dir][CurInfo.Len] + 1 < MAP[nextY][nextX]))) {
					visited[nextY][nextX][i][1] = true;
					Len[nextY][nextX][i][1] = Len[CurInfo.Y][CurInfo.X][CurInfo.Dir][CurInfo.Len] + 1;
					INFO newInfo = { nextY,nextX,i,1 };
					Q.push(newInfo);
				}
			}
		}
	};
}

int main() {
	FIRST
	init();
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> MAP[i][j];
		}
	}
	BFS();
	if (answer == INF) {
		cout << "Fired" << "\n";
	}
	else {
		cout << answer << "\n";
	}

	return 0;
}