[백준] 1260번 DFS와 BFS (Python)

문제와 입출력

예시

 

시간 복잡도와 공간 복잡도

입력 조건에 "첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다." 라는 조건이 있었다. DFS와 BFS의 시간 복잡도는 O(|V+E|)이다. 그래서 문제의 조건에 따르면 최악의 경우 O(11000)이라는 시간 복잡도가 나온다. 시간 제한이 2초이고 파이썬이 1초에 2000만번 연산한다는 점을 고려해 봤을 때 시간 복잡도는 굉장히 널널하다.

---

알고리즘

문제에서 요구하는 것은 정보를 입력받아 그래프를 만들고, 낮은 노드를 우선 방문하는 조건으로 DFS, BFS 탐색하는 것이기에 알고리즘은 굉장히 단순하다. 아래는 자연어 알고리즘과 파이썬 코드이다.

 

1. 그래프 정보를 입력받아 저장한다. 

2. 입력 받은 정보를 토대로 그래프를 생성한다. 이때, 노드는 오름차순으로 정렬되어야 한다. 

3. 그래프 탐색을 각각의 방식으로 시도한다. 

4. 그래프 탐색을 하면서 방문 노드를 출력한다.

 

from collections import deque
# 1. 그래프의 정보를 입력받아 저장한다.
node, edge, start = map(int,input().split())
graph = [[] for i in range(node+1)]

for i in range(edge):
    inp = list(map(int, input().split()))
    graph[inp[0]].append(inp[1])
    graph[inp[1]].append(inp[0])
    graph[inp[0]].sort() # 낮은 숫자 우선 방문을 위한 오름차순 정렬
    graph[inp[1]].sort()

# dfs, bfs 함수
def dfs(graph, v, visit):
    visit[v] = True
    print(v, end =" ")
    for i in graph[v]:
        if not visit[i]:
            dfs(graph, i, visit)

def bfs(graph, v, visit):
    queue = deque([v])
    visit[v] = True
    while queue:
        tar = queue.popleft()
        print(tar, end =" ")
        for i in graph[tar]:
            if not visit[i]:
                queue.append(i)
                visit[i] = True
    

visit = [False] * (node+1)
dfs(graph,start, visit)
# 방문테이블동시에 사용시 리셋 필요
visit = [False] * (node+1)
print()
bfs(graph,start,visit)

---

배운 점(소감)

앞서 말했다시피, 문제에서 요구하는 내용은 단순 BFS, DFS 탐색으로 굉장히 단순하다. 하지만, 이렇게 알고리즘이 단순한 경우에는 그래프 구성과 다른 구성 요소에 조건이 붙을 수도 있다. 다음은 그 예시이다.

 

조건 1. 낮은 노드를 우선적으로 방문한다.

그래프의 각 노드에 연결된 노드를 저장할 때, 노드를 오름차순으로 정렬해야 낮은 노드를 우선적으로 방문한다.

 

조건 2. 방문 테이블 초기화 필요

한 그래프 탐색을 완료하면 다음 그래프 탐색을 위해 방문테이블을 원상 복구 시켜놔야 한다.

---

DFS, BFS 구현 실수

이 문제에서는 DFS와 BFS 탐색을 구현하는 것이 주요 과제이다. 두 탐색을 구현할 때 저질렀던 실수는 아래와 같다.

 

실수 1. DFS 재귀함수 호출 실수 TypeError: 'list' object is not callable

DFS, BFS 모두 재귀함수 호출이 필요하다. 이때 DFS()에 대해서 재귀함수 호출을 해야하는데 리스트 자료구조인 Graph를 재귀호출하여 위와 같은 에러가 발생했다.

 

실수 2. BFS에서 방문 여부를 판단 받는 요소는?

BFS 구현 시, Queue의 Front에서 dequeue된 요소에 인접하고 방문하지 않은 요소들을 rear에 enqueue해야 한다.

이 과정에서 방문 테이블로 방문 여부를 판단 받아야 하는 요소들은 dequeue된 요소가 아니라 dequeue된 요소에 인접한 요소들이라는 것을 명심하자.