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

사용 언어 - Python3

문제 - 게임 맵 최단거리

프로그래머스

 

 

정답

이동할 때마다 칸의 값을 더해가는 BFS 문제 (정답 맞춘 여부 X)

정답 풀이

1. dx,dy 상하좌우 이동

2. deque()에 (x,y) 튜플형태로 append

한 칸 이동하면, queue에 입력되고 while문으로 popleft된다.

3. queue가 없을 때까지 while문 반복

상하좌우로 이동 nx,ny

이동한 값이 0보다 작거나 len(maps)를 벗어나면 무시한다. continue

이동한 맵 값이 0이라면 무시한다.

1일 경우, 지금까지의 maps의 값과 1을 더해준다. queue에 (nx,ny)를 새롭게 append한다.

-> 마지막까지 간 후에, 현재까지의 경로값을 다 더한 값을 return한다.

4. bfs(0,0)부터 시작한다.

5. 만약 마지막까지 가지 못했다면, maps[len(maps)][len(maps[0])-1] 값이 원래값 그래도 1일 것이다.

1일 경우, -1을 return하고 아니면 answer값을 출력한다.

from collections import deque
def solution(maps):
    answer = 0

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    def bfs(x, y):
        queue = deque()
        queue.append((x, y))
        
        while queue:
            x, y = queue.popleft()

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                
                if nx < 0 or nx >= len(maps) or ny < 0 or ny >= len(maps[0]): 
                    continue

                if maps[nx][ny] == 0:  
                    continue

                if maps[nx][ny] == 1:
                    maps[nx][ny] = maps[x][y] + 1
                    queue.append((nx,ny))
                    
        return maps[len(maps)-1][len(maps[0])-1]
    
    answer = bfs(0,0)
    return -1 if answer == 1 else answer

---

레퍼런스

• 정답 참고

[오답노트 | 파이썬] 프로그래머스 - 게임 맵 최단거리

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부