[programmers] 게임 맵 최단거리_BFS

[찾아라 프로그래밍 마에스터] 게임 맵 최단거리

link

내 풀이

• 방식 : deque를 활용한 BFS 방식으로 풀이
• 중복 방지 방법 : m 변수에 Set으로 지정하여 지나간 좌표 기록

📰code

from collections import deque

def solution(maps):
    target = (len(maps[0])-1,len(maps)-1) # x,y
    delta = ((0,1),(1,0),(0,-1),(-1,0)) 
    n,px,py = 1,0,0
    m = set()
    m.add(0)
    q = deque()
    q.append((n,px,py,m))
    
    while q :
        n,px,py,m = q.popleft()
        for dx,dy in delta:
            if 0<=px+dx<=target[0] and 0<=py+dy<=target[1] :
                if maps[py+dy][px+dx] == 1 and (py+dy)*(target[0]+1)+px+dx not in m:
                    if n >= target[0]+target[1]-1 and px+dx == target[0] and py+dy == target[1]:
                        return n+1
                    m.add((py+dy)*(target[0]+1)+px+dx)
                    q.append((n+1,px+dx,py+dy,m))
    return -1

다른 사람 풀이

• 방식 : deque를 활용한 BFS 방식으로 풀이
• 중복 방지 방법 : 변수가 아닌 Map에 직접 입력하는 방법(현재 이동한 거리를 Map에 입력)
  • 따른 변수를 가져갈 필요가 없음
  • 기록을 확인할 때 set 전체를 비교하는 것이 아닌 해당 좌표만 비교하기 때문에 속도적으로도 더 빠름

📰code

from collections import deque

def solution(maps):
    x_move = [1, 0, -1, 0]
    y_move = [0, 1, 0, -1]

    x_h, y_h = (len(maps[0]), len(maps))
    queue = deque([(0, 0, 1)])

    while queue:
        x, y, d = queue.popleft()

        for i in range(4):
            nx = x + x_move[i]
            ny = y + y_move[i]

            if nx > -1 and ny > -1 and nx < x_h and ny < y_h:
                if maps[ny][nx] == 1 or maps[ny][nx] > d + 1:
                    maps[ny][nx] = d + 1
                    if nx == x_h - 1 and ny == y_h - 1:
                        return d + 1

                    queue.append((nx, ny, d + 1))

    return -1

💡 수정 필요한 내용은 댓글이나 메일로 알려주시면 감사하겠습니다!💡