BFS(너비우선탐색)는 있냐? 없냐? 만 기억하면 된다! (Python)

Problem

BFS를 사용할 때에 가중치가 같다면 반드시 최솟값이 보장된다는 것이 이해가 안 갔다.

 

미로를 탐색한다고 했을 때

1. 막다른 길이 있을 수도 있고
2. 길이 여러 갈래로 나뉘어져있을 수도 있는데

이를 어떻게 확신할 수 있는 지 도무지 이해가 가지 않았다.

 

 

Searching

백준에서 BFS 중 가장 기본 문제로 유명한 미로 탐색 의 이미지를 가져와봤다.

2178번: 미로 탐색

 아래와 같은 미로에서 출발점으로부터 도착점까지의 최솟값을 구하는 문제다.

여기서 2가지만 기억하자.

1. 인접한 좌표 중에서 벽이 아닌, 지나갈 수 있는 길만 정점으로 고려하자.
2. 방문을 하면, 그 다음에 버린다.

 보다 쉬운 이해를 위해 이런 식으로 진행 방향을 숫자로 나타내어 보았다. 출발점을 0이라고 봤을 때, 도착점은 14가 최솟값이 된다. (문제에서는 출발점이 1이고 도착점이 15지만 다시 그리기 귀찮으니 넘어가도록 하자.)

 

 길을 지나갈 때마다 그 다음에 도달할 수 있는 인접한 곳에 길이 있는 지를 확인하고, 갈 수 없다면 삭제하는 방식으로 생각하니 머릿 속에 순서가 조금씩 그려지기 시작했다.

 

 아래 코드는 『이것이 코딩테스트다』 책에서 발췌하였다.

# 벽인 경우 무시
if graph[nx][ny] == 0:
	continue
      
# 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if graph[nx][ny] == 1:
	graph[nx][ny] = graph[x][y] + 1
	queue.append((nx, ny))

 긴 코드는 일단 생각하지 말고, 벽이냐 아니냐를 따져보자. 0일 경우는 벽이기 때문에 지나갈 수 없다. 길일 경우(1인 경우)에는 길을 지나갈 수 있으므로 한 칸을 움직인 것이 graph[x][y] +1 이다. 한 칸을 움직였으니, 서있는 위치를 큐에 저장한다. 이미 지나간 길은 신경 쓰지 말자.

# 현재 위치에서 네 방향으로의 위치 확인
for i in range(4):
	nx = x + dx[i]
	ny = y + dy[i]

# ========이 코드는 지금 고려하지 않는다.========
	# 미로 찾기 공간을 벗어난 경우 무시
	if nx < 0 or ny < 0 or nx >= n or ny >= m:
		continue
# ============================================
      
	# 벽인 경우 무시
	if graph[nx][ny] == 0:
		continue
      
	# 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
	if graph[nx][ny] == 1:
		graph[nx][ny] = graph[x][y] + 1
		queue.append((nx, ny))

 내가 위치해있는 곳에서 갈 수 있는 길을 탐색한다. 한 번에 2칸을 건너갈 수 없고, 벽을 뛰어넘어 길을 지나갈 수도 없다. 즉, 무조건 인접한 곳을 탐색해야한다. 길을 지나가려면 인접한 곳에 또 길이 있어야한다. 인접한 길은 상, 하, 좌, 우 최대 4개이다.

 nx = x + dx[i] 이 수식이 무엇인지 아직은 고민하지 말자. 이것만 기억하자. nx는 좌우 이동을 의미하고, ny는 상하 이동을 의미한다. 인접해 있는 상, 하 , 좌, 우의 길로 이동하겠다는 의미로 이해하면 된다.

# 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0] 
dy = [0, 0, -1, 1]

# ========이 코드는 지금 고려하지 않는다.============
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()
queue.append((x, y))

# 큐가 빌 때까지 반복
while queue:
	x, y = queue.popleft()
# =================================================

	# 현재 위치에서 네 방향으로의 위치 확인
	for i in range(4):
		nx = x + dx[i]
		ny = y + dy[i]

# ========이 코드는 지금 고려하지 않는다.============
		# 미로 찾기 공간을 벗어난 경우 무시
		if nx < 0 or ny < 0 or nx >= n or ny >= m:
			continue
# =================================================
      
		# 벽인 경우 무시
		if graph[nx][ny] == 0:
			continue
      
		# 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
		if graph[nx][ny] == 1:
			graph[nx][ny] = graph[x][y] + 1
			queue.append((nx, ny))

 상, 하, 좌, 우로 이동하기 위한 식의 의미가 여기서 나온다. 처음 출발 지점의 좌표가 (1, 1)이다. 우리가 가야할 도착 지점의 좌표는 (4, 6)이다. (1, 1)은 좌측 상단에 존재하고, (4, 6)은 우측 하단에 존재한다. 즉, 우측 하단으로 갈수록 숫자가 커지고, 좌측 상단으로 갈수록 숫자가 작아진다.

 

