[백준]1260번 DFS와 BFS (Python/파이썬) - 런타임 에러(KeyError) 해결

문제

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

 

입력

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

출력

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

 

> 예제 입력 1

4 5 1
1 2
1 3
1 4
2 4
3 4

 

> 예제 출력 1

1 2 4 3
1 2 3 4

 

> 예제 입력 2

5 5 3
5 4
5 2
1 2
3 4
3 1

 

> 예제 출력 2

3 1 2 5 4
3 1 4 2 5

 

> 예제 입력 3

1000 1 1000
999 1000

 

> 예제 출력 3

1000 999
1000 999

---

주의할 점

문제에서 주의할 점은 예외 입력에 대한 처리입니다!

테스트 입력 세 가지 경우에서 오류가 없었는데, 아래와 같은 예외를 처리하지 않으면 런타임 에러(Key Error)가 발생할 수 있습니다.

 

1) 시작 노드 2에 연결된 노드가 없는 경우

5 1 2
3 4

 

2) 노드 간 연결이 없는 경우, edge의 개수 M=0

5 0 2

 

위와 같은 경우에서는 아래와 같이 시작 노드 V가 출력되도록 하시면 됩니다.

 

> 출력 예시

2 #dfs result
2 #bfs result

---

작성 코드

제 코드는 BK_Paul 님의 파이썬 구현을 참고했고, 입력/출력 처리와 예외 처리 부분에서 약간의 변형을 했습니다.

from collections import deque

def dfs(graph, start_node):
    ## deque 패키지 불러오기
    visited = []
    need_visited = deque([start_node])

    ## 방문이 필요한 리스트가 아직 존재한다면
    while need_visited:
        ## 시작 노드를 지정하고
        node = need_visited.pop()

        ##만약 방문한 리스트에 없다면
        if node not in visited:
            ## 방문 리스트에 노드를 추가
            visited.append(node)
            need_visit = sorted(graph[node], reverse=True)
            need_visited.extend(need_visit)

    return visited


def bfs(graph, start_node):
    need_visited, visited = [], []
    need_visited.append(start_node)

    while need_visited:
        node = need_visited[0]
        del need_visited[0]

        if node not in visited:
            visited.append(node)
            ## 인접 노드들을 방문 예정 리스트에 추가
            need_visit = sorted(graph[node])
            need_visited.extend(need_visit)

    return visited

N, M, V = map(int, input().split())

# 1) edge가 아예 없는 경우
if M == 0:
    print(V)
    print(V)
    exit()

graph = dict()
for i in range(M):
    key, val = map(int, input().split())
    if key in graph:
        graph[key].append(val)
    else:
        graph[key] = [val]

    if val in graph:
        graph[val].append(key)
    else:
        graph[val] = [key]


# 2) V의 edge가 없는 경우
if V not in graph:
    print(V)
    print(V)
    exit()

dfs_visited = dfs(graph, V)
bfs_visited = bfs(graph, V)

dfs_result = ""
for visit in dfs_visited:
    dfs_result += "{} ".format(visit)

bfs_result = ""
for visit in bfs_visited:
    bfs_result += "{} ".format(visit)

print(dfs_result.rstrip(" "))
print(bfs_result.rstrip(" "))

---

문제 출처

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

1260번: DFS와 BFS

 

 

코드 참고

https://data-marketing-bk.tistory.com/entry/BFS-%EC%99%84%EB%B2%BD-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC

BFS 완벽 구현하기 - 파이썬

https://data-marketing-bk.tistory.com/entry/DFS-%EC%99%84%EB%B2%BD-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC

DFS 완벽 구현하기 [Python]