그래프를 리스트로 구현해서 탐색한다는게 왜이리 어려운지...
DFS는 일단 타고 내려가서 종료시점까지 재귀로 불러온다는 게 특징이지만 BFS는 deque를 사용해서 방문한 곳을 하나씩 점찍으며 내려간다.
BFS로 푸는 문제의 특징
한 칸 이동할 때마다 비용이 전부 1칸으로 같다면,
BFS는 가까운 칸부터 한 층씩 탐색하므로 처음 도착한 경로가 곧 최단거리가 됩니다.
즉,
DFS: 갈 수 있는 데까지 막 가봄 → 최단거리 보장 X
BFS: 거리 순서대로 탐색 → 최단거리 보장 O
BFS는 최단 거리를 보장하기에
BFS는 먼저 도착한 경로가 가장 짧다
기본 BFS 구조
from collections import deque
def solution(maps):
answer = 0
# 맵의 크기 측정
n = len(maps)
m = len(maps[0])
# 맵의 좌표 값이용 (방문 노드 처리)
visited = [[False] * m for _ in range(n)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def bfs(x,y):
q = deque()
q.append((x,y))
visited[x][y] = True
while q :
cx, cy = q.popleft()
# 현재 위치 (cx, cy)에서 상하좌우
for d in range(4):
nx = cx + dx[d]
ny = cy + dy[d]
# 맵밖을 나가지 않도록 조절
if 0<= nx < n and 0 <= ny < m:
# 방문 여부 파악 + 벽이 아닌 조건
if not visited[nx][ny] and maps[nx][ny] ==1:
# 방문 표시
visited[nx][ny] = True
# 이동할 다음 위치 큐에 저장
q.append((nx,ny))
bfs(0,0)
return answer하지만 이 문제에서는 최단 거리의 길이를 반환해야하기 때문에, 위치 저장과 더불어 거리저장도 함께 이루어 져야한다.
최단거리 수까지 출력하는 BFS
노드의 인자로 (큐에 들어갈 요소) 거리정보 추가
from collections import deque
def solution(maps):
n = len(maps)
m = len(maps[0])
visited = [[False] * m for _ in range(n)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def bfs(x,y):
q = deque()
q.append((x,y,1)) # 시작 칸도 포함 하므로 거리 1
visited[x][y] = True
while q :
cx, cy, dist = q.popleft() # 거리 정보도 같이 추출
# 도착했는지 여부 확인 (문제에서 n,m이 도착 지점이라고 제시)
if cx == n - 1 and cy == m - 1:
return dist
for d in range(4):
nx = cx + dx[d]
ny = cy + dy[d]
if 0<= nx < n and 0 <= ny < m:
if not visited[nx][ny] and maps[nx][ny] ==1:
visited[nx][ny] = True
# 한칸 이동 한 정보를 큐에 넣는데, 칸수 증가 +1
q.append((nx,ny, dist+1))
return -1 # 이동이 안되면 -1 리턴
return bfs(0,0)
- 노드를 거쳐가면서 추가적으로 필요한 정보가 있다면, 노드의 인자로 한개 더 만들면 된다.
- 함수의 return 문을 이용해 bfs 이후 최종 출력할 값을 지정한다.
