[Python] 프로그래머스 Lv 3 - 등굣길

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

출처 : https://programmers.co.kr/learn/courses/30/lessons/42898

 

알고리즘

우선 길찾기는 기본적으로 순열/조합으로 풀 수 있다. 
그런데, 문제는 물 웅덩이가 존재한다는 것과 그것이 몇 개인지 모른다는 것이 가장 큰 문제이다.
따라서 순열/조합의 일반화는 절대 불가능하고, 직접 경우의 수를 컴퓨터가 세 줘야 할 것이다.

여기에서, DP로 풀어야 하는 문제임을 눈치챌 수 있다.

기본적으로 자신의 윗칸까지 온 경우의 수와, 좌측까지 온 경우의 수를 더하면 그 자리까지 가는 경우의 수가 될 것이다.

변수는 물웅덩이인데, 물 웅덩이로는 못 오니까 그 칸은 0으로 센다.

또한, 물웅덩이의 추가 변수가 있다. 가장 윗 줄과 가장 왼쪽 줄에 물웅덩이가 올 경우 그 옆 / 밑은 모두 갈 수 없기에 0으로 초기화를 해야 할 것이다.

또 하나, 좌표 세는 방식이 파이썬의 환경과 문제에서의 환경이 반대고 심지어 문제는 1칸을 더 세버린다.
매우 헷갈리니까, 조심해서 코드를 작성해야 한다.

이를 바탕으로 작성한 코드는 다음과 같다.

코드

def solution(m, n, puddles):
    # 좌표가 미칠듯이 헷갈리는 문제다. 곱게 한칸 늘려주자.
    map = [[1 for _ in range(m+1)] for _ in range(n+1)]
    
    # 1단계. 물 웅덩이 설치.
    for i in range(len(puddles)):
        y = puddles[i][0]
        x = puddles[i][1]
        map[x][y] = 0
    # 2단계 물 웅덩이 첫줄  x, y 밀기.
    x_judge = 1
    for i in range(1, m+1):
        if x_judge == 0:
            map[1][i] = 0
        else:
            if map[1][i] == 0:
                x_judge = 0
    
    y_judge = 1
    for i in range(1, n+1):
        if y_judge == 0:
            map[i][1] = 0
        else:
            if map[i][1] == 0:
                y_judge = 0
    # 3단계 경우의 수 계산.
    for i in range(2, m+1):
        for j in range(2, n+1):
            if map[j][i] != 0: # 물웅덩이 칸은 0으로 해야 한다. 응 못가.
                map[j][i] = (map[j-1][i] + map[j][i-1])
        
    answer = map[n][m] % 1000000007
    return answer