프로그래머스 Lv.3: 등굣길 풀이

이번 주차는 대망의 DP다. 사실 원래 순서대로 하면 더 나중인데 어떠한 이슈로 DP를 좀 앞당겨왔다.

 

문제 설명

프로그래머스

간단히 말하자면 n * m (ㅋㅋ) 모양의 격자가 있는데, 집은 (1,1)에 있고 학교가 (m,n)에 위치해 있다.

물에 잠긴 지역을 피해 집 → 학교로 가는 최단경로의 개수를 return 해야 하는 문제.

• 격자의 크기 m, n은 1 이상 100 이하인 자연수이고, m과 n이 모두 1인 경우는 없다.
• 물에 잠긴 지역은 0개 이상 10개 이하이고, 집과 학교가 물에 잠긴 경우는 없다.
• 오른쪽과 아래쪽으로만 움직일 수 있고, 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 해야 한다.

풀이 과정

처음엔 이걸 코드로 어떻게 구현하나 막막했는데, 그림 그려서 하나씩 확인해 보니 패턴을 찾을 수 있었다.

 

일단 첫 번째 깨달은 건 어차피 대각선으로 가는 경우는 없고, 오른쪽 아니면 아래쪽으로 이동밖에 없기 때문에 (1,1)에서 (m,n)까지 가는 길이 모두 최단경로라는 것이었다.

 

그런데 내가 구해야 하는 것은 그 경로의 개수. 그리드를 그려 각 위치에 도달하는 경로의 수를 적어보니, (i,j)까지 오는 방법은 (i-1,j)까지 오는 방법과 (i,j-1)까지 오는 방법을 더한 값과 같다는 걸 알 수 있었다.

 

이를 코드로 구현하면서 처음에 나는 그리드를 n * m 크기로 잡고, (첫 제출 때 런타임 에러가 떠서 질문 게시판을 보고 깨달은 사실은... 이 문제... m과 n 값, 그리고 puddles의 x, y 값 전부 역전으로 줬다. m * n 그리드가 아니라 n * m 그리드라는 것. puddles의 인덱스 0이 y값, 1이 x값이 라는 것. << 아니... 예시를 (2,2)로 줬는데 어떻게 알아. 그래서 게시판 보면 화가 가득함.) 출발 지점을 제외하고 첫 번째 row와 첫 번째 col은 다 1로 채우고, 각 지점의 값을 위에 있는 값 + 왼쪽에 있는 값을 더해서 계산하는 방식을 썼다.

 

그랬더니 틀렸는데, 이렇게 하면 집 바로 오른쪽, 바로 아래쪽이 침수 지역일 경우를 대비하지 못 하기 때문이다. 이 경우엔 집을 나갈 수가 없어서 0을 리턴해야 하는데 첫 줄을 다 1로 값을 채워 놨으니...

이 경우를 대비하기 위해서는 출발 지점만 1로 초기화 해두고, 위쪽이 막혀있는 지점은 왼쪽 값을(road[i][j] = road[i][j-1]), 왼쪽이 막혀있는 지점은 위쪽 값으로(road[i][j] = road[i-1][j]) 설정해야 한다.

 

이렇게 하니까 맞기는 했는데... 왼쪽이나 위쪽이 막혀있는 지점을 따로 처리하고 + 막혀있는 그 지점이 또 침수 지역일 경우(= -1일 때)도 처리해야 해서 조건문이 많았다. 과연 이게 최선일까? 절대 아니지. '다른 사람의 풀이'를 보고 답을 얻어 방법을 개선할 수 있었다.

 

문제는 '막혀있는 지점' 이다. 이 경우를 따로 처리하려 하니까 조건문이 많아진 거 아닌가? 그럼 막아두지 않으면 된다.

그러니까, 그리드를 너무 fit 하게 n * m으로 설정한 게 문제라는 거다. 크기를 (n + 1) * (m + 1)로 잡으면 쉽게 해결할 수 있다. 이러면 인덱스도 -1 해서 접근하지 않아도 되고. 유레카 발생. 왜 이 생각을 못 했을까?

 

그리고 다른 사람의 풀이에서 한 가지 더 유레카였던 것은... 나는 for 문 돌면서 지점 하나씩 확인할 때 침수된 곳이면 그냥 continue 쓰고, 위나 왼쪽이 침수된 곳이면 왼쪽의 값 또는 위쪽의 값을 채택하는 방식을 썼는데. (= 막혀있는 지점과 똑같이 처리. 이렇게 했던 이유는 진짜 종이에 그리면서 값을 채워 보니 그 값이길래... 너무 FM마냥 함) 이 지점을 0으로 변환해서 앞으로의 덧셈에 문제가 없도록 한 것...! 너무 센스 있는 풀이. 이렇게 하면 침수 지역도 일반 평지와 똑같은 로직으로 처리할 수 있어져서 조건문이 또 줄어든다.

 

인덱스 하나씩 더 크게 잡는 건 어떤 경우에 쓰면 되는지 이제 배웠으니 앞으로는 잘할 수 있을 것 같은데, 이 0으로 처리하는 건... 타고난 센스처럼 느껴진다.

 

 

참고로 문제 풀 당시에는 그리드 라는 단어를 생각 못 해서 road라는 변수명을 썼다. (사실 map으로 하고 싶었는데)

def solution(m, n, puddles):
    # 인덱스 에러 안 나도록 행열 1칸씩 추가 모두 0으로 초기화함
    road = [[0 for _ in range(m+1)] for _ in range(n+1)]
    
    # 구별을 위해 침수 지역을 -1로 표시
    for a,b in puddles:
        road[b][a] = -1
        
    # 인덱스 1부터 n번째까지 순회
    for i in range(1, n+1):
        for j in range(1, m+1):
            # (1,1)은 앞으로의 계산을 위해 0이 아닌 1로 표시
            if i == 1 and j == 1: road[i][j] = 1
            # 침수 지역이면, 덧셈에 영향 안 가도록 값을 0으로 변경
            elif road[i][j] == -1: road[i][j] = 0
            # (i,j)까지 오는 방법은 (i-1,j)까지 오는 방법과 (i,j-1)까지 오는 방법을 더한 값과 같다!
            else: road[i][j] = road[i-1][j] + road[i][j-1]
    return road[i][j] % 1000000007

 

Python으로 먼저 풀고... 해당 로직을 Swift로도 작성해 봤다. 근데 와중에 이 문제는 Swift를 지원하지 않는다.

func solution(m: Int, n: Int, puddles: [[Int]]) -> Int {
    var road: [[Int]] = []
    
    for _ in 0...n {
        road.append(Array(repeating: 0, count: m+1))
    }
    
    for puddle in puddles {
        road[puddle[1]][puddle[0]] = -1
    }
    
    for i in 1...n {
        for j in 1...m {
            if i == 1 && j == 1 {
                road[i][j] = 1
            }
            else if grid[i][j] == -1 {
                road[i][j] = 0
            }
            else {
                road[i][j] = road[i-1][j] + road[i][j-1]
            }
        }
    }

    return road[n][m] % 1000000007
}

print(solution(m: 4, n: 3, puddles: [[2,1], [1,2]])) // 4

 

답만 보면 쉬운데 직접 떠올리는 건 어려운 것 같다.

 

그래도 할수록 느는 것 같아서 좋다.