[백준] 1260 - DFS와 BFS

1. 문제

1260번: DFS와 BFS

2. 개요

주어진 그래프를 DFS와 BFS로 탐색한 결과를 출력하는 문제.

단 방문 정점이 여러개인 경우 번호가 작은 것을 우선 탐색한다.

3. 풀이 및 코드

3-1. 풀이

기초적인 DFS, BFS문제.

인접한 정점의 방문여부를 판단하며 탐색을 진행하면 된다.

번호가 작은 정점을 우선 방문해야하므로 정렬을 수행하면서 DFS로 탐색한다. 이렇게 진행하면 BFS로 탐색할 때는 이를 신경 쓸 필요가 없어진다.

3-2. Python

import sys
from collections import deque

N, M, V = map(int, sys.stdin.readline().split())

graph = [[] for i in range(N+1)]
visited = [False for i in range(N+1)]

for i in range(M):
    info = list(map(int, sys.stdin.readline().split()))

    graph[info[0]].append(info[1])
    graph[info[1]].append(info[0])

def DFS(n):
    visited[n] = True
    print(n , end = ' ')

    graph[n].sort()
    for nxt in graph[n]:
        if visited[nxt] == True:
            continue

        DFS(nxt)

def BFS(n):
    q = deque([n])

    while q:
        now = q.popleft()

        visited[now] = True
        print(now, end = ' ')
        
        for nxt in graph[now]:
            if visited[nxt] == True:
                continue

            visited[nxt] = True

            q.append(nxt)

DFS(V)
visited = [False for i in range(N+1)]
print()
BFS(V)

3-3. C#

namespace boj_1260
{
    internal class Program
    {
        static List<List<int>> graph;
        static bool[] visited;

        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 = new List<List<int>>();

            for (int i = 0; i < N + 1; i++)
            {
                graph.Add(new List<int>());
            }

            visited = new bool[N + 1];

            for (int i = 0; i < M; i++)
            {
                string[] info = Console.ReadLine().Split();

                graph[int.Parse(info[0])].Add(int.Parse(info[1]));
                graph[int.Parse(info[1])].Add(int.Parse(info[0]));
            }

            DFS(V);
            Array.Fill(visited, false);
            Console.WriteLine();
            BFS(V);
        }

        static void DFS(int n)
        {
            Console.Write($"{n} ");

            visited[n] = true;
            graph[n].Sort();

            foreach (int nxt in graph[n])
            {
                if (visited[nxt])
                    continue;

                DFS(nxt);
            }
        }

        static void BFS(int n)
        {
            Queue<int> q = new Queue<int>();
            q.Enqueue(n);
            visited[n] = true;

            while (q.Count > 0)
            {
                int now = q.Dequeue();

                Console.Write($"{now} ");

                foreach(int nxt in graph[now])
                {
                    if (visited[nxt])
                        continue;

                    visited[nxt] = true;

                    q.Enqueue(nxt);
                }
            }
        }
    }
}