[ BOJ/C# ] 1260 DFS와 BFS

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

1260번: DFS와 BFS

백준에서 처음으로 DFS로 문제를 풀어본 듯하다. 

이번엔 보기 좋게 전역변수와 메서드로 풀어보았다. 

DFS는 깊이 우선 탐색으로, 공부하며 보니 주로 재귀함수나 Stack으로 푸는 것을 알 수 있었다. 

이 문제는 재귀함수로 풀어보았다. 

 

+ visited를 초기화 해주기 위하여 new bool[1001]과 Array.Clear[visited]를 사용해 보았다. 

메모리를 우선한다면 Array.Clear(), 시간을 우선한다면 new로 가능하다. 

위 - Array.Clear / 아래 - new

using System;
using System.Text;
using System.IO;

namespace B1260
{
    class Program
    {
        static StringBuilder sb = new StringBuilder();
        static bool[] visited = new bool[1001];
        static int[,] map = new int[1001, 1001];
        static void Main()
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int[] nmv = Array.ConvertAll(sr.ReadLine().Split(' '), int.Parse);
            for (int i = 0; i < nmv[1]; i++)
            {
                int[] ab = Array.ConvertAll(sr.ReadLine().Split(' '), int.Parse);
                map[ab[0], ab[1]] = 1;
                map[ab[1], ab[0]] = 1;
            }
            DFS(nmv[0], nmv[2]);    //깊이 우선 탐색
            visited = new bool[1001];   //방문 기록 초기화
            sb.Append('\n');
            BFS(nmv[0], nmv[2]);    //너비 우선 탐색
            sw.Write(sb);
            sr.Close();
            sw.Flush();
            sw.Close();
        }
        static void DFS(int n, int x)
        {
            sb.Append(x);
            visited[x] = true;
            for (int y = 1; y <= n; y++)
            {
                if (map[x, y] == 0) continue;   //연결X
                if (visited[y]) continue;   //y방문함
                sb.Append(' ');
                DFS(n, y);
            }
        }
        static void BFS(int n, int v)
        {
            Queue<int> q = new Queue<int>();
            q.Enqueue(v);

            while (q.Count > 0)
            {
                int x = q.Dequeue();
                if (visited[x] == false)
                {
                    sb.Append(x);
                    sb.Append(' ');
                    visited[x] = true;
                }
                for (int y = 1; y <= n; y++)
                    if (map[x, y] == 1 && visited[y] == false) q.Enqueue(y);
            }
        }
    }
}