[C#] 백준 1260번 DFS와 BFS

[ 문제 ]

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

 

[ 코드 ]

 

class Graph
{
    public int V;
    public List<int>[] adj;

    public Graph(int v)
    {
        V = v;
        adj = new List<int>[V + 1];
        for (int i = 1; i <= V; i++)
        {
            adj[i] = new List<int>();
        }
    }

    public void AddEdge(int u, int v)
    {
        adj[u].Add(v);
        adj[v].Add(u);
    }

    public void DFS(int v)
    {
        bool[] visited = new bool[V + 1];
        DFSUtil(v, visited);
    }

    private void DFSUtil(int v, bool[] visited)
    {
        visited[v] = true;
        Console.Write(v + " ");

        foreach (int u in adj[v])
        {
            if (!visited[u])
            {
                DFSUtil(u, visited);
            }
        }
    }

    public void BFS(int v)
    {
        bool[] visited = new bool[V + 1];
        Queue<int> queue = new Queue<int>();

        visited[v] = true;
        queue.Enqueue(v);

        while (queue.Count != 0)
        {
            v = queue.Dequeue();
            Console.Write(v + " ");

            foreach (int u in adj[v])
            {
                if (!visited[u])
                {
                    visited[u] = true;
                    queue.Enqueue(u);
                }
            }
        }
    }
}

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

        Graph graph = new Graph(N);

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

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

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

        graph.BFS(V);
    }
}

 

[ 실행화면 ]

case: 1

 

 

 

 

 

---

문제링크: https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS