벽으로 막힌 격자에서 한 점에서 출발해 닿을 수 있는 칸을 전부 칠하는 문제다. 안쪽과 바깥쪽을 가르는 데 쓴다.
같은 문제를 큐와 재귀로 각각 짜보면 두 방식의 차이가 어디에 있는지 잘 보인다.
BFS
def bfs(que):
while que:
cur = que.pop(0)
if cur in traveled:
continue
traveled.add(cur)
r, c = cur
if r > 0 and matrix[r - 1][c] != '■':
matrix[r - 1][c] = '▧'
que.append((r - 1, c))
...
큐에서 꺼내고, 네 방향을 보고, 벽이 아니면 칠하고 큐에 넣는다. 큐가 빌 때까지 돈다.
DFS
def dfs(cur):
if cur in traveled:
return
traveled.add(cur)
matrix[cur[0]][cur[1]] = '▧'
r, c = cur
if r > 0 and matrix[r - 1][c] != '■':
dfs((r - 1, c))
...
큐에 넣는 대신 바로 부른다. 네 방향을 보는 부분은 글자 그대로 같다.
실제로 달라지는 곳
두 코드에서 다른 건 큐냐 재귀냐 하나다. 나머지는 그대로 옮겨진다. 큐를 스택으로 바꾸면 DFS가 되고, 재귀 호출은 호출 스택을 쓰는 것이므로 결국 같은 이야기다.
방문 표시를 언제 하느냐는 좀 다르다.
DFS는 함수에 들어오자마자 traveled 에 넣는다. 들어온 순간이 방문한 순간이다.
BFS는 큐에서 꺼낼 때 넣는다. 그래서 같은 칸이 큐에 여러 번 들어갈 수 있다. 위쪽 칸과 왼쪽 칸에서 각각 오른쪽 아래를 큐에 넣으면 그 칸이 두 번 들어간다. 꺼낼 때 if cur in traveled: continue 로 걸러내니 결과는 맞는다.
큐에 넣을 때 표시하면 중복이 안 생긴다. 여기서는 화면 표시용 matrix 는 넣을 때 칠하고, 방문 집합은 꺼낼 때 넣는 형태라 둘이 어긋나 있다.
칠하는 것과 기록하는 것
matrix 를 '▧' 로 바꾸는 것과 traveled 에 넣는 것을 둘 다 한다.
벽이 '■' 이고 지나간 자리가 '▧' 이므로, 사실 matrix 만 봐도 이미 지나갔는지 알 수 있다. 방문 집합 없이 matrix[r][c] == ' ' 인 칸만 들어가는 식으로도 된다.
칠하는 문자를 바꾸거나 원본을 보존해야 하면 그때는 집합이 따로 필요하다. 지금은 둘 다 있어서 겹친다.