[Algorithm][C++] BOJ 1600 말이 되고픈 원숭이

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

1600번: 말이 되고픈 원숭이

 

풀이 핵심

1. BFS 활용

2. 벽 부수기 문제와 비슷한 풀이

3. 방문 여부는 check[r 좌표][c 좌표][말 점프 횟수]

4. 말 점프 횟수가 K 이면서 dir (방향 index) 가 4 이상이면 break

5. (R - 1, C - 1) 좌표에 도달하면 거리 return, 모든 탐색을 완료해도 도착지에 다다르지 못할 경우 -1 return

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <queue>
using namespace std;

int K, R, C;

int map[200][200];
bool check[200][200][30 + 1];

struct monkey {
	int r, c, horse, dist;
};
queue<monkey> q;

int bfs() {
	monkey start = { 0,0,0,0 };
	q.push(start);
	check[start.r][start.c][start.horse] = true;

	while (!q.empty()) {
		monkey cur = q.front();
		q.pop();
		if (cur.r == R - 1 && cur.c == C - 1) return cur.dist;
		const int dr[] = { 1,-1,0,0,2,2,-2,-2,1,1,-1,-1 };
		const int dc[] = { 0,0,1,-1,1,-1,1,-1,2,-2,2,-2 };
		for (int dir = 0; dir < 12; dir++) {
			int nhorse = cur.horse;
			if (cur.horse >= K) {
				if (dir >= 4) break;
			}
			else if (dir >= 4) nhorse += 1;
			int nr = cur.r + dr[dir];
			int nc = cur.c + dc[dir];
			if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
			if (map[nr][nc] || check[nr][nc][nhorse]) continue;
			q.push({ nr,nc,nhorse, cur.dist + 1 });
			check[nr][nc][nhorse] = true;
		}
	}
	return -1;
}

int main() {
	scanf("%d %d %d", &K, &C, &R);
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	printf("%d", bfs());
	return 0;
}