[백준 / C++] 2644번: 촌수계산 (BFS 풀이)

https://www.acmicpc.net/problem/2644

2644번: 촌수계산

 

난이도: solved.ac 실버 2

 

 

알고리즘 분류

---

그래프 탐색(BFS, DFS)

 

접근 방법

---

input에서 두 번째 줄에 주어지는 두 사람을 각각 a, b라고 하고, a 노드부터 시작해 BFS를 이용하여 한 칸씩 이동한다

이때 각 노드의 방문 여부를 알려주는 visited에 촌수 + 1을 적는다 (Ex. a와 i가 3촌이면 visited[i] = 4)

 

코드

---

#include<iostream>
#include<queue>

using namespace std;

int relation[101][101];
int visited[101];
int n, m, a, b;
void BFS();

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> a >> b >> m;
	int x, y;
	while (m--) {
		cin >> x >> y;
		relation[x][y] = 1;
		relation[y][x] = 1;
	}
	BFS();
	if (visited[b])
		cout << visited[b] - 1;
	else
		cout << -1;
}

void BFS() {
	queue<int> myqueue;
	myqueue.push(a);
	visited[a] = 1;
	while (!myqueue.empty()) {
		int person = myqueue.front();
		myqueue.pop();
		int tmp = visited[person];
		for (int i = 1; i <= n; i++) {
			if (relation[person][i] && !visited[i]) {
				myqueue.push(i);
				visited[i] = tmp + 1;
			}
		}
	}
}