[Python/파이썬] 백준 1260번 DFS와 BFS

1260번: DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

코드

# 1260번 DFS와 BFS
import sys

n,m,v = map(int,sys.stdin.readline().split())

graph = {i:[] for i in range(1,n+1)}
visit = []

def dfs(root):
    print(root, end=" ")
    visit.append(root)

    for r in graph[root]:
        if r in visit:
            continue
        dfs(r)
    
def bfs(root):        
    queue = []
    
    queue.append(root)
    visit.append(root)

    while queue:
        print(queue[0], end=" ")
        tmp = queue[0]
        queue.pop(0)

        for el in graph[tmp]:
            if el not in visit:
                queue.append(el)
                visit.append(el)

for i in range(m):
    a, b = map(int,sys.stdin.readline().split())
    
    graph[a] = graph.get(a,[]) + [b]
    graph[b] = graph.get(b,[]) + [a]

#정점의 번호가 작은 것부터 방문하기 위해 정렬
for el in graph.values():
    el.sort()

dfs(v)
visit.clear()
print()
bfs(v)

dfs는 재귀, bfs는 큐를 이용하여 풀었다. bfs는 리스트를 이용하긴 했지만 큐의 FIFO(First In First Out) 특성을 이용했기 때문에 큐를 이용했다고 봐도 무방할 것 같다.

 

딕셔너리 객체의 get 메소드는 

        딕셔너리.get(key[, default값])

형태로 사용할 수 있다. 이 메소드는 첫번째 인자로 넣어준 키의 value를 리턴해준다. 

만약 해당 key가 없다면 두번째 인자의 값을 리턴하게 되는데, default값은 None이다.

 

그래프는 딕셔너리를 이용했는데 처음에 딕셔너리를 

graph={ }

이렇게만 선언해주고 제출했더니 KeyError가 떴다. 이게 딕셔너리에 존재하지 않는 키값으로 접근하려 해서 생기는 오류이다.

딕셔너리에 데이터를 추가해줄 때는

     딕셔너리[키값] = 밸류

이렇게 해주면 된대서 그냥 입력받으며 키값과 밸류값을 추가할 수 있다고 생각했는데 이렇게 하면 안되는것 같다.