[BOJ] 1260번 DFS와 BFS

문제

코드

using System;
using System.Collections.Generic;
using System.IO;
using System.IO.Pipes;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading;

namespace BOJ
{
    class Program
    {
        private static int[,] graph; //그래프 선언
        private static int n;  // 정점의 갯수를 담을 변수 선언 (메서드에서의 사용을 위해 정적 변수선언)

        static void Main(string[] args)
        {
            //정점의 수 ,간선의 수 , 시작정점
            int[] nmv = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            n = nmv[0]; // 정점의 갯수
            int m = nmv[1]; //노드의 갯수
            int v = nmv[2]; // 시작 정점

            //그래프 초기화 정점의 수 n을 배열에 담으려면 n+1 만큼 선언
            graph = new int[n + 1, n + 1];
            //노드의 갯수 만큼 순회
            for (int i = 0; i < m; i++)
            {
                // 건선을 가진  XY 정점들을 담을 배열 선언 후 입력받아 변수 초기화
                int[] xy = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                //2차원 배열 그래프에 노드가 있다면 1로 선언
                graph[xy[0], xy[1]] = 1;
                graph[xy[1], xy[0]] = 1;
            }

            //깊이 우선 탐색 메서드 시작정점 V 매개변수
            DFS(v);
            Console.WriteLine();
            //너비 우선 탐색 메서드 
            BFS(v);
        }
        static void DFS(int x)
        {
            // 스택 생성
            Stack<int> stack = new Stack<int>();
            // 방문한 정점 들을 담을 정수 배열 선언 0~4까지
            int[] visited = new int[n + 1];
            //스택에 정점 Push
            stack.Push(x);
            //방문한 정점 표시
            visited[x] = 1;
            //방문한 정점 출력
            Console.Write("{0} ", x);

            while (stack.Count > 0)
            {
                int u = stack.Peek();
                //이어져 있는 노드를 방문했는가?
                bool end = true;
                //정점의 갯수 + 1 만큼 순회
                for (int v = 0; v < n + 1; v++)
                {
                    //탐색을 시작할 정점 과 정점 사이에 간선 있고 아직 방문하지 않은 정점이라면
                    if (graph[u, v] == 1 && visited[v] == 0)
                    {
                        //이어져 있는 정점 스택에 Push
                        stack.Push(v);
                        //방문한 정점 표시
                        visited[v] = 1;
                        //방문한 정점 출력
                        Console.Write("{0} ", v);
                        end = false;
                        break;
                    }
                } 
                //해당 정점과 간선이 있는 정점이 더이상 없다면 
                if (end)
                    stack.Pop();
            }
        }
        static void BFS(int x)
        {
            //q생성
            Queue<int> q = new Queue<int>();
            //방문 정점을 담을 정수 배열 생성
            int[] visited = new int[n + 1];
            //q에 시작 정점 담기
            q.Enqueue(x);
            //방문 정점 표시
            visited[x] = 1;
            //방문 정점 출력
            Console.Write("{0} ", x);

            while (q.Count > 0)
            {
                // Dequeue한 정점 변수에 담기
                x = q.Dequeue();
                //정점의 갯수 + 1 만큼 순회
                for (int y = 0; y < n + 1; y++)
                {
                    //탐색을 시작할 정점 과 정점 사이에 간선이 있고 아직 방문하지 않은 정점이라면
                    if (graph[x, y] == 1 && visited[y] == 0)
                    {
                        //간선이 있는 정점 출력 (자식 정점 출력)
                        Console.Write("{0} ", y);
                        //방문한 정점 표시
                        visited[y] = 1;
                        q.Enqueue(y);
                    }
                }
            }
        }
    }
}

결과창

아직 익숙하지 않은 부분이 많아 헷갈리는 부분이 많이 있었다.

원래는 최소신장 트리 문제를 바로 풀어보려고 했으나 생각보다 BFS 와 DFS 를 모르면 문제를 풀기 어려웠기에 다시 원점으로 돌아와  BFS 와 DFS 문제를 먼저 분석해 보았다.

 

사실 아직도 원리도 이해가 가고 어떤 식으로 코드를 작성하는지 까지 이해는 가나 직접 작성해보려고 하면 생각보다 난관이 있어 좀더 공부를 해야하는 부분이다.