BFS: 게임 맵 최단거리 구하기

from collections import deque
# 최단거리: BFS
def solution(maps):
    answer = 0

    n = len(maps)
    m = len(maps[0])
    
    visited = [[False]*m for _ in range(n)]
    q = deque()
    q.append((0, 0))

    # e,w,s,n
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    visited[0][0] = True  # me
    
    while q:
        y, x = q.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            
            # e/w/s/n 이동이 n*m 내부이고 maps에서 1인 경우(이동 가능)
            if 0<=nx<m and 0<=ny<n and maps[ny][nx]==1:
            	# 방문하지 않았으면 방문하기
                if not visited[ny][nx]:
                    visited[ny][nx] = True
                    q.append((ny, nx))	# 이동한 방향 append
                    maps[ny][nx] = maps[y][x]+1	# N번째 방문
                
                # 목표지점에 방문했으면 몇 번째 방문인지 return
                if visited[n-1][m-1]:
                    return maps[n-1][m-1]
    return -1

 

 

 

추가로 다중배열을 만들 때, 그냥 곱하면 안된다. (1차열은 가능)

[[False]*m]*n
[[False, False, False, False, False],
 [False, False, False, False, False],
 [False, False, False, False, False],
 [False, False, False, False, False],
 [False, False, False, False, False]]

[[False]*m for _ in range(n)]
[[False, False, False, False, False],
 [False, False, False, False, False],
 [False, False, False, False, False],
 [False, False, False, False, False],
 [False, False, False, False, False]]

이 둘은 보기에도 같아보이고, 비교했을 때도 True로 나오지만,

0,0으로 접근했을 때 완전히 다르게 작업한다.

 

 

 

 

 

 

 

 

for문으로 이중배열을 생성해준 경우, 원하는 인덱스로 접근이 가능했지만

배열을 다시 곱한 경우에는 visited[0][n]의 모든 경우에 값이 변했다.

 

 

 

 

 

 

 

 

 

 

 

 

다른 코드

from collections import deque

def solution(maps):
    x_move = [1, 0, -1, 0]
    y_move = [0, 1, 0, -1]

    x_h, y_h = (len(maps[0]), len(maps))
    queue = deque([(0, 0, 1)])

    while queue:
        x, y, d = queue.popleft()

        for i in range(4):
            nx = x + x_move[i]
            ny = y + y_move[i]

            if nx > -1 and ny > -1 and nx < x_h and ny < y_h:
                if maps[ny][nx] == 1 or maps[ny][nx] > d + 1:
                    maps[ny][nx] = d + 1
                    if nx == x_h - 1 and ny == y_h - 1:
                        return d + 1

                    queue.append((nx, ny, d + 1))

    return -1