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

나는 지금 겁나 부족하다. 다른 사람들을 보면 문제를 읽고 나면 이 문제는 어떤 유형인지 바로 파악하고 문제 풀이를 시작하는데 나는 그걸 못한다. 그래서 일단 여러 문제를 부딛혀보고 있다. 이번엔 게임 맵 최단 거리를 풀어봤다. 시간을 정하고 풀다보니 결국 풀긴 풀었지만 오답이 나왔다. 일단 내 풀이

def solution(maps):
    startx = 0
    starty = 0
    endx = len(maps) - 1
    endy = len(maps[0]) -1
    if(len(maps) == 1 and len(maps[0]) == 1):
        return 1
    x = 0
    y = 0
    while True:
        if(x+1 <= endx and maps[x+1][y] != 0 and maps[x][y]+1 < maps[x+1][y]):
            x += 1
        elif(y+1 <= endy and maps[x][y+1] != 0 and maps[x][y]+1 < maps[x][y+1]):
            y += 1
        elif(x-1 >= startx and maps[x-1][y] != 0 and maps[x][y]+1 < maps[x-1][y]):
            x-=1
        elif(y-1 >= starty and maps[x][y-1] != 0 and maps[x][y]+1 < maps[x][y-1]):
            y-=1
        else:
            break

    if(maps[endx][endy] == 1):
        return -1
    else:
        return maps[endx][endy]

일단 얘가 이동은 하는데 카운트를 안 센다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 그래서 오류가 생겼다.

시간에 쫒기다보니 너무 급하게 생각했다.

 

풀이

이 문제는 BFS(너비 우선 탐색)의 queue를 사용하면 풀 수 있다. 

from collections import deque


def solution(maps):
    mx = [1, -1, 0, 0]
    my = [0, 0, 1, -1]

    queue = deque()
    queue.append([0, 0])

    while queue:
        now = queue.popleft()
        for i in range(4):
            nextx = now[0] + mx[i]
            nexty = now[1] + my[i]

            if (nextx >= 0 and nexty >= 0 and nextx < len(maps) and nexty < len(maps[0]) and maps[nextx][nexty] != 0):
                if (maps[nextx][nexty] == 1):
                    maps[nextx][nexty] = maps[now[0]][now[1]] + 1
                    queue.append([nextx, nexty])
    if (maps[len(maps)-1][len(maps[0])-1] == 1):
        return -1
    else:
        return maps[len(maps)-1][len(maps[0])-1]
    return answer

 

이때 maps의 값이 1일 경우에는 방문하지 않았다고 가정해 이전 위치에 있던 값에 1을 더한 값을 넣는다.

그리고 return 부분에 마지막 위치가 1일 경우에는 방문을 하지 않은거기 때문에 -1을 return하고 1이 아닐 경우에는 위치를 반환하게 된다. 

 

아직 알고리즘에 대한 개념이 부족해서 그런지 문제를 봤을 때 이 문제가 어떤 알고리즘을 사용하는지 파악하는 능력이 없다. 더 공부해야겠다.