dx = [-1, 1, 0, 0] 

  상 (-1) / 하 (+1) / 좌 0 / 우 0

  상단으로 움직이면 x값이 줄어들고, 하단으로 움직이면 x값은 증가한다. 좌, 우는 x값과 상관이 없다.

 
dy = [0, 0, -1, 1]

  상 0 / 하 0 / 좌 (-1) / 우 (+1)

  좌측으로 움직이면 y값이 줄어들고, 우측으로 움직이면 y값은 증가한다. 상, 하는 y값과 상관이 없다.

 

 x축, y축이 아니다. 좌표라는 걸 다시 명시한다. 도착점을 향해 갈수록 값이 증가하고, 출발점과 가까울 수록 값은 줄어든다는 사실만 고려하면 헷갈리지 않을 수 있다!

 

 이제 for i in range(4) 의 의미가 이해될 것이다. 상, 하, 좌, 우로 길을 지나가는 행위를 0번째, 1번째, 2번째, 3번째 index에 저장을 해놓고 벽이냐, 아니냐를 확인하고 있는 것이다.

# BFS 소스코드 구현
def bfs(x, y):
  # 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
  dx = [-1, 1, 0, 0] 
  dy = [0, 0, -1, 1]

  # 큐(Queue) 구현을 위해 deque 라이브러리 사용
  queue = deque()
  queue.append((x, y))

  # 큐가 빌 때까지 반복
  while queue:
    x, y = queue.popleft()
    
    # 현재 위치에서 네 방향으로의 위치 확인
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      # 미로 찾기 공간을 벗어난 경우 무시
      if nx < 0 or ny < 0 or nx >= n or ny >= m:
        continue
      
      # 벽인 경우 무시
      if graph[nx][ny] == 0:
        continue
      
      # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
      if graph[nx][ny] == 1:
        graph[nx][ny] = graph[x][y] + 1
        queue.append((nx, ny))
  
  # 가장 오른쪽 아래까지의 최단 거리 반환
  return graph[n-1][m-1]

 그럼 이제 다 봤다. 아까 고려하지 않았던 부분에서 if nx < 0 or ny < 0 or nx >= n or ny >= m 코드가 이제는 이해가 될 것이다. 인접한 곳을 탐색하다보면 벽도 있지만, 끝에 도달하게 되면 미로 밖으로 튀어나가게 된다. 주어진 미로를 벗어나지 않아야하기 때문에 반드시 제한 조건을 걸어주어야한다.

 

 다시 이 그림을 생각해보자.

  현재 서있는 길을 큐에 넣어준다고 했다. 또한, 한번 지나친 길에 대해서는 고려하지 않는다고 했다. 그런데 여기서 의문이 생길 것이다. 지나친 길에 대해서 고려하지 않으면, 또다시 이전의 길을 탐색하면서 백스텝을 하게 되지 않을까? 방문 여부를 왜 체크하지 않을까?

 

 그 답은 바로 graph[nx][ny] = graph[x][y] + 1 이 코드에 있다. 백스텝을 하여, 다시 이전의 길을 탐색한다고 하더라도 상관이 없다. 위 그림에서 적은 숫자는 해당 좌표에 고정적으로 저장된다.

 

 graph[1][1]은 현재 1이 저장되어있다. 상, 하, 좌, 우를 탐색하여 graph[2][1]에는 2가 저장되었다. (위 그림에 적은 숫자에서 +1로 생각해주길 바란다.) graph[2][1] = graph[1][1] + 1 이다. graph[3][1]에는 3이 저장되었다. graph[3][1] = graph[2][1] + 1 이다. 즉, graph[3][1] = 2 + 1이다.

 

 한 칸씩 움직일 때마다 +1을 더해주지만 한 번 저장된 값은 변동되지 않는다.

 

 

Result

 그러므로, 최솟값을 비교할 필요도 없고 방문여부를 따로 표시할 필요도 없는 것이다. 가장 빠르게 도달하는 값이 최솟값이 될 수밖에 없는 이유다.

 

 

Reference

• https://nulls.co.kr/graph/141
• https://blog.naver.com/kks227/220574993422
• 『이것이 코딩테스트다』 서적

 

전체코드

from collections import deque

# N, M을 공백으로 구분하여 입력받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
	graph.append(list(map(int, input())))

# BFS 소스코드 구현
def bfs(x, y):
  # 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
  dx = [-1, 1, 0, 0] 
  dy = [0, 0, -1, 1]

  # 큐(Queue) 구현을 위해 deque 라이브러리 사용
  queue = deque()
  queue.append((x, y))

  # 큐가 빌 때까지 반복
  while queue:
    x, y = queue.popleft()
    
    # 현재 위치에서 네 방향으로의 위치 확인
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      # 미로 찾기 공간을 벗어난 경우 무시
      if nx < 0 or ny < 0 or nx >= n or ny >= m:
        continue
      
      # 벽인 경우 무시
      if graph[nx][ny] == 0:
        continue
      
      # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
      if graph[nx][ny] == 1:
        graph[nx][ny] = graph[x][y] + 1
        queue.append((nx, ny))
  
  # 가장 오른쪽 아래까지의 최단 거리 반환
  return graph[n-1][m-1]