백준 1240 C++

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

1240번: 노드사이의 거리

 

문제 정리

주어진 정보로 트리를 만들고 노드 사이의 거리를 출력하는 문제

 

생각

트리 문제가 너무 오랜만인데... dfs나 bfs 쓰면 될 것 같다

1. 그래프를 만든다

2. dfs로 노드 사이의 최단거리를 구한다

3. 출력

 

2차원 배열에 두 노드와 노드 사이의 거리를 입력받고 노드를 연결하고 (양방향) 그 후 dfs를 실행하는데 배열이 0이 아니라면 탐색을 하고 0이면 dfs를 실행한다.

 

코드

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n, m;
int graph[1001][1001];
bool visited[1001];

int dfs(int start, int end) {
    if (start == end) return 0;
    visited[start] = true;
    int ans = 987654321;
    for (int i = 0; i <= n; i++) {
        if (graph[start][i] != 0 && !visited[i]) {
            ans = min(ans, graph[start][i] + dfs(i, end));
        }
    }
    return ans;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a][b] = c;
        graph[b][a] = c;
    }
    for (int i = 0; i < m; i++) {
        memset(visited, false, sizeof(visited));
        int a, b;
        cin >> a >> b;
        cout << dfs(a, b) << endl;
    }
}

 

입력 받기

int n, m;
int graph[1001][1001];
bool visited[1001];

int main() {
    cin >> n >> m;
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a][b] = c;
        graph[b][a] = c;
    }
    for (int i = 0; i < m; i++) {
        memset(visited, false, sizeof(visited));
        int a, b;
        cin >> a >> b;
        cout << dfs(a, b) << endl;
    }
}

- 양방향 연결이니까 [a][b] = [b][a] = c

 

dfs

int dfs(int start, int end) {
    if (start == end) return 0;
    visited[start] = true;
    int ans = 987654321;
    for (int i = 0; i <= n; i++) {
        if (graph[start][i] != 0 && !visited[i]) {
            ans = min(ans, graph[start][i] + dfs(i, end));
        }
    }
    return ans;
}

- 노드의 시작점과 끝점이 같으면 거리 0을 리턴!

- visited로 방문 확인

- ans(현재까지의 최소 거리)와 다음 노드까지의 거리를 합친 값이 최소 거리가 되도록 갱신