[프로그래머스/Python] 게임 맵 최단거리

문제

프로그래머스 - 게임 맵 최단거리

해결 과정

• BFS로 풀기
• (0,0)에서 시작하고 동서남북 좌표를 확인하며
  • maps 범위 안에 있고, 1이라면 (벽이 아니라면)
  • visited에 거리를 저장한다.

시행착오

• 36.1점.. 왜 틀렸지🥲 -> visited 부분이랑 break을 지워줌

from collections import deque
def solution(maps):
    visited = [[0] * (len(maps[0])) for _ in range(len(maps))]
    return bfs(0,0,maps,visited)
def bfs(x,y,maps,visited):
    # 이동 횟수
    answer = 1
    # 동,서,남,북
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    # 행 n, 열 m
    n = len(maps)
    m = len(maps[0])        
    q = deque()
    q.append((x,y))
    visited[x][y] = 1
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if not visited[nx][ny] and maps[nx][ny] == 1:
                    q.append((nx,ny))
                    visited[nx][ny] = visited[x][y] + 1
                    maps[nx][ny] = 0
                    answer += 1
                    break

    return visited[-1][-1] if visited[-1][-1] else -1

• 구글링으로 힌트를 얻었다.

# 힌트 1: 방문처리하는 부분에 거리를 넣어라
visited[nx][ny] = visited[x][y] + 1

풀이

from collections import deque
def solution(maps):
    # 동,서,남,북
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    
    # 행 n, 열 m
    n = len(maps)
    m = len(maps[0])
    
    # 거리를 저장
    visited = [[0] * m for _ in range(n)]
    
    q = deque()
    
    # (0,0) 에서 시작
    q.append((0,0))
    visited[0][0] = 1
    
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] == 1:
                q.append((nx,ny))
                visited[nx][ny] = visited[x][y] + 1
                maps[nx][ny] = 0
    return visited[-1][-1] if visited[-1][-1] else -1