[프로그래머스] 등굣길 문제 풀이: BFS와 DP의 비교 - 파이썬

등굣길 문제 풀이: BFS와 DP의 비교

문제 설명

어떤 학교에서는 학생들이 집에서 학교로 갈 때, ( m \times n ) 크기의 격자 모양 마을을 지나야 합니다. 학생들은 오른쪽 또는 아래쪽으로만 이동할 수 있으며, 일부 칸에는 물웅덩이가 있어 지나갈 수 없습니다. 좌측 상단 ( (1,1) )에서 우측 하단 ( (m,n) )까지 갈 수 있는 최단 경로의 수를 구하세요. 결과는 ( 1,000,000,007 )로 나눈 나머지를 반환합니다.

제한사항

• 격자의 크기 ( m )과 ( n )은 ( 1 ) 이상 ( 100 ) 이하인 자연수입니다.
• 물웅덩이는 ( 0 )개 이상이며, 위치는 ([x, y]) 형태로 주어집니다.
• 시작점과 도착점은 물웅덩이가 아닙니다.

입출력 예

m	n	puddles	result
4	3	[[2, 2]]	4

BFS 풀이

코드

from collections import deque

# BFS 풀이
def solution(m, n, puddles):
    answer = 0
    queue = deque()
    visited = [[0 for _ in range(0, m+1)] for _ in range(0, n+1)]
    path = [[0 for _ in range(0, m+1)] for _ in range(0, n+1)]
    def bfs(start):
        queue.append(start)
        x, y = start[0], start[1]
        visited[y][x] = 1
        path[1][1] = 1
        while queue:
            x, y = queue.popleft()
            for i, j in [(1, 0), (0, 1)]:
                ni, nj = x+i, y+j
                if 0 <= ni < m+1 and 0 <= nj < n+1:
                    if [ni, nj] not in puddles:
                        if visited[nj][ni] == 0:
                            queue.append((ni, nj))
                            visited[nj][ni] = visited[y][x] + 1
                            path[nj][ni] = path[y][x]
                        elif visited[nj][ni] == visited[y][x] + 1:
                            path[nj][ni] = (path[nj][ni] + path[y][x]) % 1000000007
    bfs((1,1))
    answer = path[n][m]
    return answer

설명

• 탐색 방법: BFS를 사용하여 최단 거리를 우선으로 탐색합니다.
• 데이터 구조:
  • queue: 다음에 탐색할 좌표를 저장합니다.
  • visited: 해당 위치까지의 최단 거리를 저장합니다.
  • path: 해당 위치까지의 최단 경로 수를 저장합니다.
• 동작 과정:
  1. 시작점 ( (1,1) )에서 BFS를 시작합니다.
  2. 현재 위치에서 오른쪽과 아래쪽으로 이동할 수 있는지 확인합니다.
  3. 이동 가능한 위치라면, 그 위치까지의 최단 경로 수를 업데이트합니다.
  4. 이미 방문한 위치라도 최단 거리가 같다면 경로 수를 누적합니다.

시간 및 공간 복잡도

• 시간 복잡도: ( O(mn) )
  • 모든 노드를 최대 한 번씩 방문하므로 격자의 크기에 비례합니다.
• 공간 복잡도: ( O(mn) )
  • visited와 path 배열을 사용하여 공간을 사용합니다.

DP 풀이

코드

# DP 풀이
def solution2(m, n, puddles):
    dp = [[0] * (m+1) for _ in range(n+1)]
    dp[1][1] = 1
    for y in range(1, n+1):
        for x in range(1, m+1):
            if [x, y] in puddles:
                dp[y][x] = 0
                continue
            if x > 1:
                dp[y][x] += dp[y][x - 1] % 1000000007
            if y > 1:
                dp[y][x] += dp[y - 1][x] % 1000000007
    return dp[n][m] % 1000000007

설명

• 탐색 방법: 동적 프로그래밍(DP)을 사용하여 이전 상태를 기반으로 현재 상태를 계산합니다.
• 데이터 구조:
  • dp[y][x]: 위치 ( (x, y) )까지의 최단 경로 수를 저장합니다.
• 동작 과정:
  1. 시작점 ( (1,1) )에서 경로 수를 1로 초기화합니다.
  2. 각 칸을 탐색하며, 물웅덩이인 경우 0으로 설정합니다.
  3. 그렇지 않은 경우, 왼쪽 칸과 위쪽 칸의 경로 수를 더합니다.
  4. 계산된 경로 수를 현재 위치에 저장합니다.

시간 및 공간 복잡도

• 시간 복잡도: ( O(mn) )
  • 이중 반복문을 사용하여 격자의 모든 칸을 방문합니다.
• 공간 복잡도: ( O(mn) )
  • dp 배열을 사용하여 공간을 사용합니다.

두 가지 풀이의 비교

비교 항목	BFS 풀이	DP 풀이
시간 복잡도	( O(mn) )	( O(mn) )
공간 복잡도	( O(mn) )	( O(mn) )
실제 성능	상대적으로 느림	상대적으로 빠름
코드 복잡도	비교적 복잡	비교적 간단
특징	그래프 탐색 활용	이전 결과 활용

• 시간 및 공간 복잡도: 두 풀이 모두 동일하지만, BFS는 큐의 사용으로 인해 오버헤드가 발생할 수 있습니다.
• 실제 성능: DP 풀이가 배열 접근만으로 이루어져 있어 더 빠릅니다.
• 코드 복잡도: BFS는 여러 조건문과 자료 구조를 사용하여 복잡하지만, DP는 단순한 배열 계산으로 구현됩니다.

결론

등굣길 문제에서는 DP 풀이가 BFS 풀이에 비해 시간적, 공간적 효율성이 더 좋으며, 코드도 간결합니다. 최단 경로의 수를 구하는 문제에서는 이전 결과를 활용하는 DP 접근법이 효과적입니다.