백준C# - 1260 +) 풀이

DFS와 BFS를 구현하는 문제이다.

 

1. 초기 설정

01 graph와 visited 변수 설정

graph는 그래프를 표현하기 위한 인접리스트이고 vistied는 정점의 방문 여부를 나타내는 배열이다.

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

---

02 입력 받기

int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
int N = input[0]; // 정점
int M = input[1]; // 간선
int V = input[2]; // 탐색을 시작할 정점의 번호

---

03 그래프 초기화

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

 

만약 그래프를 초기화 안하면 어떻게 되나요?

그래프를 초기화하는 이유는 각 정점에 대한 빈 리스트가 생성되고 나중에 간선 정보를 추가할 수 있게 된다.

만약 초기화를 안하는 경우 graph[i]는 null값을 가지고 있게 된다. null값일때 요소를 추가하려고 하면 NullReferenceException이 발생한다.

초기화 안하는 경우 :graph[1] = null, graph[2] = null, ...
초기화 하는 경우 : graph[1] = [], graph[2] = [], ...

---

04 간선 정보 입력

for (int i = 0; i < M; i++)
{
    int[] edge = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    int u = edge[0];
    int v = edge[1];

    graph[u].Add(v);
    graph[v].Add(u); // 양방향 간선이므로 반대 방향도 추가
}

---

05 오름차순으로 간선 정리

문제에서 정점이 낮은 순서대로 방문한다고 하였으므로 오름차순으로 간선을 정리한다.

for (int i = 1; i <= N; i++)
{
    graph[i].Sort();
    // Console.WriteLine($"graph[{i}] {string.Join(" ", graph[i])}");
}

---

2. DFS

01 DFS알고리즘

시작 노드에서 출발하여 한 경로를 따라 최대한 깊이 들어가며 탐색하는 알고리즘이다. 스택과 재귀로 구현된다.

C# - DFS(깊이우선탐색)개념 및 코드 구현

---

02 DFS 코드

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

    foreach(int next in graph[now])
    {
        if (visited[next])
            continue;
        DFS(next);
    }
}

실행 과정

1) 현재 정점 now를 방문했다고 표시하고 해당 정점을 출력한다. 

2) 해당 정점의 이웃 정점들을 가져온 후 순차적으로 순회하며 방문하지 않은 이웃 정점이 있다면 해당 이웃 정점에 대해 DFS함수를 재귀적으로 호출한다.

---

3. BFS

01 BFS 알고리즘

시작 노드에서부터 인접한 노드들을 먼저 탐색하는 알고리즘이다. 큐를 사용해서 많이 구현된다.

C# - BFS(너비우선탐색)개념 및 코드 구현

---

02 BFS 코드

public static void BFS(int start)
{
    Queue<int> queue = new Queue<int>();
    queue.Enqueue(start);
    visited[start] = true;
    while (queue.Count > 0)
    {
        int now = queue.Dequeue();
        Console.WriteLine(now + " ");

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

 

실행 과정

1) 시작 정점 추가한다음 방문했다고 표시

2) 큐에 현재 정점 추출

3) 현재 정점에서 방문하지 않은 이웃 정점 큐에 추가 및 방문했다고 표시

4) 2 - 3 번 반복 큐가 비면 반복문 종료

---

코드 전문

using System;
using System.Collections.Generic;

namespace baek2
{

   class Program 
   {
        static bool[] visited;
        static List<int>[] graph;
        public static void DFS(int now)
        {
            Console.Write(now + " ");
            visited[now] = true;

            foreach(int next in graph[now])
            {
                if (visited[next])
                    continue;
                DFS(next);
            }
        }

        public static void BFS(int start)
        {
            Queue<int> queue = new Queue<int>();
            queue.Enqueue(start);
            visited[start] = true;
            while (queue.Count > 0)
            {
                int now = queue.Dequeue();
                Console.Write(now + " ");

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

        }
        public static void Main()
        {
            int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int N = input[0]; 
            int M = input[1]; 
            int V = input[2];
            graph = new List<int>[N + 1];
            for (int i = 1; i <= N; i++)
            {
                graph[i] = new List<int>();
            }

            for (int i = 0; i<M;i++)
            {
                int[] edge = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                int u = edge[0];
                int v = edge[1];

                graph[u].Add(v);
                graph[v].Add(u);
            }
            for (int i = 1; i <= N; i++)
            {
                graph[i].Sort();
            }
            
            visited = new bool[N + 1];
            DFS(V);
            Console.WriteLine();
            visited = new bool[N + 1];
            BFS(V);
        }
   }
}