오늘의 학습 키워드

• 완전탐색 - BFS

[백준] 촌수계산 - 2644

• [백준] 촌수계산 - 2644
• Silver II
• C++ 풀이
• 풀이시간: 33m

문제해설

부모와 자식 간의 관계가 주어졌을 때, 주어진 두 사람 사이의 촌수를 계산하는 문제이다.
두 사람 간의 관계가 상위-하위, 혹은 하위-상위일지는 탐색 전에는 알 수 없으며, 상대적인 거리만 계산하면 된다. 만약 두 사람이 서로 연결(connected components)되어 있지 않다면, -1을 출력한다.

접근법: BFS

서브트리 구현할 필요가 없는 이유

문제를 처음 읽었을 때 계층 구조가 눈에 띄어 서브트리를 구현해야 할지 고민했지만, 실제로는 상대적인 거리만 구하면 되므로 서브트리를 만들 필요가 없다.
이 문제는 무방향 그래프에서 최소 방문 순서를 찾는 문제이므로, 입력을 받을 때 양방향 관계로 설정해야 한다.

또한, 전체 사람의 수 n이 최대 100이므로 완전탐색이 가능하다고 판단되어 최소거리를 구하기 적절한 BFS를 선택했다.

#include <bits/stdc++.h>
#include<unordered_map>
using namespace std;

int N, M;
vector<int> family[102];
int dist[102];

int bfs(int st, int ed) {
	queue<int> Q;
	Q.push(st);
	dist[st] = 1;

	while (!Q.empty()) {
		int cur = Q.front(); Q.pop();
		if (cur == ed) {
			return dist[cur] - 1;
		}
		for (int next : family[cur]) {
			if (dist[next] > 0) continue;
			Q.push(next);
			dist[next] = dist[cur] + 1;
		}
	}
	return -1;
}

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

	int  st, ed, x, y;
	cin >> N >> st >> ed >> M;
	
	for (int i = 0; i < M; i++) {
		cin >> x >> y;
		family[x].push_back(y);
		family[y].push_back(x);
	}

	memset(dist, 0, sizeof(dist));
	int answer = bfs(ed, st);
	memset(dist, 0, sizeof(dist));
	if (answer == -1) answer = bfs(st, ed);
	cout << answer;
}

오늘의 회고

이 문제는 3년 전에도 풀이했던 문제이다. 다시 문제를 풀고 3년 전 풀이와 비교해보니 로직이 똑같았다. 일관된 접근 방식을 유지하고 있어 다행이라고 느꼈고, 다른 사람들의 풀이도 참고하여 더 효율적인 방법이 있는지 찾아보고 싶다.