프로그래머스(Programmers) : 등굣길 - python 풀이

❓프로그래머스 : 등굣길

📈 문제 요약

격자의 크기 m,n과 물이 잠긴 지역의 좌표를 담은 2차원 배열이 주어질 때 물에 잠긴 지역은 갈 수 없는 경우 집이 있는 좌표 (1, 1)에서 학교가 있는 좌표 (m, n) 까지 갈 수 있는 최단경로의 개수를 구하면 되는 문제

🤔 접근법

좌표계가 우리가 생각했던 (y, x) 좌표계가 아니라 (x, y) 좌표계로 모든 변수가 주어져서 많이 헷갈렸던 문제이다. 이런 경우 빡집중해서 헷갈리지 않는 것이 시간을 줄이는 유일한 방법인 것 같다.

우선 문제의 개념은 학창시절 수학 수업시간에서도 많이 봤던 유형의 문제이다. 오른쪽과 아래쪽으로만 이동할 수 있으므로 특정 칸 MAP[y][x]까지 이동할 수 있는 경로 수는 MAP[y-1][x] + MAP[y][x-1]이다. 즉, 점화식을 다음과 같이 쓸 수 있다.

$map[y][x] = map[y-1][x] + map[y][x-1]$

단, y 좌표가 0인 경우와 x좌표가 0인 경우는 (0, 0)에서 갈 수 있는 방법이 아래쪽으로 쭉, 오른쪽으로 쪽 한 가지의 방법 밖에 없을 것이다. 이 경우 수식을 다음과 같이 쓸 수 있다.

$map[1][x] = 1$

$map[y][0] = 1$

따라서 지도를 표시하는 MAP을 아래와 같이 정의할 수 있다.

MAP = [[1 if j == 0 or i == 0 else 0 for j in range(m)] for i in range(n)]

하지만 위와 같이 맨 윗줄과 맨 왼쪽 줄의 경로 수를 1로 정의하고 시작한다면 문제가 발생할 수 있다. 이 부분 때문에 시간이 많이 소요되었는데, 만약 맨 윗줄 혹은 맨 왼쪽 줄에 웅덩이가 있는 경우 웅덩이 뒷쪽으로는 최단 경로 1로 갈 수 없다. 즉, 돌아서 가야한다는 뜻인데, 해당 돌아서 가는 위치의 최단 경로 수는 구할 필요 없으므로 웅덩이 뒤에 좌표는 아래와 같이 0으로 처리해주었다.

    if puddles[0]:
        for x, y in puddles:
            MAP[y-1][x-1] = 'X'
            if x == 1:
                for r in range(y, n):
                    MAP[r][x-1] = 0
            if y == 1:
                for c in range(x, m):
                    MAP[y-1][c] = 0

맨 왼쪽 줄과 맨 윗줄을 위와 같이 정의 했으면 이제 다른 칸들을 위 점화식으로 채워 넣으면 된다. 단, 웅덩이로 표시된 좌표의 값은 갈 수 없는 곳이므로 0으로 만들어주고 연산을 수행해야 한다.

    for y in range(1, n):
        for x in range(1, m):
            if MAP[y][x] == 'X':
                continue
            up = 0 if MAP[y-1][x] == 'X' else MAP[y-1][x]
            left = 0 if MAP[y][x-1] == 'X' else MAP[y][x-1]
            MAP[y][x] = up+left
    return MAP[-1][-1]%1000000007

문제의 개념 자체는 간단한 문제였지만 헷갈리는 좌표계, 그리고 웅덩이가 첫 번째 라인에 있는 예외 케이스 덕에 시간을 많이 썼던 문제이다. 전자는 헷갈리지 않는 것이 중요하고, 후자는 미리 1로 값을 채워 넣지 않고 (0, 0)의 좌표부터 예외 처리를 통해 점화식으로 접근했다면 만나지 않았을 문제였을 것이라고 생각한다.

🔡 코드

def solution(m, n, puddles):
    MAP = [[1 if j == 0 or i == 0 else 0 for j in range(m)] for i in range(n)]
    
    if puddles[0]:
        for x, y in puddles:
            MAP[y-1][x-1] = 'X'
            if x == 1:
                for r in range(y, n):
                    MAP[r][x-1] = 0
            if y == 1:
                for c in range(x, m):
                    MAP[y-1][c] = 0

    for y in range(1, n):
        for x in range(1, m):
            if MAP[y][x] == 'X':
                continue
            up = 0 if MAP[y-1][x] == 'X' else MAP[y-1][x]
            left = 0 if MAP[y][x-1] == 'X' else MAP[y][x-1]
            MAP[y][x] = up+left
    return MAP[-1][-1]%1000000007