BFS 유형 파헤치기

최단거리로 움직일 때, 경로가 존재하는가?

def bfs(start_pos):
    # BFS 탐색을 위한 초기화 작업을 수행합니다.
    initialize_visited()
    
    # 시작 위치를 queue에 넣습니다.
    start_x, start_y = start_pos
    
    visited[start_x][start_y] = True
    bfs_q.append((start_x, start_y))
    
    dxs, dys = [0, 1, 0, -1], [1, 0, -1, 0]

    # BFS 탐색을 수행합니다.
    while bfs_q:
        curr_x, curr_y = bfs_q.popleft()
        
        for dx, dy in zip(dxs, dys):
            new_x, new_y = curr_x + dx, curr_y + dy
            
            if can_go(new_x, new_y):
            	if new_x == goal[0] and new_y == goal[1]:
                	return True
                bfs_q.append((new_x, new_y))
                visited[new_x][new_y] = True
    return False

최단경로의 길이는 얼마인가?

step = [
	[0 for _ in range(m)]
    for _ in range(n)
]

def bfs(start_pos):
    # BFS 탐색을 위한 초기화 작업을 수행합니다.
    initialize_visited()
    
    # 시작 위치를 queue에 넣습니다.
    start_x, start_y = start_pos
    
    visited[start_x][start_y] = True
    step[start_x][start_y] = 0
    bfs_q.append((start_x, start_y))
    
    dxs, dys = [0, 1, 0, -1], [1, 0, -1, 0]

    # BFS 탐색을 수행합니다.
    while bfs_q:
        curr_x, curr_y = bfs_q.popleft()
        
        for dx, dy in zip(dxs, dys):
            new_x, new_y = curr_x + dx, curr_y + dy
            
            if can_go(new_x, new_y):
                bfs_q.append((new_x, new_y))
                # 최단경로 거리 표시
                step[new_x][new_y] = step[curr_x][curr_y] + 1
                visited[new_x][new_y] = True

최단경로는 그래서 뭔가?

from collections import deque

m, n = 5, 5
from_where = [[(-1, -1) for _ in range(m)] for _ in range(n)]

def bfs(start_pos, end_pos):
    visited = [[False] * m for _ in range(n)]
    # from_where 초기화
    for i in range(n):
        for j in range(m):
            from_where[i][j] = None

    sx, sy = start_pos
    ex, ey = end_pos

    q = deque()
    q.append((sx, sy))
    visited[sx][sy] = True
    from_where[sx][sy] = (sx, sy)  # 시작의 부모는 자기 자신으로 표시

    dirs = [(0,1),(1,0),(0,-1),(-1,0)]
    found = False

    while q and not found:
        x, y = q.popleft()
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if (0 <= nx < n and 0 <= ny < m) and not visited[nx][ny]:
                visited[nx][ny] = True        # <- 큐 넣기 전에 방문표시
                from_where[nx][ny] = (x, y)
                if nx == ex and ny == ey:
                    found = True              # 바깥 while까지 종료
                    break
                q.append((nx, ny))

    if not found:
        return []  # 경로 없음

    # --- 경로 복원: end -> start로 따라가서 뒤집기 ---
    route = []
    cx, cy = ex, ey
    while (cx, cy) != (sx, sy):
        route.append((cx, cy))
        cx, cy = from_where[cx][cy]
    route.append((sx, sy))
    route.reverse()
    return route

# 사용 예:
route = bfs((0, 0), (4, 4))
print(route)  # [(sx,sy), ..., (ex,ey)]