[C++] 2644: 촌수 계산

실버 Ⅰ

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int saram1, saram2;
//일부러 양방향 그래프로 만듦
vector<int> adjList[101];//0번 안씀
bool visit[101];//0번 안씀

int bfs() {
	//뭘 넣든 상관없음
	queue<pair<int, int>> q;
	q.push({ saram1, 0 });

	while (!q.empty()) {
		int cur = q.front().first;
		int chonsoo = q.front().second;
		q.pop();

		if (cur == saram2) return chonsoo;

		for (int i = 0; i < adjList[cur].size(); i++) {
			int next = adjList[cur][i];
			if (visit[next]) continue;
			visit[next] = true;
			q.push({ next, chonsoo + 1 });
		}
	}
	return -1;
}

int main() {
	int n, m;
	scanf("%d", &n);
	scanf("%d%d", &saram1, &saram2);
	scanf("%d", &m);
	int x, y;
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &x, &y);
		adjList[x].push_back(y);
		adjList[y].push_back(x);
	}
	printf("%d", bfs());
}

 

이 문제는 별 거 없다

그 bfs에서 진짜 자주 나오는

뭉텅이들 개수 세어주는 그거다! (아래 사진)

위 그림에서 보면 (노란색, 민트색, 보라색) 이 한 세트

 

예를 들어서

그냥 아래로 쭉 뻗는 이진 트리가 있다고 치면

bfs에서 depth 세어주기? level 세어주기..?

그런거다!

 

약간 특이한점이라고 하면 부모-자식이니까 단방향 그래프 같지만

나는 bfs에서 어느 점이 부모 , 자식일지 모르니까

어느 점을 넣어도 탐색이 가능하도록 양방향 그래프로 설정해줌