乗り間違い : BFS, dist[]

문제요약

정점 간의 관계가 주어질 때, x 정점에서 y 정점으로 가는 시간을 구하라.

근데, 정점에 연결된 정점이 두개 이상일 때, 항상 잘못된 정점으로 먼저 갔다가 돌아오는 실수를 한다.

 

https://paiza.jp/works/mondai/bfs_dfs_problems_advanced/bfs_dfs_problems_advanced__wrong_train/edit?language_uid=c-sharp&t=81a55f22de299c6510567717a907b554

---

난이도

B Rank

---

풀이 포인트

• BFS 기본
• 약간의 응용: 차수(정점에 연결된 간선의 개수)가 2이상일 때의 로직 추가

---

REVIEW

 

BFS 근간 코드를 아직 외우지 못했다.

1차원 탐색 문제임에도 아직 낯선 상태.

 

방문 배열 즉, True와 False값이 아닌

거리 배열 즉, -1과 양수를 기반으로 탐색해 나갈 수 있다는 거 명심.

 

---

CODE

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {

        var line = Console.ReadLine().Split();
        int n = int.Parse(line[0]);
        int x = int.Parse(line[1]) - 1;
        int y = int.Parse(line[2]) - 1;

     
        List<int>[] graph = new List<int>[n];
        int[] degree = new int[n];
        for (int i = 0; i < n; i++)
        {
            graph[i] = new List<int>();
        }


        for (int i = 0; i < n - 1; i++)
        {
            var edge = Console.ReadLine().Split();
            int a = int.Parse(edge[0]) - 1;
            int b = int.Parse(edge[1]) - 1;
            graph[a].Add(b);
            graph[b].Add(a);
            degree[a]++;
            degree[b]++;
        }


        Queue<int> queue = new Queue<int>();
        queue.Enqueue(x);
        int[] dist = new int[n];
        Array.Fill(dist, -1);
        dist[x] = 0;

        while (queue.Count > 0)
        {
            int current = queue.Dequeue();
            foreach (int next in graph[current])
            {
                if (dist[next] == -1)
                {
                    dist[next] = dist[current] + 1;
                    queue.Enqueue(next);
                }
            }
        }


        if (degree[x] < 2)
        {
            Console.WriteLine(5 * dist[y]);
        }
        else
        {
            Console.WriteLine(10 + 5 * dist[y]);
        }
    }
}