[백준][C#] 1260번, DFS와 BFS

문제

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

풀이

/*
    DFS, BFS 개념 파악 문제
    양방향 확인 필요

    DFS : 깊이 우선 탐색
    - 방문한 곳을 끝까지 탐색

    BFS : 너비 우선 탐색
    - 한 Depth를 다 훑고 가는 탐색
*/

using System;

namespace Algorithm
{
    class Program
    {
        static int N, M, V;
        static bool[,] nodes; // 인접 행렬
        static bool[] visited; // 방문 여부

        // 방문 기록 초기화
        static void Reset()
        {
            for(int i = 0; i < visited.Length; i++)
            {
                visited[i] = false;
            }
        }

        // BFS에서 다음 Depth 탐색을 위한 대기열
        static Queue<int> bfsQueue = new Queue<int>();

        static void Main(string[] args)
        {
            Answer();
        }

        static void Answer ()
        {
            // 문제에서 주어지는 입력값
            int[] inputs = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            N = inputs[0];
            M = inputs[1];
            V = inputs[2];

            nodes = new bool[N+1, N+1];
            visited = new bool[N+1];

            for(int i = 0; i < M; i++)
            {
                int[] points = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                nodes[points[0], points[1]] = true;
                nodes[points[1], points[0]] = true; // 양방향 처리
            }

            // 결과 출력
            DFS(V);

            Reset();
            Console.WriteLine();

            BFS(V);
        }

        static void DFS(int v) 
        {
            visited[v] = true;
            Console.Write($"{v} ");

            for(int i = 1; i <= N; i++)
            {
                if(nodes[v, i] == true && !visited[i]) // 인접 행렬인데 방문을 안했다면 방문하러 고고
                {
                    DFS(i);
                }
            }
        }

        static void BFS(int v)
        {
            visited[v] = true;
            Console.Write($"{v} ");

            for(int i = 1; i <= N; i++)
            {
                if(nodes[v, i] == true && !visited[i])
                {
                    if(!bfsQueue.Contains(i)) // 이미 대기 중이라면 패스
                        bfsQueue.Enqueue(i);
                }
            }

            if(bfsQueue.Count > 0) // 대기가 없을 때까지 재귀
                BFS(bfsQueue.Dequeue());
        }
    }
}

Comment

- 양방향 처리 반드시 해줘야만 방문 행렬을 명확히 처리할 수 있다.

- 어렵게 생각할 것 없다.

> DFS는 깊게 파고드는 것

> BFS는 행, 열로 따지자면 한 행을 다 파악하고 가는 것 그리고 대기열(Queue)에 담아두었다가 하나씩 꺼내서 출력

- 헷갈려서 그림으로 그려가면서 확실히 이해했다.

---

https://github.com/SolHaan/algorithm_study