[프로그래머스] 등굣길

문제 출처 : 프로그래머스 (https://school.programmers.co.kr/learn/courses/30/lessons/42898)

 

문제 설명

출처: 프로그래머스

🔎계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

 

해당 문제는 언듯 보면 BFS 문제인 것 같다는 생각이 바로 들게 만들어 놓은 문제였다. 하지만, 문제를 자세히 읽어보면 최단경로를 도출하는 것이 아니라 최단경로의 개수를 도출하는 문제였다.

 

나는 거짓말처럼 바로 BFS를 통해 문제 해결을 시도했고.. 처음에는 최단경로 문제인 줄 알고 일반적인 BFS를 구현했지만, 최단경로의 개수라는 것을 인지하고 바꾸어 시도해봤다.

<틀린 코드 보기>

from collections import deque
def solution(m, n, puddles):
    dx, dy = [0, 1], [1, 0]
    maps = [[0] * m for _ in range(n)]
    maps[0][0] = 1
	
    # x, y가 뒤바뀌어서 주어짐;;;
    for x, y in puddles:
        maps[y][x] = -1

    q = deque()
    q.append((0, 0))

    visit = set()
    visit.add((0, 0))

    while True:
        x, y = q.popleft()
        if x == n - 1 and y == m - 1:
            break

        visit.add((x, y))

        for i in range(2):
            nx, ny = x + dx[i], y + dy[i]
            if nx < n and ny < m and maps[nx][ny] != -1:
                q.append((nx, ny))
                maps[nx][ny] = (maps[nx][ny]+1) % (10**9+7)

#    print(*maps, sep='\n')

    return maps[-1][-1]

하지만 결과는 시간초과였다..

 

문제는 BFS를 통한 방문을 계산하게 되면 같은 좌표에 대한 연산을 방문할 수 있을 때 마다 하는 것이었다.

BFS를 통해 문제를 풀었을 경우:

BFS는 현재 좌표에서 이동가능한 경로들을 queue에 삽입하여 다음 loop에 꺼내 활용한다. 일반적으로는 visit을 표시하여 재방문을 하지 않지만, 해당 문제의 경우 (우, 하향) 으로 밖에 움직이지 않기 때문에 해당 좌표에 대한 모든 방문 경로가 최단거리임이 보장되었기에 visit할 때 마다 1씩 증가시키는 것으로 시도하였다.

 

하지만 문제에서 10**9 + 7을 나눈 몫으로 계산하라는 것에서 암시할 수 있듯, 위와 같은 방식으로 하면 한 좌표에 대한 방문 연산이 10**9 + 7 보다 더 크게 나올 수도 있는 것이었다.

따라서, 해당 문제의 분류인 다이나믹 프로그래밍으로 접근하여 문제를 해결하였다.

 

<정답 코드>

from collections import deque
limit = 10**9+7

def solution(m, n, puddles):
    maps = [[0]*m for _ in range(n)]
        
    for x, y in puddles:
        maps[y-1][x-1] = -1
    
    maps[0][0] = 1
    
    for i in range(1, n):
        if maps[i][0] != -1:
            maps[i][0] = maps[i-1][0]
    
    for i in range(1, m):
        if maps[0][i] != -1:
            maps[0][i] = maps[0][i-1]
    
    for i in range(1,n):
        for j in range(1,m):
            a, b = maps[i-1][j], maps[i][j-1]
            if maps[i][j] == -1:
                continue
            
            # 이 부분이 좀 지저분
            if a==-1:
                a=0
            if b==-1:
                b=0
            maps[i][j] = (a+b) % limit
    
    return maps[-1][-1]

 

접근은 다음과 같다.

문제에선 (우, 하향) 으로 밖에 움직이지 않기 때문에 특정 좌표에 대한 모든 방문 경로가 최단거리임이 보장된다.

 

1. 1행 또는 1열에 대해서는 방문할 수 있는 경우의 수가 1 밖에 없다. 

2. 1행 또는 1열에 존재하는 웅덩이들은 제외한다.

3. 2행 2열부터 n행m열까지 모든 경로(x, y)에 대해 (x-1, y), (x, y-1)의 값을 더해준다.

 

이렇게 점화식처럼 이전에 밟을 수 있었던 좌표들 간의 연산을 통해 진행된다는 점이 다이나믹 프로그래밍 스러운 문제였다.

 

조금 해매기도하고, 출제자의 실수(인지 의도인지 모르겠지만)가 있었기에 풀이하는데 꽤나 오랜 시간이 걸렸다.

하지만, 해당 문제처럼 방문 경로가 반드시 최단거리임이 보장이 될 때 DP로 문제를 해결하는 방법에 대해 배울 수 있어서 좋았다.