반응형

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

 

1240번: 노드사이의 거리

N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 연결된 노드와 거리를 입력받고, vector<pair<int, int>> list[ 1001 ]에 저장합니다.

 

2. visited 배열을 만들어 각 노드의 방문 여부를 기록합니다.

 

3. 거리를 알고 싶은 노드를 입력 받고, 깊이 우선 탐색을 활용하여 노드 사이의 거리를 출력합니다.

 

4. visited 배열을 초기화 합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<vector>
 
using namespace std;
 
int N, M;
vector<pair<int, int>> list[1001];
int visited[1001];
int a, b;
 
void dfs(int num, int dist)
{
    if (num == b) {
        printf("%d\n", dist);
        return;
    }
    for (auto& next : list[num]) {
        if (visited[next.first] != 1) {
            visited[next.first] = 1;
            dfs(next.first, dist + next.second);
        }
    }
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N - 1; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        list[a].push_back({ b,c });
        list[b].push_back({ a,c });
    }
 
    for (int i = 0; i < M; i++) {
        fill(visited, visited + N + 1, 0);
        scanf("%d %d", &a, &b);
        visited[a] = 1;
        dfs(a, 0);
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 14950번 - 정복자 (C++)  (0) 2023.03.12
[ 백준 ] 1106번 - 호텔 (C++)  (0) 2023.03.11
[ 백준 ] 1068번 - 트리 (C++)  (0) 2023.03.09
[ 백준 ] 27009번 - Out of Hay (C++)  (0) 2023.03.08
[ 백준 ] 16202번 - MST 게임 (C++)  (0) 2023.03.07

+ Recent posts

티스토리툴바