[BOJ 20158 / C++] 사장님 달려가고 있습니다

백준 문제 링크 : 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"를 출력한다.

입출력 예시

풀이

너비우선탐색(BFS)로 도착지점까지 갈 수 있는 최소 시간을 구하는 문제입니다.
다만 신경써야 할 조건들이 좀 까다롭습니다

문제에서는 (1, 1)을 시작 지점으로, (N, N)을 끝 지점으로 하고있지만 저는 (0, 0)을 시작 지점으로 삼았습니다.


문제에서 예제 입력 3에 대해 친절한 설명도 함께 덧붙여있는데, 눈 여겨 보아야 할 점은

• 1초인 시점에서 출발하였고 -> 가속도 때문에 오른쪽으로 두 칸 갈 수 있으니 두 칸 이동하여 (0, 3)으로 이동 -> 이동이 끝난 후에 2초가 되고, (0, 2)의 통제가 시작됨.

따라서 현재 t초가 지났다고 하면, -> ((어떤 좌표의 통제 시작 시간) <= t) 인 경우에는 지나갈 수 없습니다.

bfs수행을 위해 queue에 집어넣을 정보는 다음과 같습니다 :

• 좌표 i, j
• 현재 시간 t
• 가속도 a : 동일한 방향으로 이동할 때마다 해당 방향으로 이동하는 거리가 증가
• 이전에 이동했던 방향 prevK : 이전과 같은 방향으로 향하고 있는지, 또는 방향을 전환했는지를 알고자 함

a, prevK 대신에 속도 dx dy를 구조체에 포함시키고 이동방향에 따라 변화하도록 해봤지만 복잡하고 완벽히 구현되지 않는 것 같아 바꿨습니다.

또한 해당 좌표에 방문했는지 확인하는 visited 배열은 4차원 배열로 선언하며, 좌표와 방향, 가속도를 모두 확인합니다. (현재 좌표에, 현재 방향에서 현재의 가속도로 방문한 적 있는지 확인)
방향과 가속도 또한 확인하는 것이 다음과 같은 반례에서 중요합니다 :

6
0 1 1 1 1 1
0 1 1 1 1 1
0 1 1 1 1 1
0 1 1 1 1 1
0 1 1 1 1 1
0 0 0 0 0 0

이 경우 다음과 같이 이동하게 됩니다 :
(0,0) -> (1,0) -> (3,0) -> (2,0) -> (3,0) -> (5,0) -> (5,1) -> (5,3) -> (5,2) -> (5,3) -> (5,5)
처음 (3,0)에 도달했을 때, 아래쪽으로 한번 더 가려면 지도를 벗어나게 됩니다 (3칸 이동하게 됨)
따라서 (2,0)으로 한번 물러났다가, 다시 (3,0) -> (5,0)
오른쪽으로 가는 경우 또한 이와 같은 과정이 되며, 이 경우 답은 10입니다
방향과 가속도까지 포함하여 방문여부를 확인해야 이러한 경우를 처리할 수 있습니다

다음으로 가게 될 좌표인 ni, nj에 대해, 해당 좌표까지 가는게 가능한지는 bool값을 반환하는 함수(canGO)를 두어 확인하도록 했습니다. 이 함수에서는 (ni, nj)가 지도를 벗어나는지, 또는 방문했는지의 여부와 함께, 해당 좌표까지 가는 도중 혹여 통제가 시작된 좌표가 있지는 않은지 확인합니다. 방향에 따라 조건문을 4개를 넣었는데, for문으로 한번에 작성할 수 있을 것 같지만 그러지 않은 것은 당장 이렇게 쓰는게 편해서도 있지만 그냥 실력부족입니다.

요약

전체적인 정리를 한번 하자면 다음과 같습니다.

1. 너비우선탐색으로 queue에 넣을 정보는 {좌표i,좌표j,시간t,가속도a,이전방향prevK}
2. 이전과 같은 방향으로 움직이려는 경우 (curInfo.prevK == k) 가속도만큼 더 이동
3. 해당 위치로 이동 가능한지 canGo()함수에서 확인 : 방문여부는 좌표와 방향, 가속도까지 일치하는지 확인.
4. 이동 가능하다면, 방향을 전환했는지 또는 같은 방향으로 이동하는지에 따라 가속도를 현재+1 또는 1로 하여 queue에 정보를 삽입

코드

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef struct info {
	int i, j, t, a, prevK;
}info; //좌표 i, 좌표 j, 경과시간 t, 가속도 a, 이전에 이동했던 방향 prevK 
int map[101][101];
bool visited[101][101][4][101]; //좌표, 방향, 가속도
int minT = -1;
int di[4] = {1, 0, -1, 0};
int dj[4] = {0, 1, 0, -1};

bool canGo(int ni, int nj, info curInfo, int n, int k) {
	if (ni < 0 || nj < 0 || ni >= n || nj >= n || visited[ni][nj][k][curInfo.a]) return false; //다음 위치가 지도범위를 넘어가는지 확인
	//또한, (ni, nj)로 가는 과정에서, 이미 통제가 시작된 구역이 포함되어있으면 갈 수 없음.
	if (ni - curInfo.i > 0) {
		for (int curi = curInfo.i, curj = curInfo.j; curi <= ni; curi++) {
			if (map[curi][curj] != 0 && map[curi][curj] <= curInfo.t) return false; 
		}
	}
	if (ni - curInfo.i < 0) {
		for (int curi = curInfo.i, curj = curInfo.j; curi >= ni; curi--) {
			if (map[curi][curj] != 0 && map[curi][curj] <= curInfo.t) return false; 
		}
	}
	if (nj - curInfo.j > 0) {
		for (int curi = curInfo.i, curj = curInfo.j; curj <= nj; curj++) {
			if (map[curi][curj] != 0 && map[curi][curj] <= curInfo.t) return false;
		}
	}
	if (nj - curInfo.j < 0) {
		for (int curi = curInfo.i, curj = curInfo.j; curj >= nj; curj--) {
			if (map[curi][curj] != 0 && map[curi][curj] <= curInfo.t) return false;
		}
	}
	return true;
}

void bfs(int n) {
	queue<info>q;
	q.push({0,0,0,1,-1});
	visited[0][0][1][1] = true;
	while (q.size()) {
		info curInfo = q.front();
		q.pop();
		int i = curInfo.i;
		int j = curInfo.j;
		if (i == n-1 && j == n-1) {
			if (minT == -1 || minT > curInfo.t) minT = curInfo.t;
			continue;
		}
		for(int k=0;k<4;k++) {
			int ni = i + di[k], nj = j + dj[k];
			if (curInfo.prevK == k) {
				ni = i + di[k] * (curInfo.a+1);
				nj = j + dj[k] * (curInfo.a+1);
			} //이전과 같은 방향으로 움직이려는 경우 더 간다
			if (canGo(ni, nj, curInfo, n, k)) {
				if (curInfo.prevK == -1) {
					info p = {ni, nj, curInfo.t+1, 1, k};
					q.push(p);
					visited[ni][nj][k][1] = true;
				}
				else {
					info p = {ni, nj, curInfo.t+1, 1, k};
					if (curInfo.prevK == k) {
						p.a = curInfo.a + 1;
					} //prevK와 k가 같을 경우 같은 방향으로 이동하게 된 경우임 => 가속도 증가
					q.push(p);
					visited[ni][nj][k][p.a] = true;
				}
			}
		}
	}
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) {
			cin >> map[i][j];
		}
	}
	bfs(n);
	if (minT == -1) cout << "Fired";
	else cout << minT;
}