들어가며
최근에 BFS 유형의 문제에 익숙해지기 위해 백준에서 BFS 문제들을 풀어보았다. 문제를 풀면서 어려움을 겪었던 점이 있어 이를 설명하고 풀이 방법에 대해서 정리해볼 것이다. 코드는 파이썬을 기준으로 작성했다.
헷갈렸던 점
처음에 BFS문제를 풀면서 가장 헷갈렸던 부분은 언제 방문 체크를 해야하는지였다. 기존에 알고있던 BFS의 동작방식과 내가 블로그에서 찾았던 코드들의 구현방법이 달랐기 때문에 그랬던 것 같다.
# 대략 내가 찾았던 코드의 동작 예시
visited = [] # 방문한 곳을 저장할 저장소
queue = deque([root])
while queue:
value = queue.popleft() #꺼내고(dequeue)
if value not in visited: #방문하지 않은 것이면
visited.append(value) #방문 처리하고
queue += (set(graph[value]) - set(visited)) #queue에 enqueue
많은 블로그에서 위처럼 dequeue를 할 때 방문체크를 하고 if 문을 통해 중복으로 enqueue된 값을 거르는 방법을 알려주었는데, 곰곰이 생각해보니 꼭 그럴 필요가 없다고 생각이 들었다.
예를 들어 위와 같은 방법(dequeue시 방문체크)으로 위 그래프를 1번부터 방문 한다면
queue에 들어가는 순서는 다음과 같을 것이다.
1 - 2 - 3 - 4 - 4
위에 4번 노드가 2번 들어간 것 처럼 queue에 방문할 데이터가 중복으로 들어가는 경우가 생길 수 있고 이는 트리 관계가 복잡해질 수록 중복이 많아진다.
물론, 이를 visited에 있는지 확인을 통해 중복데이터를 거르긴 하지만 처음에 enqueue할 때 방문체크를 해버리면 불필요하게 중복으로 넣었다 뺄 필요가 없다고 생각했다.
그래서 enqueue시에 방문체크를 하는 방법이 더 직관적이고 효율적이라고 생각이 들어 나는 이 방법으로 구현을 하기로 했다.(물론 위의 방법이 틀린 것은 아니다.)
BFS 구현하는 법
대략적인 동작방식은 다음과 같다.
- 갈 곳을 queue에 넣는다.(root를 enqueue)
- 갈 곳에 방문 체크를 한다.(visited에 추가)
- queue에서 dequeue를 하여 가장 먼저 방문할 노드를 꺼내온다.
- 갈 수 있는 곳에서 이미 갔던 곳(visited에 추가된 곳)을 제외하고 다시 queue에 넣는다.(1번과 같은 enqueue작업)
- 2~4과정을 반복한다.
위를 파이썬으로 구현한 코드는 다음과 같다.
root = 1
visited = set([])
queue = deque() #'from collections import deque'선언 필요
queue.append(root)
visited.add(root)
while queue:
value = queue.popleft() # 꺼내기(dequeue)
queue += graph[value] - visited # 방문할 곳 넣기(enqueue), graph와 visited 둘 다 set
visited.update(graph[value] - visited) # 방문체크(set이면 굳이 visited를 안빼도 됨)
위의 코드에서 눈여겨 볼 점이 또 두 가지가 있다.
1. 라이브러리를 통해 deque를 사용
- 파이썬에서 pop(0)을 통해서도 dequeue동작을 할 수 있지만 연결리스트로 구현된 deque의 popleft()를 이용해 dequeue동작의 시간복잡도를 O(n)에서 O(1)로 줄일 수 있다.
2. set 활용
- enqueue 동작을 할 때 visited에 있는 노드를 제외한 노드들을 넣어야하는데, 각 노드는 유일하기 때문에 visited나 graph에서 중복된 정보를 가질 필요가 없다.
- 따라서 set을 이용할 수 있는데 set을 이용하면 차집합을 간단히 구현할 수 있어 편리하다.
⚠️주의
set은 순서가 보장되지 않기 때문에 간선간 가중치가 있거나 경로를 알아야 하는 경우에는 적합하지 않다.
깊이를 카운팅 하는 법
위의 문제에서 최단거리를 구해야 했는데 '최단거리 == BFS로 첫 탐색의 깊이'이기 때문에 깊이를 구해야 했다.
처음에 반복문에 카운팅도 해보고 여러가지 시도를 해봤지만 잘 되지 않았다. 그래서 방법을 찾아보았는데 의외로 간단했다.
enqueue를 할 때 카운팅하며 같이 저장을 해주면 된다.
# 미로 탐색 제출코드 중 BFS 부분
queue = deque()
queue.append((0,0,1))
map[0][0] = '0'
count = 0
while queue:
# queue에서 빼오고 표시
p = queue.popleft()
n,m,c = p
## print(n,m)
if n == N-1 and m == M-1:
print(c)
break
# 갈 수 있는 곳 queue에 넣고 방문체크
if n < N-1 and map[n+1][m] == '1': #아래로 한칸
queue.append((n+1,m,c+1))
map[n+1][m] = '0'
if m < M-1 and map[n][m+1] == '1': #오른쪽 한칸
queue.append((n,m+1,c+1))
map[n][m+1] = '0'
if n > 0 and map[n-1][m] == '1': #위로 한칸
queue.append((n-1,m,c+1))
map[n-1][m] = '0'
if m > 0 and map[n][m-1] == '1': #왼쪽 한칸
queue.append((n,m-1,c+1))
map[n][m-1] = '0'2차원 공간에서의 BFS
위와 같은 2차원 공간의 탐색 문제를 많이 접할 수 있는데 이를 그래프의 관점에서 보고 BFS로 구현할 수 있다. (특히 최단거리 문제)
일반적인 N*M의 2차원 공간이 주어진다면, 각 칸이 노드이고 상하좌우로 양뱡향 연결이 되어 있는 것으로 생각할 수 있다.
구현 방법
각 상하 좌우의 범위가 인덱스를 넘지 않는지를 먼저 판단하여 접근 여부를 확인하고, 그 다음 갈 수 있는 곳인지를 판단(방문여부 판단)한 뒤 갈 수 있다면 queue에 넣고 방문 체크를 한다.
방문 체크 방법
이 때 방문 체크를 어떤식으로 저장할지도 중요해지는데 visited에 그냥 좌표를 넣을 경우 또 탐색을 해야하기 때문에 방문 여부를 탐색하는 시간복잡도가(V*E)가 된다.
이를 최적화 하기 위해, 미리 2차원 공간을 만들어 방문 여부를 체크하면 시간복잡도를O(1)로 줄일 수 있다. 위 같은 미로문제에는 2차원 공간이 미리 주어져 있기 때문에 이를 이용하여 체크하면 된다.
사실 이건 2차원 공간 뿐만 아니라 모든 그래프에 적용할 수 있다.
정리
- 방문 체크는 enqueue와 동시에 하자
- enqueue 동작은 deque의 popleft()를 사용하자
- 경우에 따라 set을 잘 활용하자
- 깊이는 enqueue시 카운팅 하여 구할 수 있다
- 2차원 공간도 그래프로 볼 수 있다
- 시간이 오래 걸린다면 방문체크에 메모리를 적극 활용하자
지금까지 BFS문제를 풀면서 알게된 점에 대해서 정리를 해봤다. 아직 많은 문제를 풀어보진 않았지만 그래도 BFS문제를 푸는법에 대해서는 대략적으로 알게된 것 같다.
다음에는 동적 프로그래밍 유형의 문제를 풀어보고 정리를 해봐야겠다.
잘못된 정보가 있으면 언제든지 지적해주시길 바랍니다!🐥
