[BOJ] 2644: 촌수계산 (C++)

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

2644번: 촌수계산

걸린 시간 : 24분 30초

---

기본적인 그래프 순회 문제이다.

 

그래프 문제가 직사각형으로 주어지면, 다시 말해서 정점 위주로 주어지면 바로 인접 행렬 방식으로 그래프를 구현한다. 하지만 이렇게 간선 위주로 주어진다면 인접 리스트 방식으로 구현하는 게 좋다.

다시 말해서 입력이 인접 행렬과 같이 주어지거나, V(정점 개수)가 너무 작거나, 플로이드 알고리즘을 사용할 경우 인접 행렬을 사용하면 된다.

 

촌수라는 최단 경로를 구해야 하므로 당연히 bfs를 써야 한다. 단지 연결 리스트 구현 방식에서 bfs가 익숙하지 않아서 오래 걸렸다.

또, 역시나 Off-by-one 오류때문에 10분 이상을 잡아먹었다. dist 배열의 초기화를 dist[1] ~ dist[n] 까지 해야 하는데 dist[0] ~ dist[n-1] 까지 했다. 이런 오류는 잘 보이기도 하는 오류이지만, 안 보일 때는 진짜 안 보이는 오류이기 때문에 발생하지 않도록 해야 한다. 항상 범위가 0 ~ n-1 인지 1 ~ n 인지 잘 판단하기!

 

#include <bits/stdc++.h>

using namespace std;

vector<int> graph[101];
int dist[101];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, a, b;
	cin >> n >> a >> b >> m;
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	queue<int> q;
	q.push(a);
	fill(dist+1, dist+n+1, -1);
	dist[a] = 0;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int i = 0; i < graph[cur].size(); i++) {
			int next = graph[cur][i];
			if (dist[next] == -1) {
				q.push(next);
				dist[next] = dist[cur] + 1;
				if (next == b) {
					cout << dist[next];
					return 0;
				}
			}
		}
	}
	cout << -1;
	return 0;
}