[Python/Baekjoon] 1260. DFS와 BFS

💬 문제

문제 난이도: 백준 실버 2

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

❗️접근 방법

1. 재귀를 사용해서 DFS를 구현한다.
DFS란? 해당 노드에 대한 분기를 모두 탐색 후 다른 노드로 넘어가는 방식

2. 큐를 사용해서 BFS를 구현한다.
BFS란? 시작 노드에서 가까운 노드를 먼저 탐색한 후 멀리 떨어져 있는 노드를 탐색하는 방식

✅ 정답 코드

# DFS와 BFS
import sys
from collections import defaultdict, deque
input = sys.stdin.readline

route = defaultdict(list)
N, M, V = map(int, input().rstrip().split(' '))
for _ in range(M):
    one, two = map(int, input().split(' '))
    route[one].append(two)
    route[two].append(one)
visitedBfs = [0 for _ in range(N)]
visitedDfs = [0 for _ in range(N)]

# 오름차순 정렬
for key in route:
    route[key].sort()

def dfs(start):
    print(start, end = ' ')
    visitedDfs[start-1] = 1
    for next in route[start]:
        if visitedDfs[next-1] != 1:
            dfs(next)

def bfs(start):
    queue = deque([start])
    visitedBfs[start-1] = 1
    while queue:
        q = queue.popleft()
        print(q, end = ' ')
        for next in route[q]:
            if visitedBfs[next-1] != 1:
                queue.append(next)
                visitedBfs[next-1] = 1

def solution():
    dfs(V)
    print('')
    bfs(V)

solution()