[DFS, BFS] 백준 1260번: DFS와 BFS

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

1260번: DFS와 BFS

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사

www.acmicpc.net

import collections
n, m, v = map(int,input().split())
graph = collections.defaultdict(list)

for _ in range(m):
    node1, node2 = map(int,input().split())
    graph[node1].append(node2)
    graph[node2].append(node1)
for i in range(n):
    graph[i] = sorted(graph[i])

start = v
dfs_discovered = []
bfs_discovered = [start]
def dfs(node):
    if node in dfs_discovered:
        return
    dfs_discovered.append(node)
    for next in graph[node]:
        dfs(next)
def bfs():
    queue = [start]
    while queue:
        cur = queue.pop(0)
        for next in graph[cur]:
            if next not in bfs_discovered:
                queue.append(next)
                bfs_discovered.append(next)
dfs(start)
bfs()
print(*dfs_discovered)
print(*bfs_discovered)

<배운점>

- dfs는 재귀, bfs는 큐로 구현

- 중복 방지를 위해 discovered라는 리스트를 만들어 방문 여부를 확인해줘야 한다.

- 마지막에 *기호는 리스트를 언팩해주는 기호다. 리스트 형식을 숫자로만 출력해야할 때 쓰면 된다.