[Python] 백준 1260 DFS와 BFS

 

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

1260번: DFS와 BFS

 

 

접근 : 

 - 기본적인 DFS 와 BFS 관련 문제

 

 

- DFS

 

 

 

 

- BFS

 

 

 - 코드 구현 : 

from collections import deque
import sys


def answer():
    N, M, V = map(int, sys.stdin.readline().rstrip().split(' '))
    graph = [[] for _ in range(N+1)]
    d_visited = [False] * (N+1)

    for _ in range(M):
        s, e = map(int, sys.stdin.readline().rstrip().split(' '))
        graph[s].append(e)
        graph[e].append(s)

    for i in range(1, N+1):
        graph[i].sort()

    def dfs(idx, res=''):
        res += str(idx) + ' '
        d_visited[idx] = True

        for next in graph[idx]:
            if not d_visited[next]:
                res = dfs(next, res)
        return res

    def bfs(idx):
        b_visited = [False] * (N+1)
        res = ''
        q = deque()

        q.append(idx)
        res += str(idx) + ' '
        b_visited[idx] = True

        while q:
            idx = q.popleft()
            for next in graph[idx]:
                if not b_visited[next]:
                    q.append(next)
                    res += str(next) + ' '
                    b_visited[next] = True
        return res

    print(dfs(V))
    print(bfs(V))

answer()