BOJ 1260 BFS와 DFS python

본격적으로 그래프 탐색에 대한 공부를 시작하게 됐는데, 역시 처음에는 가장 기본에 충실한 문제를 풀어봐야 한다.

이론으로써 알고 있는 절차를 그대로 코드에 녹여낼 수 있는 문제였다.

기

문제를 풀기에 앞서, 기본적인 DFS와 BFS에 대한 내용을 공부했다.

DFS(depth first search)는 깊이 우선 탐색이다. 그래프를 탐색할 때, 더 이상 인접한 노드가 없을 때까지 그래프를 파고든다.

인접한 노드가 없을 때까지 방문하는 모든 노드들을 스택 자료구조에 넣어야 하기 때문에, 자연스럽게 시스템 상의 스택을 이용하는 재귀 함수로 구현을 하게 된다.

BFS(breadth first search)는 너비 우선 탐색이다. 그래프를 탐색할 때, 한 노드와 인접한 노드를 차례대로 방문하는 과정을 반복한다.

인접한 노드가 없을 때까지 같은 level의 노드들을 큐 자료구조에 넣어야 한다.

또한 두 탐색 기법을 이용할 때, 당연하게도 그래프를 구성하고 

 

승

그래프를 먼저 구현하는데, 그래프를 구현하는 방법에는 인접 리스트 형식과 인접 행렬 형식이 있다.

인접 리스트는, 이차원 배열을 만들어서 각 번호의 원소에 인접한 노드의 번호들을 모두 기입하는 형식으로 만들어진다.

인접 행렬은, n 개의 노드에 대해 n*n 정방행렬을 만들어서 각 원소들의 인접 여부를 체크하는 형식으로 만들어진다.

인접 리스트는 노드를 탐색하는 데 걸리는 시간이 인접 행렬에 비해 크다는 단점이 있고, 인접 행렬은 인접 리스트에 비해 탐색은 빠르지만 메모리 오버헤드가 크다는 단점이 있다.

또한 그래프 탐색을 할 때는 방문 처리를 할 수 있어야 한다. 이는 어떤 노드를 방문했을 때 그 노드를 방문했다는 표시를 할 수 있어야 한 노드의 인접 노드를 살필 때 그 노드를 건너뛸 수 있기 때문이다.

 

전

먼저 그래프를 인접 리스트로 구현하고,dfs와 bfs에 각각 사용할 방문 리스트를 만들어주었다. 또한 인접한 노드들에 대한 탐색은 오름차순으로 이뤄지기 때문에 인접 리스트의 원소들을 정렬해주었다.

dfs는 인접 노드를 살펴본 후, 방문하지 않은 노드를 스택에 넣고 방문 처리를 한 뒤 재귀호출을 한다. 그래프의 끝까지 호출하면, 스택에 들어있는 노드 순으로 리턴되면서 처음 시작 노드까지 돌아오게 된다.

bfs는 인접 노드를 살펴보고 방문하지 않은 노드를 큐에 넣고 방문 처리를 한다. 이후 큐에 남아있는 노드들을 순서대로 pop한다. 이 노드의 인접 노드들 중 방문하지 않은 노드들에 대해 방문 처리를 하고 큐에 집어넣는다.

 

결

그래프 탐색 문제를 제대로 공부하기 전, 이론 복습을 다시 하면서 온전히 코드를 작성하느라 시간이 조금 걸렸다. 워낙 기본적인 형태의 그래프 탐색 코드라, 다른 문제들에서 여러 갈래로 응용을 할 수 있을 것이다. 이 형태를 잘 기억해놔야겠다.

---

코드

from collections import deque

n,e,s = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited_dfs = [s]
visited_bfs = [s]

for i in range(e):
    a, b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    graph[a].sort()
    graph[b].sort()

def dfs(graph, visited_dfs, start):
    for child in graph[start]:
        if child not in visited_dfs:
            print(child, end = ' ')
            visited_dfs.append(child)
            dfs(graph, visited_dfs, child)

print(s, end = ' ')
dfs(graph, visited_dfs, s)
print()
print(s, end = ' ')
q = deque([s])
while q:
    node = q.popleft()
    for child in graph[node]:
        if child not in visited_bfs:
            q.append(child)
            visited_bfs.append(child)
            print(child, end = ' ')