[프로그래머스 lv 2] 게임 맵 최단거리(깊이/너비 우선 탐색(DFS/BFS))

아이디어 : 이코테 책에서 본 유형과 비슷하다. BFS방식으로 지나간 칸에 숫자를 1씩 더하면서 최종 거리를 구하면 될 것 같다.

 

# 첫 번째 시도

from collections import deque

def solution(maps):
    queue = deque([(0,0)])
    n = len(maps)
    m = len(maps[0])

    # 동서남북
    dx = [1,-1,0,0]
    dy = [0,0,-1,1]
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx >= 0 and ny >= 0 and nx < m and ny < n:
                if maps[nx][ny]==1:
                    queue.append((nx,ny))
                    maps[nx][ny] = maps[x][y] + 1
                       
    if maps[n-1][m-1]<=1:
        answer = -1
    else:
        answer = maps[n-1][m-1]
    return answer

 

테스트케이스는 넘겼으나 무수한 실패와 런타임에러의 향연에 다시 생각해봐야 할 것 같다.

 

# 두 번째 시도(성공)

from collections import deque

def solution(maps):
    answer = 0
    n,m = len(maps), len(maps[0])
    # 동서남북
    dx = [1,-1,0,0]
    dy = [0,0,-1,1]
    x,y=0,0
    queue = deque()
    queue.append((x,y))
    while queue:
        x, y = queue.popleft()
        for i in range(len(dx)):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= n or ny >= m or maps[nx][ny]==0:
                continue
            elif maps[nx][ny]==1:
                queue.append((nx,ny))
                maps[nx][ny]=maps[x][y]+1

    answer = maps[n-1][m-1]
    if answer==1:
        answer = -1
    return answer