백준 1600번 - 말이 되고픈 원숭이 (C++)

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

 

bfs 문제로 1년만에 다시 풀어보았다. 흥미로운 점은 과거의 나는 k값을 주어진 개수만큼 넣어놓고 --한 반면 오늘의 나는 0으로 두고 하나씩 늘려나갔다는 것과 지금은 큐 내에서 cnt 를 늘렸는데 과거에선 dis 배열을 만들어서 거기에다가 값을 넣어놓았다. 둘 다 할 수 있는 방법이지만 왜 굳이 저렇게 했는지.. 

 

그런데 dis배열에 넣는 것이 훨씬 시간이 짧았다... 이걸로 다익스트라처럼 가지치기를 하는 것도 아니고 같은 순회를 할 탠데 왜 시간이 덜 걸리는지 모르겠다.

 

각설하고 이 문제는 말처럼 이동할 수 있는 k이동을 20번 남았을 때와 10번 남았을 때의 상황을 따로 가정하여 방문 표시를 해야한다. 때문에 3차원 visited 배열을 선언하여 순회해야한다. 

 

위 3차원 visited만 떠올리면 엄청 어려울 것은 없는 문제이다. 하지만 이것을 떠올리기가 어렵다.

 

#include <iostream>
#include <queue>
using namespace std;

const int MAX = 201;
const int KMAX = 31;

bool visited[MAX][MAX][KMAX];
int board[MAX][MAX];

int N, M, K;

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int kx[] = {-1,-2,-2,-1,1,2,1,2};
int ky[] = {2,1,-1,-2,-2,-1,2,1};

bool range(int x, int y){
	return (x < N && x > -1 && y < M && y > -1);
}

int bfs(){
	queue<pair<pair<int, int>, pair<int, int>>> q;
	q.push({{0,0}, {0, 0}});

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

		q.pop();

		if(x == N - 1 && y == M - 1){
			return cnt;
		}

		for(int i = 0; i < 4; i++){
			int nx = x + dx[i];
			int ny = y + dy[i];

			if(range(nx, ny) && !visited[nx][ny][k] && board[nx][ny] == 0){
				q.push({{nx, ny}, {k, cnt + 1}});	
				visited[nx][ny][k] = true;
			}

			if(k < K){
				for(int i = 0; i < 8; i++){
					int nx = x + kx[i];
					int ny = y + ky[i];

					if(range(nx, ny) && !visited[nx][ny][k + 1] && board[nx][ny] == 0){
						visited[nx][ny][k + 1] = true;
						q.push({{nx, ny}, {k + 1, cnt + 1}});
					}
				}
			}
		}
	}

	return -1;
}

int main(){
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> K >> M >> N;

	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			cin >> board[i][j];
		}
	}

	cout << bfs() << '\n';
}