백준 20040 C++

백준 20040Permalink

일반적인 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>


using namespace std;
int N, M;
int node[500001];
int find_root(int a) {
	if (node[a] == -1) return a;
	return node[a] = find_root(node[a]);
}

void group(int a, int b) {
	a = find_root(a);
	b = find_root(b);

	if (a == b)return;
	else {
		if (a < b)node[b] = a;
		else node[a] = b;
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int x = 0; x < N; x++) {
		node[x] = -1;
	}
	for (int x = 0; x < M; x++) {
		int i, j;
		cin >> i >> j;
		if (find_root(i) == find_root(j)) {
			cout << x + 1;
			return 0;
		}
		group(i, j);
	}
	cout << 0;
	return 0;
}

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