[Python][백준] 1260번 DFS와 BFS | 런타임 에러 (KeyError) 해결

DFS(Depth First Search)와 BFS(Breadth First Search)

컴퓨터시스템개론, 자료구조, 알고리즘을 하나라도 들어봤다면 누구나 알지.

그래프 이론의 핵심.

 

모르는 사람은 아래 영상을 보고 배워보자

https://youtu.be/pcKY4hjDrxk

CS 1타 강사 Professor Abdul Bari 사랑해요

 

Python으로 구현해보겠다!

그래프를 구현하는 방법은 인접 행렬 (Adjacency matrix)과 인접 리스트 (Adjacency List)가 있다.

필자는 그 중 인접 리스트, 정확히는 Python의 dictionary 자료구조를 이용하여 그래프를 만들고, DFS와 BFS를 구현할 것이다.

여러 웹페이지, 백준 질문게시판 등등을 참고하여 만들었다.

 

그래프 구현

node, edge, start = map(int, input().split())  # 정점, 간선, 시작할 정점의 번호 입력

graph = {}  # 그래프, dictionary 초기화
for _ in range(edge):
    src, dst = map(int, input().split())  # 출발 정점, 도착 정점 입력
    if src not in graph.keys():
        graph[src] = {dst}  # dict에 src가 없으면(새로운 정점이면) 새로운 자료 생성 
    else:
        graph[src].add(dst)  # dict에 src가 있으면(기존 정점이면) 추가
	
    # 양방향 그래프
    if dst not in graph.keys():
        graph[dst] = {src}
    else:
        graph[dst].add(src)
        
print(*dfs(graph, start), sep=' ')  # dfs 실행 결과(리스트) 출력
print(*bfs(graph, start), sep=' ')  # bfs 실행 결과(리스트) 출력

 

DFS, BFS

def dfs(graph, start):
    visited = list()
    stack = list()  # 리스트 자료구조를 스택처럼 사용.

    stack.append(start)

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            if node in graph:  # 왜 이렇게 했는지는 밑에서 설명하겠다!
                stack.extend(sorted(graph[node], reverse=True))
                # 딕셔너리의 요소를 뒤집어 스택에 넣어, 작은 수부터 방문하게 설계

    return visited


def bfs(graph, start):
    visited = list()
    deque = deque()  # 덱 자료구조를 사용하여, 실행시간 개선

    deque.append(start)
    while deque:
        node = deque.popleft()  # FIFO
        if node not in visited:
            visited.append(node)
            if node in graph:  # 왜 이렇게 했는지는 밑에서 설명하겠다!
                queue.extend(sorted(graph[node]))
                
    return visited

 

런타임 에러 (KeyError) 해결

 

if node in graph로 해결하라

반례

위와 같은 그래프가 있다고 가정하자.

위 그래프를 순회할 때, 시작 정점이 5이면 어떻게 될까?

 

그래프를 만들때 정점 5는 존재하지만 입력하지 않았다.

다른 정점과 연결되지 않았기 때문이다.

 

그런데 이 정점에서 그래프 순회를 시작한다?

시작하고, 그래프의 인접 정점을 큐/스택에 넣어야 하는데, 딕셔너리에 정점이 없다??

즉시오류.

 

그래서, 그래프에 노드가 있을 때만 큐/스택에 넣을 수 있게 예외처리를 해주어야한다.

 

해결