[백준] 1240 - 노드사이의 거리

1. 문제

1240번: 노드사이의 거리

2. 개요

N개의 노드로 이루어진 트리와 M개의 노드 쌍이 주어진다.

이 때 입력받은 순서대로 각 노드 쌍의 거리를 출력하는 문제.

3. 풀이 및 코드

3-1. 풀이

그래프를 이용해 트리를 만든다.

연결된 노드와 거리가 주어지지만, 무엇이 부모이고 자식인지 알 수 없는 경우가 있으므로 양방향으로 만들어준다.

각 노드 쌍 (s, e)에 대해 visited[e]에 값이 채워질 때까지 BFS를 진행한다.

이때 항상 visited를 초기화해주고 진행한다.

visited[e]가 채워졌다면 해당 값을 출력한다.

3-2. Python

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

graph = [[] for i in range(N + 1)]

for i in range(N-1):
    node1, node2, dist = map(int, sys.stdin.readline().split())

    graph[node1].append([node2, dist])
    graph[node2].append([node1, dist])

for i in range(M):
    visited = [0 for i in range(N + 1)]

    s, e = map(int, sys.stdin.readline().split())
    q = deque([s])

    while visited[e] == 0:
        now = q.popleft()

        for nexts in graph[now]:
            nxt = nexts[0]

            if visited[nxt] != 0:
                continue

            visited[nxt] = visited[now] + nexts[1]

            q.append(nxt)

    print(visited[e])

3-3. C#

namespace boj_1240
{
    internal class Program
    {
        static string[] input;
        static void Main(string[] args)
        {
            input = Console.ReadLine().Split();

            int N = int.Parse(input[0]);
            int M = int.Parse(input[1]);

            List<List<int[]>> graph = new List<List<int[]>>();

            for (int i = 0; i < N + 1; i++)
            {
                graph.Add(new List<int[]>());
            }

            for (int i = 0; i < N - 1; i++)
            {
                input = Console.ReadLine().Split();
                int node1 = int.Parse(input[0]);
                int node2 = int.Parse(input[1]);
                int dist = int.Parse(input[2]);

                graph[node1].Add(new int[] { node2, dist });
                graph[node2].Add(new int[] { node1, dist });
            }

            for (int i = 0; i < M; i++)
            {
                int[] visited = new int[N + 1];

                input = Console.ReadLine().Split();
                int s = int.Parse(input[0]);
                int e = int.Parse(input[1]);
                Queue<int> q = new Queue<int>();
                q.Enqueue(s);

                while (visited[e] == 0)
                {
                    int now = q.Dequeue();

                    foreach (int[] nexts in graph[now])
                    {
                        int nxt = nexts[0];

                        if (visited[nxt] != 0)
                            continue;

                        visited[nxt] = visited[now] + nexts[1];
                        q.Enqueue(nxt);
                    }
                }

                Console.WriteLine(visited[e]);
            }
        }
    }
}