# 22 [파이썬] 백준 1260번: DFS와 BFS ( 인접리스트 풀이 )

<문제>

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

---

 

<소스코드>

import sys
from collections import deque
input = sys.stdin.readline

def DFS(graph, v):
    visited = {}
    stack = [v]
    while stack:
        d = stack.pop()
        if d not in visited:
            visited.setdefault(d)
            stack += reversed(graph[d])
    return visited

def BFS(graph, v):
    visited = {}
    deq = deque([v])
    while deq:
        d = deq.popleft()
        if d not in visited:
            visited.setdefault(d)
            deq += graph[d]
    return visited

n, m, v = map(int, input().split())
graph = {i:[] for i in range(1,n+1)}

for i in range(1, m+1):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

for key in graph:
    graph[key].sort()

print(*DFS(graph, v))
print(*BFS(graph, v))

---

 

<NOTE>

★★★1. 그래프를 그릴 때, 시작노드의 간선이 없는 경우를 반드시 고려해야한다.

이것을 모르고 처음 그래프를 그렸을 때 아래와 같이 그렸다.

n, m, v = map(int, input().split())
graph = dict()

for _ in range(m):
    a, b = map(int, input().split())
    if a not in graph:
        graph[a] = list()
    if b not in graph:
        graph[b] = list()
    graph[a].append(b)
    graph[b].append(a)

그러나, 이렇게 할 경우 시작노드의 간선이 없는 케이스 때문에 런타임에러(KeyError)가 발생한다. 따라서, 시작노드에 간선이 없는 경우 while문을 빠져나갈 수 있도록 입력값으로 들어온 데이터가 아닌 모든 노드에 대해 리스트를 초기화한 후 그래프를 만들어야 한다.

 

 

 

2. deque에 리스트로된 원소를 넣을 경우, append가 아닌 +=로 붙이자!

아래와 같이 작성하면 기존 리스트 내에 리스트 원소 형식으로 들어가기 때문에 해시 규정에 맞지 않게 된다. 

deq.append(graph[d])

따라서 기존의 리스트에 원소만 넣으려면 아래와 같이 작성해야 한다.

deq += graph[d]

 

 

 

3. 리스트 내에서 특정 원소를 찾아야 한다면, 리스트가 아닌 딕셔너리를 사용하자!

리스트에서 특정 원소를 찾을 때 시간복잡도는 원소 개수에 비례하여 O(N)이 된다. 반면, 딕셔너리에서 특정 key를 찾을 때 시간복잡도는 O(1)이다. 이용하고자 하는 것이 key: value쌍의 해시구조가 아닐지라도 append대신 "setdefault()"를 사용하여 value값은 None으로 만들어주고, key값만 입력하여 마치 리스트인것처럼 사용하면 된다.