- 문제 ( 1240번 ) : 노드 사이의 거리
- 노드의 개수 N 이 주어지고, 노드 사이의 거리가 주어졌을 때, M 개의 두 노드 쌍을 입력받아 그 노드 사이의 거리를 출력하는 프로그램 작성.
- 알고자 하는 노드 쌍의 개수가 M 개임.
- 즉, 출력은 M 개의 거리를 구해야하는 문제.
- 입력 및 출력
[ 입력 ]
- 첫째 줄에 노드의 개수 ( 2 ≤ N ≤ 1,000 ), 거리를 알고싶은 노드 쌍의 개수 ( 1 ≤ M ≤ 1,000 ) 입력.
- 둘째 줄부터 N-1 개의 줄에 걸쳐 트리 상에 연결된 두 점과 거리를 공백을 사이에 두고 입력
-> input : node1 node2 distance- 위의 정보가 다 입력된 후, 그 다음줄부터 M 개의 줄에 걸쳐 거리를 알고싶은 노드쌍을 한 줄에 한 쌍씩 입력.
-> input : node1 node2
[ 출력 ]
- M 개의 줄에 차례대로 입력받은 두 노드 사이의 거리 출력.
- 문제 풀이
-
이번 1240번 문제의 유형은 그래프 탐색문제이다. 깊이우선탐색 ( DFS ), 너비우선탐색 ( BFS ) 두 가지 탐색 방법 모두 적용 가능한 문제이다.
이 전까지 그래프 탐색 문제는 BFS 또는 DFS 로만 해결했었는데, 이번 문제는 BFS 와 DFS 두가지 방법으로 해결해봤다.
solution1. 너비우선탐색 ( BFS )
-
BFS 로 해결하는 방법은 간단하다. M 줄에 걸쳐서 한 쌍의 노드를 입력받을 때 앞에 입력받은 node1 에 대해서 node2 에 도달할 때까지 탐색을 진행하고, node2 에 도달했다면 탐색하면서 누적해왔던 distance 를 return 하도록 구현하면 된다.
- BFS 함수는 return type 이 int 인 함수로 선언했다. BFS 탐색이 끝났을 때 즉, 우리가 원하는 종료조건을 만족시켰을 때의 distance 를 반환해주고자 int type 으로 선언해주었다.
- BFS 함수의 인자로는 탐색을 시작하고자하는 node, 목적지 node 총 두개의 인자를 받는다.
- BFS 함수는 return type 이 int 인 함수로 선언했다. BFS 탐색이 끝났을 때 즉, 우리가 원하는 종료조건을 만족시켰을 때의 distance 를 반환해주고자 int type 으로 선언해주었다.
-
BFS 는 queue 라는 자료구조를 사용하기 때문에 queue 를 하나 선언한 후 그 queue 에 탐색할 원소들을 넣은 후, queue 에 있는 원소들을 하나씩 빼면서 방문하지 않은 노드라면 방문하는 방식으로 진행된다.
- 이 때 queue 에 저장되는 원소들은 현재 노드와 연결되어있는 next_node 와 ( 현재 노드까지의 distance + 현재 노드에서 next_node 까지의 거리를 더한 distance ) 즉, 탐색을 시작한 첫번째 노드에서부터 next_node 까지 떨어진 거리를 함께 queue 에 저장해준다.
-
이렇게 넘겨받은 distance 인자를 종료조건인 ( current_node == destination_node ) 를 만족하는 상황에서 반환해주면 BFS 로 탐색해 문제 해결 완료!
Solution2. 깊이우선탐색 ( DFS )
-
DFS 도 BFS 와 마찬가지로 해결하는 방법은 간단하다. 하지만 깊이우선탐색은 하나의 경로를 끝까지 탐색해가는 방법이므로 back tracking 방식도 섞어 해결이 가능하다.
-
DFS 탐색은 재귀로 해결을 할 수 있는데, DFS 함수를 계속 부르기 때문에 DFS 함수의 인자로 필요한 정보들을 모두 전달해주어야한다.
그렇기 때문에 DFS 함수의 type 은 void 즉, 결과를 저장할 변수에 값을 저장하도록 하여 해결했고, 인자로는 BFS 보다 한개 더 많은 3개의 인자를 넘겨받도록 선언해주었다.
- DFS 함수의 인자로는 탐색을 시작할 노드, 탐색을 끝낼 목적지 노드 뿐만 아니라 탐색을 처음 시작한 노드로부터 현재 current_node ( 첫번째 인자 ) 까지의 거리정보까지 함께 넘겨준다.
-
그 후 탐색을 시작하는데 너무 깊게 들어가서 overflow 가 발생하는 것을 방지하고자 back tracking 개념을 함께 사용한다.
- 막히면 즉, 탐색을 하다가 종료조건을 만나게 되면 이전 노드로 돌아가 다른 경로를 찾아 탐색한다.
- 그렇기 때문에 DFS 함수가 불리기 전에 방문 여부를 true 로 바꾼 후, DFS 함수가 종료가 되어 다시 실행되던 flow 로 돌아왔을 때 방문 여부를 false 로 바꿔 다른 경로에 대해 탐색을 진행한다.
-
재귀적으로 트리를 탐색할 때 DFS 인자에는 다음에 탐색할 node, 내가 가고자하는 목적지 node, BFS 에서처럼 처음 node 로 부터 현재 node 까지의 distance 를 함께 넘겨준다.
-
그 후 우리가 원하는 종료조건인 ( current_node == destination node ) 라면 결과를 저장할 변수에 현재 가지고 있는 distance 를 저장 후 함수를 종료한다.
-
그 후 distance 가 저장된 변수의 값을 출력하면 문제 해결!
- 첫번째 제출이 DFS 탐색으로 해결한 결과 ( 위에 있는 결과 )
- 두번째 제출이 BFS 탐색으로 해결한 결과 ( 아래에 있는 결과 )
- 최종 코드
#include <iostream>
#include <vector>
#include <queue>
#define N_MAX 1001
using namespace std;
// 그래프 선언 (연결된 node 와 그 노드까지 가는 거리가 튜플로 저장)
vector< pair<int, int> > graph[N_MAX];
// 방문 확인 배열 선언
bool is_visit[N_MAX];
// 방문 배열 false 로 초기화
void init_is_visit () {
for(int i = 0; i < N_MAX; i++) {
is_visit[i] = false;
}
}
// 결과 저장 변수 선언
int answer = 0;
// DFS 탐색
void DFS(int current_node, int dest_node, int distance) {
// 종료조건 : current_node 와 dest_node 가 일치하면 도달했으므로 종료
if(current_node == dest_node) {
answer = distance;
return;
}
// 종료조건이 아니라면
for(int i = 0; i < graph[current_node].size(); i++) {
int n_node = graph[current_node][i].first;
int n_dist = graph[current_node][i].second;
// next_node 를 방문하지 않았다면 방문
if(is_visit[n_node] == false) {
is_visit[n_node] = true;
DFS(n_node, dest_node, (distance + n_dist));
// 끝까지 탐색했지만 n2 에 도달하지 못했다면 돌아와서 다시 탐색해야하므로 방문 여부 다시 false 로
is_visit[n_node] = false;
}
}
}
// BFS 탐색
int BFS(int current_node, int dest_node) {
// 탐색할 queue 선언 (first element: current_node, second element: 처음 BFS 가 불렸을때의 node 에서부터 떨어진 distance)
queue< pair<int, int> > q;
// current_node 방문 여부 update 후 q에 넣고 탐색 시작
is_visit[current_node] = true;
q.push(make_pair(current_node, 0));
// BFS 탐색 시작
while(!q.empty()) {
int c_node = q.front().first;
int c_dist = q.front().second;
q.pop();
// 종료조건: c_node 와 dest_node 가 일치하면 도달했으므로 종료
if(c_node == dest_node) {
return c_dist;
}
for(int i = 0; i < graph[c_node].size(); i++) {
int n_node = graph[c_node][i].first;
int n_dist = graph[c_node][i].second;
// next_node 를 방문하지 않았다면 방문하기 위해 queue 에 push
if(is_visit[n_node] == false) {
is_visit[n_node] = true;
q.push(make_pair(n_node, (c_dist+n_dist)));
}
}
}
return -1;
}
int main() {
// 노드의 개수 N, 거리를 알고싶은 노드 쌍의 개수 M 입력
int N = 0, M = 0;
cin >> N >> M;
// N-1 개의 줄에 트리 상에 연결된 두 점과 거리 입력 (n1 n2 distance)
for(int i = 0; i < N-1; i++) {
int n1 = 0, n2 = 0, dist = 0;
cin >> n1 >> n2 >> dist;
// graph 에 저장
graph[n1].push_back(make_pair(n2, dist));
graph[n2].push_back(make_pair(n1, dist));
}
// M 개의 줄에 걸쳐 거리를 알고싶은 노드 쌍 입력 (n1 n2)
for(int i = 0; i < M; i++) {
int n1 = 0, n2 = 0;
cin >> n1 >> n2;
// 방문한 배열 false 로 초기화
init_is_visit();
// 입력받은 n1 부터 n2 에 도달할 때까지 탐색
// DFS : n1 에 대해 방문여부 update
is_visit[n1] = true;
DFS(n1, n2, 0);
is_visit[n1] = false;
// DFS 결과 출력
cout << answer << endl;
// int result = BFS(n1, n2);
// BFS 결과 출력
// cout << result << endl;
}
return 0;
}
