[C#] 백준 1260번 문제풀이

안녕하세요.

백준 1260번 'DBF와 BFS' 문제풀이를 진행해보도록 하겠습니다.

해당 문제는 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성해야하는 문제입니다.

단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료해야하며 정점 번호는 1번부터 N번까지입니다.

 

문제풀이를 진행하기 앞서, DBF와 BFS가 무엇인지에 대해 알아보겠습니다.

DBF와 BFS란: 그래프 탐색 알고리즘. 즉, 어떤 정점에서 시작해서 그래프의 모든 정점이나 도달 가능한 정점들을 방문하는 것 입니다. 
DFS: 한 방향으로 끝까지 쭉 들어갔다가, 더 이상 갈 곳 없으면 되돌아오면서 다른 방향을 탐색하는 알고리즘.시

BFS: 시작점에서 가까운 정점부터 차례대로 탐색하는 알고리즘.

이렇게는 이해가 쉽지 않을 수 있으니 동영상 링크를 첨부해두었습니다.
https://www.youtube.com/watch?v=BsYbdUnKZ-Y&pp=ygUKQkZT7JmAIERGUw%3D%3D

이제 문제풀이를 진행해보도록 하겠습니다.

먼저, 입력으로 정점의 개수, 간선의 개수, 탐색을 시작할 정점의 개수(N, M, V)를 받아옵니다.

int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
int N = input[0];
int M = input[1];
int V = input[2];

 

다음으로, 그래프 리스트와 방문한 정점을 표시할 bool값 배열을 선언해줍니다.

배열의 길이를 N+1로 하는 이유는 정점의 번호를 1부터 매기기 때문에 0 자리를 비워두기 때문입니다.

graph = new List<int>[N + 1];
visited = new bool[N + 1];

 

첫번째 for문에서 그래프 리스트 안에 리스트를 선언해 각각 넣어줍니다.

두번째 for문에서 그래프 리스트 안에 선언된 리스트에 정점을 넣어줍니다. 이때, 양방향으로 입력된 정점을 넣어줘야 양쪽에서 접근할 수 있습니다. 예를들어, 1과 2가 있을때 1번 간선에 정점 2를 넣고 2번 간선에 정점 1을 넣어야 양쪽 간선에서 접근할 수 있습니다.

세번째 for문에서 그래프리스트속 리스트를 전부 오름차순 정렬해줍니다.

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

for (int i = 0; i < M; i++)
{
    string[] edge = Console.ReadLine().Split();
    int a = int.Parse(edge[0]);
    int b = int.Parse(edge[1]);

    graph[a].Add(b);
    graph[b].Add(a);
}

for (int i = 0; i <= N; i++)
{
    graph[i].Sort();
}

 

이제 본격적으로 DFS와 BFS 알고리즘을 구현할 차례입니다.

먼저 DFS를 구현해보겠습니다.
DFS 메소드를 만들어주고, int값으로 노드값을 받아옵니다.

해당 노드를 값으로 받아왔다는 것은 그 노드를 방문했다는 의미이므로, 해당 노드 번호에 맞는 visited 배열 값 부분을 true로 바꿔줍니다. 그리고 나서 방문 노드를 출력해줍니다.
이제 그래프 안에 모든 리스트를 순회하며 재귀함수로 탐색을 시작합니다.

만약 방문하지 않은 노드를 발견했다면 해당 노드를 값으로 하여 다시 DFS메서드를 재귀호출합니다.
모든 노드를 탐색했다면, 메서드를 종료합니다.

void DFS(int node)
{
    visited[node] = true;
    Console.Write(node + " ");

    foreach(int next in graph[node])
    {
        if (!visited[next])
        {
            DFS(next);
        }
    }
}

 

다음으로는 BFS 알고리즘을 구현하겠습니다.
전에 구현하였던 DFS는 스택기반이지만, BFS는 큐 기반 알고리즘입니다.
BFS가 큐를 사용하는 이유는 큐가 선입선출의 구조이며, 즉 현재 노드의 모든 이웃을 전부 탐색한 후에 그 이웃들의 이웃을 나중에 탐색할 수 있기 때문입니다.

BFS도 DFS와 같이 입력값에 시작할 노드값을 받아와줍니다.

다음으로 큐를 선언해줍니다. 큐는 방문할 노드들의 순서를 기억하고, 차례대로 꺼내기 위해 사용합니다.
또한 방문한 노드를 표시하기 위한 불값배열도 선언해줍니다.

이제 큐에 시작노드를 넣고, 시작노드 방문을 true로 변경해줍니다.

while문으로 큐에 아직 방문해야할 노드가 남아있는동안 반복하도록 해줍니다.

while문 안에서, 큐의 맨 앞에있는 노드를 꺼내줍니다. 그 후에 방문한  노드를 출력해줍니다.

다음으로 current 노드에 연결된 모든 노드들을 하나씩 꺼내줍니다. 아직 방문하지 않은 노드들은 큐에 넣습니다.

이 행동을 반복하고, 더 이상 방문할 노드가 없으면 메서드를 종료합니다.

void BFS(int start)
{
    Queue<int> queue = new Queue<int>();
    bool[] visitedBfs = new bool[graph.Length];

    queue.Enqueue(start);
    visitedBfs[start] = true;

    while (queue.Count > 0)
    {
        int current = queue.Dequeue();
        Console.Write(current + " ");

        foreach(int next in graph[current])
        {
            if (!visitedBfs[next])
            {
                queue.Enqueue(next);
                visitedBfs[next] = true;
            }
        }
    }
}

 

이번 문제는 제게 많이 벅찬 문제였던 것 같았습니다. 심지어 원리를 이해하기까진 2일이 걸렸습니다 😵
GPT도움도 많이 받고, 관련 자료도 많이 찾아보았던 것 같습니다.
다음은 전체코드입니다.

전체코드

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

class Program
{
    static void Main()
    {
        int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        int N = input[0];
        int M = input[1];
        int V = input[2];

        List<int>[] graph;
        bool[] visited;

        graph = new List<int>[N + 1];
        visited = new bool[N + 1];

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

        for (int i = 0; i < M; i++)
        {
            string[] edge = Console.ReadLine().Split();
            int a = int.Parse(edge[0]);
            int b = int.Parse(edge[1]);

            graph[a].Add(b);
            graph[b].Add(a);
        }

        for (int i = 0; i <= N; i++)
        {
            graph[i].Sort();
        }

        DFS(V);
        Console.WriteLine();
        BFS(V);

        void DFS(int node)
        {
            visited[node] = true;
            Console.Write(node + " ");

            foreach(int next in graph[node])
            {
                if (!visited[next])
                {
                    DFS(next);
                }
            }
        }

        void BFS(int start)
        {
            Queue<int> queue = new Queue<int>();
            bool[] visitedBfs = new bool[graph.Length];

            queue.Enqueue(start);
            visitedBfs[start] = true;

            while (queue.Count > 0)
            {
                int current = queue.Dequeue();
                Console.Write(current + " ");

                foreach(int next in graph[current])
                {
                    if (!visitedBfs[next])
                    {
                        queue.Enqueue(next);
                        visitedBfs[next] = true;
                    }
                }
            }
        }
    }
}