[Programmers] - 게임 맵 최단거리 (찾아라 프로그래밍 마에스터) with Python

📎 간략한 문제 정리

• 시작점 (0, 0)에서 도착점 (n-1, m-1)에 도착하기까지 최단거리를 구하고, 도착이 불가능할 경우 -1을 출력하는 메소드를 구현합니다.

 

📈 문제 분석

• 최단거리를 찾는 문제는 전형적인 BFS 문제로 BFS를 구현하며 도착점에 도착하면 그때까지의 depth를 출력하면 됩니다.

 

🙋‍♂️ 내가 처음 생각한 해결 방법

• 이 문제는 최단거리이기 때문에 BFS가 더 적합해보이지만 DFS로도 한번 같이 구현해보았습니다.

 

💻 풀이한 코드

# BFS
def solution_bfs(maps):
    from collections import deque
    n, m = len(maps), len(maps[0])
    visited = [[-1 for _ in range(m)] for _ in range(n)]
    visiting = deque([(0, 0)])
    visited[0][0] = 1
    dx, dy = [-1, 1, 0, 0], [0, 0, 1, -1]
    while visiting:
        x, y = visiting.popleft()
        for i in range(4):
            xx, yy = x + dx[i], y + dy[i]
            if 0 <= xx < n and 0 <= yy < m and maps[xx][yy] == 1 and visited[xx][yy] == -1:
                visited[xx][yy] = visited[x][y] + 1
                visiting.append((xx, yy))
    return visited[n-1][m-1]

# DFS
def solution_dfs(maps):
    from sys import setrecursionlimit
    setrecursionlimit(10**9)
    n, m = len(maps), len(maps[0])
    visited = [[10001 for _ in range(m)] for _ in range(n)]
    dx, dy = [-1, 1, 0, 0], [0, 0, 1, -1]
    def dfs(x, y, depth):
        visited[x][y] = depth
        for i in range(4):
            xx, yy = x + dx[i], y + dy[i]
            if 0 <= xx < n and 0 <= yy < m and maps[xx][yy] == 1 and visited[xx][yy] > depth+1:
                dfs(xx, yy, depth+1)
    dfs(0, 0, 1)
    if visited[n-1][m-1] == 10001:
        return -1
    return visited[n-1][m-1]

 

📝 해결 과정에서 만난 문제, 고민들

• BFS는 반복문을 통해 구현하고 DFS는 재귀를 통해 구현했습니다. 최단거리를 구하는 문제인만큼 당연히 BFS가 효율적이어서 정확성과 효율성 모두 통과했지만 DFS는 최단거리를 체크하기위해 모든 가능성을 탐색하므로 map의 크기가 커질수록 탐색의 경우가 많아져 정확성은 통과하여도 효율성은 통과하지 못했습니다. 특이한 점은 정확성 테스트 케이스 20번의 경우 오히려 DFS가 더 빨랐다는 점입니다. 0.01ms와 0.02ms이므로 오차 가능 범위이지만 무조건 BFS가 빠르지 않다는 점은 확인 가능했습니다. 메모리의 경우도 거의 차이가 없었습니다. 문제와는 상관없이 구현력을 높이기 위한 연습으로 두 방식으로 작성했습니다.

 

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