백준 1600 C++

백준 1600

일반적인 BFS문제이지만 보통의 문제와는 다른 점이 있다.

첫 번째로 체스말의 나이트처럼 움직일 수도 있다는 점.

두 번째로는 무조건 나이트처럼 움직이는게 아니라, 그렇게 움직일 수도 있고 일반적으로 움직일 수도 있다는 점이다.

우선 나이트처럼 움직일 수 있게 환경을 조성하기 위해서 hy[8], hx[8]을 만들어뒀다.

두 번째 부분이 꽤 걸리는데. 이걸 처리하기 위해서 visited. 즉, 방문경로를 3차원으로 만들어야한다.

만약 기존처럼 2차원으로 만들었다면 (0,0)에서 (2,1)로 움직이는게

(0,0) > (0,1) > (1,1) > (2,1)처럼 걸어서 움직이는 것과, (0,0) > (2,1)로 말처럼 이동하는 것이 동일시 되어버려 K번 있는 말처럼 움직일 수 있는 기회를 제대로 카운트하지 못해서, (H-1, W-1)이라는 도착점에 도달할 수 없게 되어버린다.

그래서 방문 여부를 3차원으로 구성해야한다.

visited[0][0][1] : 말의 이동방식을 1번 한 경우.

visited[0][0][2] : 말의 이동방식을 2번 한 경우.

이런 식으로 말의 이동방식을 한 횟수마다의 방문여부에 대한 맵을 따로따로 만들어줘야한다.

즉, BFS나 DFS에서 무언가 이동하는데에 선택할 수 있는 방식이 있다면, 그에 맞게 경우의 수를 늘려줘야한다.

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

using namespace std;
int K, W, H;
int arr[201][201];
bool visited[201][201][31];

int hy[8] = { 1,2,2,1,-1,-2,-2,-1 };
int hx[8] = { -2,-1,1,2,2,1,-1,-2 };

int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };

struct node {
	int y, x, nk, cnt;
};

bool chk(int y, int x, int k) {
	if (y >= 0 && y < H && x >= 0 && x < W) {
		if (!visited[y][x][k+1] && arr[y][x] == 0) return true;
	}
	return false;
}

int bfs() {
	queue<node> que;
	que.push({ 0,0,0,0});
	visited[0][0][0] = true;

	while (!que.empty()) {
		int y = que.front().y;
		int x = que.front().x;
		int k = que.front().nk;
		int ct = que.front().cnt;

		que.pop();

		if (y == H - 1 && x == W - 1) {
			return ct;
		}

		if (k < K) {
			for (int i = 0; i < 8; i++) {
				int ny = y + hy[i];
				int nx = x + hx[i];
				if (chk(ny, nx, k)) {
					visited[ny][nx][k+1] = true;
					que.push({ ny,nx, k + 1,ct + 1 });
				}
			}
		}
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny >= 0 && nx >= 0 && ny < H && nx < W) {
				if (arr[ny][nx] == 0 && !visited[ny][nx][k]) {
					visited[ny][nx][k] = true;
					que.push({ ny,nx,k,ct + 1 });
				}
			}
		}
	}
	return -1;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> K >> W >> H;
	for (int y = 0; y < H; y++) {
		for (int x = 0; x < W; x++) {
			cin >> arr[y][x];
		}
	}
	cout<< bfs();
	return 0;
}

BOJ 카테고리 내 다른 글 보러가기