[프로그래머스] 게임맵 최단거리 - python3 BFS 풀이

 

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/1844?language=python3

프로그래머스

 

나의풀이

from collections import deque

visited = set()

def bfs(maps, y, x, n, m):
    global visited
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    
    queue = deque([(y, x)])

    while queue :
        current = queue.popleft();
        visited.add(current)
        for i in range(4) :
            nextY = current[0] + dy[i]
            nextX = current[1] + dx[i]
            if nextY < 0 or nextY >= n or nextX < 0 or nextX >= m :
                continue
            if maps[nextY][nextX] == 0 :
                continue
            if (nextY, nextX) not in visited :
                visited.add((nextY, nextX))
                queue.append((nextY, nextX))
                maps[nextY][nextX] = maps[current[0]][current[1]] + 1
    
    return maps[n - 1][m - 1]

def solution(maps):
    y = len(maps)
    x = len(maps[0])
    
    answer = bfs(maps, 0,0, y, x)
    if answer == 1 or answer == 0 :
        return -1
    return answer

탐색 문제에서 재귀를 사용한 DFS만 쓰다가, 마음속에 부담감으로만 있던 BFS로 처음 풀어본 문제! 재귀를 활용한 DFS로 풀었을 땐 시간 초과로 해결되지 않았었다.

 BFS 구현을 위한 큐는 덱을 사용해 구현하는 것이 list 보다 시간복잡도에서 효율적이다(deque의 .popleft()에서 크게 차이가 난다.)

느낀점

항상 C, C++만 사용해서 프로젝트를 진행하다가 python을 갑자기 사용하려니 문법 자체가 어색하다. 매일 코테문제 연습을 하며 자주 써야하는 라이브러리와 내부 메서드에 익숙해져보자!