[C#]백준 24444번: 알고리즘 수업 - 너비 우선 탐색 1

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

24444번: 알고리즘 수업 - 너비 우선 탐색 1

---

• 문제

---

• 문제풀이

먼저, 입력 값을 받아와서 그래프를 초기화한다. 각 정점마다 인접한 정점을 리스트에 추가한다.

그리고, 방문 여부 배열과 정점 방문 순서 배열을 초기화한다. 방문 여부 배열은 모두 false로, 정점 방문 순서 배열은 모두 0자동 설정된다.

BFS 함수를 호출합니다. BFS 함수는 Queue를 사용하며, 현재 정점을 방문하고 방문 순서를 기록한 뒤 인접한 정점들에 대해서 BFS를 순차적으로 사용한다.

마지막으로, 정점 방문 순서 배열을 출력한다. 만약 해당 정점이 시작 정점에서 방문할 수 없는 경우 0을 출력한다.

 

---

• 코드 1

namespace YONGYONG2
{
    using System;
    using System.Collections.Generic;
    using System.Text;

    public class Program
    {
        static int N;
        static bool[] BFSbool;
        static int[] BFSlist;
        static int count = 1;
        static List<int>[] graph;
        
        public static void BFS(int V)
        {
            Queue<int> queue = new Queue<int>();
            queue.Enqueue(V);
            BFSbool[V] = true;
            BFSlist[V] = count;
            count++;
            while (queue.Count != 0)
            {
                int temp = queue.Dequeue();
                foreach(int next in graph[temp])
                {
                    if (!BFSbool[next])
                    {
                        BFSbool[next] = true;
                        queue.Enqueue(next);
                        BFSlist[next] = count;
                        count++;
                    }
                   
                }
                
            }
        }
        public static void Main(string[] args)
        {
            using StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
            using StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
            string[] input = sr.ReadLine().Split(' ');
            N = int.Parse(input[0]);
            int M = int.Parse(input[1]);
            int V = int.Parse(input[2]);
            graph = new List<int>[N + 1];
            for (int i = 1; i <= N; i++)
            {
                graph[i] = new List<int>();
            }

            BFSbool = new bool[N + 1];
            for (int i = 0; i < M; i++)
            {
                string[] line = sr.ReadLine().Split();
                int a = int.Parse(line[0]);
                int b = int.Parse(line[1]);
                graph[b].Add(a);
                graph[a].Add(b);
            }
            for (int i = 1; i <= N; i++)
            {
                graph[i].Sort();
            }
            BFSlist=new int[N+1];
            BFS(V);
            for (int i = 1; i <= N; i++)
            {
               sw.WriteLine(BFSlist[i]);
            }

        }
    }

}

 

---

• 후기

처음에 방문하지 못하는곳을 0으로 만드는것이 너무 어려웠다.