백준 1260 DFS와 BFS

문제

DFS와 BFS

문제 그대로 DFS와 BFS를 구현하라

난이도 : Silver2

---

풀이

1. 정점과 간선 정보를 주면, dfs와 bfs를 모두 구현하고 방문 순서 출력

---

코드

import sys
from collections import deque, defaultdict

N, M, V = tuple(map(int, sys.stdin.readline().split()))
vertex = defaultdict(list)

for _ in range(M):
    p1, p2 = tuple(map(int, sys.stdin.readline().split()))
    vertex[p1].append(p2)  # 1 2가 주어졌으면 2 1도 그래프에 포함시킴
    vertex[p2].append(p1)

dfs_answer = []

def bfs(start):
    answer = []
    visit = [False] * N
    q = deque([start])
    visit[start-1] = True
    
    while q:
        point = q.popleft()
        answer.append(point)
        
        for i in sorted(vertex[point]):  # 작은 정점부터 방문해야 하므로 오름차순 정렬
            if not visit[i-1]:
                visit[i-1] = True  # 노드는 1부터 시작하지만 인덱스는 0부터 시작
                q.append(i)

    return answer

def dfs(start, visited):
    visited[start-1] = True
    dfs_answer.append(start)
    
    for point in sorted(vertex[start]):
        if not visited[point-1]:
            dfs(point, visited)  # 재귀로 이어진 정점을 최대한 깊게 탐색


dfs(V, [False] * N)
for i in dfs_answer:
    print(i, end=' ')
print('')
for i in bfs(V):
    print(i, end=' ')

        

---

결과

모든 그래프 문제를 bfs로 풀다 보니 dfs가 어색했다. 둘 다 자유자재로 구현할 수 있도록 많이 풀 필요성을 느꼈다.