[백준10164번] 격자상의 경로 / Python3

문제

행의 수가 N이고 열의 수가 M인 격자의 각 칸에 1부터 N×M까지의 번호가 첫 행부터 시작하여 차례로 부여되어 있다. 격자의 어떤 칸은 ○ 표시가 되어 있다. (단, 1번 칸과 N × M번 칸은 ○ 표시가 되어 있지 않다. 또한, ○ 표시가 되어 있는 칸은 최대 한 개이다. 즉, ○ 표시가 된 칸이 없을 수도 있다.)

행의 수가 3이고 열의 수가 5인 격자에서 각 칸에 번호가 1부터 차례대로 부여된 예가 아래에 있다. 이 격자에서는 8번 칸에 ○ 표시가 되어 있다.

격자의 1번 칸에서 출발한 어떤 로봇이 아래의 두 조건을 만족하면서 N×M번 칸으로 가고자 한다.

• 조건 1: 로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있다. (즉, 대각선 방향으로는 이동할 수 없다.)
• 조건 2: 격자에 ○로 표시된 칸이 있는 경우엔 로봇은 그 칸을 반드시 지나가야 한다.

위에서 보인 것과 같은 격자가 주어질 때, 로봇이 이동할 수 있는 서로 다른 경로의 두 가지 예가 아래에 있다.

• 1 → 2 → 3 → 8 → 9 → 10 → 15
• 1 → 2 → 3 → 8 → 13 → 14 → 15

격자에 관한 정보가 주어질 때 로봇이 앞에서 설명한 두 조건을 만족하면서 이동할 수 있는 서로 다른 경로가 총 몇 개나 되는지 찾는 프로그램을 작성하라.

입력

입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으로 구분된다. K의 값이 0인 경우도 있는데, 이는 ○로 표시된 칸이 없음을 의미한다. N과 M이 동시에 1인 경우는 없다.

출력

주어진 격자의 정보를 이용하여 설명한 조건을 만족하는 서로 다른 경로의 수를 계산하여 출력해야 한다.

예제 입력 1

3 5 8

예제 출력 1

9

나의 풀이

이 문제는 주어지는 지도에서 동그라미가 쳐지는 곳을 잘 찾아서 지도를 나눈다음 두 개에서 나오는 경로를 곱해주면 되는 문제이다. 우선 k가 0이라는 말은 아무곳도 거치지 않는 다는 뜻으로 (1,1)에서 (n,m)으로 가는 경로의 수를 구하면 된다.

그렇지않으면 위에서 처럼 매겨지는 번호의 인덱스 값을 찾아내서 지도를 나누어야한다. 이 문제에서 핵심은 저거였다고 생각한다. k에 따라서 인덱스를 구하는 식을 일반화 시키면 아래와 같다.

# 왼쪽 위 지도
dotN1 = (k-1) // m + 1
dotM1 = k - (dotN1-1) * m

# 오른쪽 아래 지도
dotN2 = n - (dotN1-1)
dotM2 = m - (dotM1-1)

그럼 이제 중간 지점이 설정되었다. 그럼 dotN1,dotM2로 dp를 하나 만들고 dotN2,dotM2 로 또 다른 dp를 만들어 각각의 dp에서 '(1,1)에서 (n,m)까지 가는 경로의 수를 구해 서로 곱해주면 전체 경우의 수가 나온다.'

위에서 전체 경로의 수를 구해내는 방법을 살펴봤다면 이제 각 dp에서 경로의 수를 구하는 법을 보겠다. 이 문제는 인접한 오른쪽과 아래로만 움직일 수 있다고 한다. 그럼 현재의 위치에서 가능한 경로의 수는 위에서의 경로의 수와 왼쪽에서 경로의 수를 더해주면 된다. 식으로 쓰면 dp[i][j] = dp[i-1][j] + dp[i][j-1]이 된다.

코드

# 10164번 격자상의 경로
import sys

# 경로 수 구하는 함수
def find(y,x):
    dp = [[0 for _ in range(x+1)] for _ in range(y+1)]

    for i in range(1,y+1):
        for j in range(1,x+1):
            if i == 1 and j == 1:
                dp[i][j] = 1
                continue

            dp[i][j] = dp[i-1][j] + dp[i][j-1]

    return dp[y][x]

# main
n, m, k = [int(x) for x in sys.stdin.readline().split()]

if k == 0:      # 중간지점이 없는 경우
    print(find(n,m))

else:       # 중간지점이 있는 경우
    dotN1 = (k-1) // m + 1
    dotM1 = k - (dotN1-1) * m
    dotN2 = n - (dotN1-1)
    dotM2 = m - (dotM1-1)

    # 왼쪽 위 경로
    r1 = find(dotN1,dotM1)
    # 오른쪽 아래 경로
    r2 = find(dotN2,dotM2)

    print(r1*r2)