[알고리즘 문제 풀기] 노드사이의 거리(1240)

1. 문제 풀이 아이디어

• 트리의 두 노드 간 거리 계산 문제로, BFS를 사용하여 최단 거리(가중치 합)를 구해 문제를 해결한다.

2. 나의 정답 코드

using System.Text;
using System.Collections.Generic;

StringBuilder sb = new StringBuilder("");

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    string[] split = sr.ReadLine().Split();
    int n = int.Parse(split[0]);
    int m = int.Parse(split[1]);
    int[,] ds = new int[n, n];
    List<int[]>[] list = new List<int[]>[n];
    for (int i = 0; i < n; i++)
    {
        list[i] = new List<int[]>();
    }
    for (int i = 0; i < n - 1; i++)
    {
        split = sr.ReadLine().Split();
        int a = int.Parse(split[0]) - 1;
        int b = int.Parse(split[1]) - 1;
        int d = int.Parse(split[2]);
        list[a].Add(new int[] { b, d });
        list[b].Add(new int[] { a, d });
    }
    for (int i = 0; i < m; i++)
    {
        split = sr.ReadLine().Split();
        int x = int.Parse(split[0]) - 1;
        int y = int.Parse(split[1]) - 1;
        bool[] chk = new bool[n];
        Queue<int[]> que = new Queue<int[]>();
        que.Enqueue(new int[] { x, 0 });
        chk[x] = true;
        while (que.Count > 0)
        {
            int[] cur = que.Dequeue();
            foreach (int[] next in list[cur[0]])
            {
                if (chk[next[0]]) continue;
                if (next[0] == y)
                {
                    sb.AppendLine((cur[1] + next[1]).ToString());
                    que.Clear();
                    break;
                }
                chk[next[0]] = true;
                que.Enqueue(new int[] { next[0], cur[1] + next[1] });
            }
        }
    }
    sw.Write(sb);
}

3. 정리

• 트리를 인접 리스트(List<int[]>[])로 저장하여 간선 정보를 관리한다.

• BFS를 사용하여 두 노드 간 최단 거리를 탐색하며, 방문 여부를 chk 배열로 관리한다.

• Queue<int[]>를 활용하여 (현재 노드, 누적 거리) 정보를 저장하고 탐색을 진행한다.

• 목표 노드를 찾으면 누적 거리를 출력하고 탐색을 종료한다.