백준 2644: 촌수계산

문제 요약

여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS
• DFS

문제 풀이

BFS로 풀면 된다. 문제에서 7과 3의 관계를 알고자 한다면, 7부터 BFS하면서 레벨을 더해가고, 3에 도달했을때 최종 레벨을 출력하면 된다.

큐가 비어서 BFS가 끝났는데도 찾지 못했다면, -1을 출력한다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>

using namespace std;

bool visited[101];

int main()
{
	int n, m, temp, qsize;
	int s, e, in1, in2, res = 1;
	multimap<int, int> mm;
	queue<int> q;
	cin >> n;
	cin >> s >> e >> m;
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &in1, &in2);
		mm.insert({ in1,in2 });
		mm.insert({ in2,in1 });
	}
	q.push(s);
	visited[s] = true;
	while (!q.empty()) {
		qsize = q.size();
		for(int i = 0; i < qsize; i++) {
			temp = q.front();
			q.pop();
			auto range = mm.equal_range(temp);
			for (auto& it = range.first; it != range.second; it++) {
				if (!visited[it->second]) {
					if (it->second == e) {
						printf("%d", res);
						return 0;
					}
					visited[it->second] = true;
					q.push(it->second);
				}
			}
		}
		res++;
	}
	printf("-1");
	return 0;
}