[백준 BOJ/C++] 1240 노드사이의 거리

 

1240번: 노드사이의 거리

 

간선정보를 입력받아 그래프의 최단거리를 구하는 문제다.
아주 기본에 가까운 문제라 최단거리 알고리즘의 기본기를 연습하기 좋은 문제라고 할 수 있다.
시작점과 끝점 여러개를 입력받아 거리를 구해야한다는 점과 문제 설명이 자세하지 않다는 점 정도가 고민해봐야할 부분이다.

 

 

문제 설명이 아주 간단한데 말 그대로 주어진 그래프에서 특정 두 노드의 거리를 구해주면 된다.

두 노드 사이의 간선에 방향성이 있는지, 여러개의 간선이 같은 두 노드 사이에 존재할 수 있는지 등 일반적인 그래프 탐색 문제에서 주어지는 설명은 한마디로 압축하고있다.

 

 

트리는 두 노드 사이에 간선이 하나만 존재하며 간선에 방향이 존재하지 않는다.

또한 트리는 사이클이 없는 그래프일 뿐이므로 BFS나 DFS와 같은 그래프 탐색을 통해 거리를 구해주면 된다.

 

 

---

 

 

문제의 포인트

 

간선정보를 이용해 그래프를 표현하고 탐색하기
여러 쌍의 노드 사이 거리를 구하기

 

 

간선정보를 이용해 그래프를 표현하고 탐색하기

 

탐색 문제에서는 일반적으로 맵 형태의 2차원 배열을 이용하거나 시작점, 끝점, 가중치 형태로 간선정보를 이용해 탐색할 그래프에 대한 정보가 주어진다.

그래프 문제를 풀기 위해서는 일단 주어진 정보를 자료구조로 적절히 표현하는것이 시작이다.

 

 

본 문제에서는 시작점과 끝점, 가중치로 각 간선의 정보를 제공한다.

간선 정보를 이용해 그래프를 자료구조로 옮기는 방법에는 인접 행렬 (Adjacency Matrix)와 인접 리스트 (Adjacency List)가 있다.

 

 

각각 장단점이 있지만 메모리와 시간제한을 신경써야 하는 알고리즘 문제풀이에서는 대체로 인접 리스트가 유리한 편이다.

실제로 간선이 존재하든 안하든 모든 노드 사이를 배열로 표현하는 인접행렬은 메모리 공간도 공간이지만 탐색 시 for문을 훨씬 많이 돌수 있기 때문에 시간초과의 가능성도 있다.

따라서 노드 수의 최대 갯수 자체는 아주 크지 않아도 본 문제와 같이 여러번 탐색할 필요가 있다면 인접리스트를 이용하는 것이 좋다.

 

 

본 문제의 그래프는 트리이므로 양방향 그래프의 인접리스트 표현 방법에 따라 주어진 두 점 a와 b에 대해 a → b 와 b → a 두가지 경우 모두 인접리스트에 추가해주자.

 

 

거리를 구하기 위한 탐색은 깊이 우선 탐색 (DFS) 나 너비 우선 탐색 (BFS) 을 이용하면 된다.

트리는 사이클이 없는 그래프이기 때문에 사실 두 점 사이의 거리는 그 자체로 최단 거리가 되며 최단거리 알고리즘인 다익스트라 (Dijkstra) 문제로 볼 수도 있다.

어쨌든 그래프를 탐색하고 거리만 구할 수 있다면 어떤 방식을 이용해도 된다.

 

 

여러 쌍의 노드 사이 거리를 구하기

 

문제는 단 한 쌍의 노드들 사이의 거리를 구하는 것이 아니라는 점이다.

거리를 구하고자 하는 시작 노드와 끝 노드는 문제에서 입력으로 주어지며 고정되어있지 않은데다가 심지어 여러쌍이다.

 

 

그래프 자체가 변화하는 것은 아니기 때문에 우선 전체를 한번 탐색해 1번 노드부터 N번 노드까지 모든 노드들의 1번 노드 기준에서의 거리를 구해놓고 이를 이용해 간단하게 여러 쌍의 노드 사이 거리를 구할 수 있는 방법을 찾아봤다.

하지만 시작점이나 도착점이 바뀜에 따라 1번 노드부터의 거리와 비교해 늘어날지 줄어들지 조차도 간단한 계산으로는 확인할 방법이 없어보인다.

 

 

오히려 단순한 방식으로 접근하면 어렵지 않게 문제를 풀 수 있었다.

바로 매 입력마다 입력받은 시작점을 기준으로 다시 탐색해 거리를 구해주는 것이다.

 

 

이렇게 여러번 그래프를 탐색시켜야 할 때에는 주의해야할 부분이 있다.

시작점 기준으로 각 노드까지의 거리를 담아줄 dist 배열과 같이 탐색에 참조하기 위한 자료를 매번 초기화 해줘야 한다는 점이다.

그래프를 변화시켜 다시 탐색해야 하거나 여러개의 test case를 처리해야하는 문제에서는 탐색에 필요한 자료에 대한 초기화를 신경써줘야 한다.

 

 

그래프 탐색 또는 최단거리 문제 중 높은 난이도의 문제들에서는 이와 같이 여러번의 그래프 탐색이 필요한 문제가 많다.

플래티넘 난이도의 거의 최단 경로나 개코전쟁과 같은 문제들 처럼 최초 그래프에서 최단거리를 구하고 최단거리 경로 내에서 간선에 변화를 준 이후 다시 최단거리를 구하는 형태의 문제들이 있다.

 

 

이문제는 그래프 자체는 그대로이기 때문에 난이도는 어렵지 않지만 그와 유사하게 여러번의 그래프 탐색을 연습해볼 수 있는 문제였다.

 

 

---

 

 

전체 Code

 

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

using namespace std;
int N, M;

vector<pair<int, int>> adj[1000 + 10];
int dist[1000 + 10];

void initDist() {
	int i;

	for (i = 1; i <= N; i++) {
		dist[i] = -1;
	}
}

void BFS(int s) {
	int curr, next, i;

	queue<int> q;

	q.push(s);
	dist[s] = 0;

	while (!q.empty()) {
		curr = q.front();
		q.pop();

		for (i = 0; i < adj[curr].size(); i++){
			next = adj[curr][i].first;
			if (dist[next] > 0) continue;
			q.push(next);
			dist[next] = dist[curr] + adj[curr][i].second;
		}
	}
}

int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);

	int i, a, b, d, s, e;

	cin >> N >> M;

	for (i = 0; i < N - 1; i++) {
		cin >> a >> b >> d;
		adj[a].push_back(make_pair(b, d));
		adj[b].push_back(make_pair(a, d));
	}

	for (i = 0; i < M; i++) {
		initDist();
		cin >> s >> e;
		BFS(s);
		cout << dist[e] << "\n";
	}

	return 0;
}