취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1600번 문제인 말이 되고픈 원숭이이다.
문제는 아래 링크를 확인하자.

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

나이트의 움직임(K번 횟수제한)과 상하좌우 움직임을 이용해 BFS를 하는 문제이다.

(칸, K번 움직인 횟수)의 순서쌍을 하나의 노드로 생각해 BFS를 진행해보자.

상하좌우 움직임과 나이트 움직임은 아래 코드의 dr dc 및 kr kc와 같은 배열을 이용하면 편리하게 구현할 수 있다.

아래는 제출한 소스코드이다.

#define make_pair(x,y) MP(x,y)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int R, C, K;
int arr[200][200];
int dist[200][200][31];

int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };
int kr[8] = { 1,2,2,1,-1,-2,-2,-1 };
int kc[8] = { 2,1,-1,-2,-2,-1,1,2 };

void bfs() {
	queue<pair<pair<int, int>, int>> que;
	que.push(MP(MP(0, 0),0));
	dist[0][0][0] = 1;

	while (!que.empty()) {
		int r = que.front().first.first, c = que.front().first.second, k = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
			if (dist[rr][cc][k] || arr[rr][cc]) continue;
			dist[rr][cc][k] = dist[r][c][k] + 1;
			que.push(MP(MP(rr, cc), k));
		}
		if (k < K) {
			for (int i = 0; i < 8; i++) {
				int rr = r + kr[i], cc = c + kc[i];
				if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
				if (dist[rr][cc][k + 1] || arr[rr][cc]) continue;
				dist[rr][cc][k + 1] = dist[r][c][k] + 1;
				que.push(MP(MP(rr, cc), k + 1));
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> K >> C >> R;

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cin >> arr[r][c];
		}
	}

	bfs();

	int ans = 1000000007;
	for (int k = 0; k <= K; k++) {
		if (dist[R - 1][C - 1][k]) {
			ans = min(ans, dist[R - 1][C - 1][k]);
		}
	}

	if (ans == 1000000007) cout << -1;
	else cout << ans - 1;
}