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

문제

링크

풀이

from collections import deque

def solution(maps):
    n, m = len(maps)-1, len(maps[0])-1
    load = deque()
    load.append([0, 0])
    while load :
        a, b = load.popleft()
        for p, q in [[-1, 0], [0, 1], [1, 0], [0, -1]] :
            if 0 <= a+p <= n and 0 <= b+q <= m and maps[a+p][b+q] == 1 :
                maps[a+p][b+q] = maps[a][b] + 1
                load.append([a+p, b+q])
    return maps[n][m] if maps[n][m] > 1 else -1             

처음에 코드를 아래와 같이 작성했었다.

from collections import deque

def solution(maps):
    n, m = len(maps)-1, len(maps[0])-1
    if maps[n][m-1] == 0 and maps[n-1][m] == 0 :
        return -1
    load = deque()
    load.append([0, 0])
    while load :
        a, b = load.popleft()
        for p, q in [[-1, 0], [0, 1], [1, 0], [0, -1]] :
            if 0 <= a+p <= n and 0 <= b+q <= m and maps[a+p][b+q] == 1 :
                maps[a+p][ b+q] = maps[a][b] + 1
                load.append([a+p, b+q])
    return maps[n][m]          

그랬더니 자꾸 오류가 발생했다..
분명히 개념 그대로 적용한 bfs 문제였기 때문에 더욱 알 수 없었다.
알고보니..return maps[n][m] 이 부분이 문제였다.
maps[n][m]이 1일 수도 있다는 것을 생각하지 못했다.

n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.

n, m이 모두 1인 경우가 없다고 했지 n, m 둘 중에 하나라도 1이 될 수 있다는 조건을 생각하지 않고 문제를 풀었더니 이런 문제가 발생했다.
만약 직선으로 이루어진 맵이고, ◻︎◼︎◻︎ 이런 모양이라고 하자.
그렇다면 n은 0이고 m은 2가 된다.

if maps[n][m-1] == 0 and maps[n-1][m] == 0 :
        return -1

이 부분에서 maps[n][m-1] == 0 에는 걸리겠지만, maps[n-1][m] == 0 는 maps[-1][2] == 0 이므로 조건문에 걸리지 않고 넘어가게 된다.
이런 부분들이 있어maps[n][m]이 1이 되는 경우가 있으므로 마지막에 return maps[n][m] if maps[n][m] > 1 else -1 이렇게 다시 걸러서 답을 출력해야 한다.