[BOJ 2644] 촌수 계산

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

2644번: 촌수계산

---

전형적인 BFS 문제이다.

처음에 문제를 잘못 접근했다.

1부터 시작해서 target1과 target2의 촌수를 구해서 서로 더하면 된다고 생각했다.

그러나 다음 예외가 존재한다.

3
2 3
2
1 2
2 3

target1과 target2가 겹치기 때문에 값이 오류가 발생한다.

 

따라서, 시작점을 target1으로 시작해서 각 촌수를 구한 다음, target2의 촌수를 출력하면 된다.

 

 [ 코드 보기 ]

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, t1, t2, m, a, b;
int arr[101][101];
int res[101];
int diff[101];
queue<int> q;



void bfs(int x,int idx) {
	q.push(x);
	
	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		for (int i = 1; i <= n; i++) {
			
			if (arr[cur][i] == 1 && res[i]==0) {
				//cout << "cur: " << cur << endl;
				res[i] = res[cur]+1;
				diff[i]=idx;
				q.push(i);
			}
		}
	}

}

int main() {
	cin >> n;
	cin >> t1 >> t2;
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		arr[a][b] = 1;
		arr[b][a] = 1;
	}

	int idx = 0;

	bfs(t1, idx++);
	
	
	if (res[t2] == 0)
		cout << -1;
	else
		cout << res[t2];
		
	
}