(Python/LV2) 게임 맵 최단거리

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

풀이:

from collections import deque

def solution(maps):
    N, M = len(maps) , len(maps[0])
    visited = [[-1]*M for _ in range(N)]
    visited[0][0] = 1
    move = [(0,1), (0,-1),(-1,0),(1,0)]

    q = deque([(0,0)])

    while q:

        x, y = q.popleft()
        if x == N-1 and y == M - 1:
            return visited[x][y]
        for a, b in move:
            dx, dy = x+a , y+b # 들어갈 곳
            if N > dx >=0 and M > dy >=0 and visited[dx][dy] == -1 and maps[dx][dy] == 1:
                q.append((dx,dy))
                visited[dx][dy] = visited[x][y] + 1

    return -1

 

오늘 처음 친구한테 배워서 그대로 연습한 bfs 

 

visited에 똑같은 판을 -1로 만들어준다. -1은 안갔기 때문에 -1 을 해주고

시작점 [0][0]은 밟은거니깐 1로 해준다

 

move 는 상하좌우 를 리스트에 튜플로 넣어둠

 

 

캐릭터가 있는 부분에서 위로도 갈수있고 아래로도 갈수있다.

while q 할때 위로가는것과 우로 들어가는것 두개가 된다는것이다,

캐릭터 자리가 7일때 위에랑 오른쪽이 8 되고 쭊쭊 나가다가

 

이 캐릭터위치 왔을때 9이고 바로 윗칸은 12 이다

밑으로 내려가고 싶어도 for문 밑에 조건문에 이미 방문했던 곳 이기 때문에 방문하지 않는다.

 

와일문을 돌다가 N-1,M-1 에 도착하면 그때 방문한갯수 리턴하면 된다