[Programmers] 게임 맵 최단거리

태환·2024년 3월 23일
0

Coding Test

목록 보기
141/151

📌 [Programmers] 게임 맵 최단거리

📖 문제

📖 예제

📖 풀이

from collections import deque

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

def BFS(x, y, maps):
    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 0<= nx<len(maps) and 0<=ny<len(maps[0]) and maps[nx][ny] == 1:
                maps[nx][ny] = maps[x][y] + 1
                queue.append((nx,ny))

def solution(maps):
    BFS(0, 0, maps)
    if maps[-1][-1] == 1:
        return -1
    else:
        return maps[-1][-1]

BFS를 활용하여 최단거리 문제를 해결할 수 있다.

profile
연세대학교 컴퓨터과학과 석사 과정

0개의 댓글