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

DEINGVELOP·2022년 8월 8일
0

📒 문제 정보




🔑  문제 풀이


BFS 활용

BFS를 활용한 풀이이다. 

from collections import deque

def solution(maps):
    x, y = 0, 0
    n, m = len(maps), len(maps[0])

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

    queue = deque()
    queue.append((x, y))

    while queue:
        x, y = queue.popleft()
        for di in range(4):
            nx = x + dx[di]
            ny = y + dy[di]
            if nx < n and ny < m and nx >= 0 and ny >= 0:
                if maps[nx][ny] != 0:
                    if maps[nx][ny] == 1:
                        maps[nx][ny] = maps[x][y] + 1
                        queue.append((nx, ny))

    if maps[n-1][m-1] in [0, 1]:
    	return -1
    else:
    	return maps[n-1][m-1]



💡  What I learned


이번 기회에 dfs, bfs 내용을 정리할 수 있었다. 특히, 이제는 왜 나는 'dfs 원툴'이다 / 'bfs 원툴'이다 라고들 이야기 하는지 깨달았다. 다만 각 알고리즘에 더욱 효율적인 알고리즘은 있으니 둘 다 자유자재로 사용할 줄 아는 것이 좋겠다.

문제를 딱 보면 이것이 DFS인지 BFS인지 딱 알아보는 안목이 생길 때까지 훈련이 필수적이겠다.

0개의 댓글