큐·방문 집합과 BFS

꺼내기와 새 이웃 넣기가 기존 후보 뒤로 이어지는지 봅니다.

from collections import deque
q=deque(['start','right'])
print(q.popleft())
q.append('up')
print(list(q))

셀 수와 이동 횟수를 구분해 읽습니다.

"""Static grid planning; cells are (column,row), row 0 is the bottom."""
import math
from collections import deque

DIRECTIONS = ((1,0),(0,1),(-1,0),(0,-1))
EPS=1e-10

def validate_grid(grid):
    if not isinstance(grid,list) or not grid or not isinstance(grid[0],str) or not grid[0]:
        raise ValueError("BAD_MAP")
    width=len(grid[0])
    if any(not isinstance(row,str) or len(row)!=width or set(row)-set(".#?") for row in grid):
        raise ValueError("BAD_MAP")
    return width,len(grid)

def bfs(grid,start,goal):
    width,height=validate_grid(grid)
    def free(cell):
        return (isinstance(cell,(tuple,list)) and len(cell)==2 and
                all(type(v) is int for v in cell) and
                0<=cell[0]<width and 0<=cell[1]<height and grid[cell[1]][cell[0]]=='.')
    if not free(start) or not free(goal): return []
    start,goal=tuple(start),tuple(goal)
    queue=deque([start]);parent={start:None}
    while queue:
        here=queue.popleft()
        if here==goal:
            path=[]
            while here is not None:
                path.append(here);here=parent[here]
            return path[::-1]
        for dc,dr in DIRECTIONS:
            nxt=(here[0]+dc,here[1]+dr)
            if free(nxt) and nxt not in parent:
                parent[nxt]=here
                queue.append(nxt)
    return []

p=bfs(['...','...'],(0,0),(2,1))
print(p)
print(f'cells={len(p)} moves={len(p)-1}')

두 반환값을 후속 액션에서 서로 다르게 처리해야 합니다.

"""Static grid planning; cells are (column,row), row 0 is the bottom."""
import math
from collections import deque

DIRECTIONS = ((1,0),(0,1),(-1,0),(0,-1))
EPS=1e-10

def validate_grid(grid):
    if not isinstance(grid,list) or not grid or not isinstance(grid[0],str) or not grid[0]:
        raise ValueError("BAD_MAP")
    width=len(grid[0])
    if any(not isinstance(row,str) or len(row)!=width or set(row)-set(".#?") for row in grid):
        raise ValueError("BAD_MAP")
    return width,len(grid)

def bfs(grid,start,goal):
    width,height=validate_grid(grid)
    def free(cell):
        return (isinstance(cell,(tuple,list)) and len(cell)==2 and
                all(type(v) is int for v in cell) and
                0<=cell[0]<width and 0<=cell[1]<height and grid[cell[1]][cell[0]]=='.')
    if not free(start) or not free(goal): return []
    start,goal=tuple(start),tuple(goal)
    queue=deque([start]);parent={start:None}
    while queue:
        here=queue.popleft()
        if here==goal:
            path=[]
            while here is not None:
                path.append(here);here=parent[here]
            return path[::-1]
        for dc,dr in DIRECTIONS:
            nxt=(here[0]+dc,here[1]+dr)
            if free(nxt) and nxt not in parent:
                parent[nxt]=here
                queue.append(nxt)
    return []

print(bfs(['.'],(0,0),(0,0)))
print(bfs(['.#.'],(0,0),(2,0)))

grid는 팽창이 끝난 차단 지도이며 .만 통과합니다. start·goal은 [열,행] 정수 쌍입니다. 4방향을 오른쪽·위·왼쪽·아래 순서로 탐색합니다. 최초 발견 때 부모를 기록하고 시작·목표를 포함한 JSON 경로를 반환합니다. 경로 없음·범위 밖·차단 끝점은 [], 빈 동일 셀은 셀 하나입니다. 지도 형식 오류는 ERROR입니다. parent 연결 TODO를 고치고 제공한 큐와 출력 코드는 유지합니다.