[백준] 10164 격자상의 경로 (Python 파이썬)

https://www.acmicpc.net/problem/10164

10164번: 격자상의 경로

문제 설명

격자 맵과 한 지점이 주어졌을 때,

시작점 부터 그 지점을 거쳐 종료점까지 만들 수 있는 경로의 개수를 구하는 문제이다.

---

풀이 과정

경우의 수와 DP를 활용하는 문제이다.

초등학교 때 길 찾기 경우의 수를 배울 때 이러한 방법을 사용했을 것이다.

1	1	1	1
1	2	3	4
1	3	6	10

위 표처럼 가장 첫 칸과 첫 행을 1로 채우고

다음칸부터 왼쪽과 위쪽칸의 수를 더해 칸을 채워 나가는 방식이다.

 

이 규칙에, 문제에서 지정한 칸을 반드시 거치는 경로의 수를 구하는 문제이다.

예를 들어, 2행 2열 칸을 반드시 거쳐 지나가야 한다고 하자.

1	1
1	2

그럼 먼저, 2행 2열 칸 까지 가는데의 경우의 수를 구한 후

그 칸을 시작점으로 생각하여 도착점 까지의 경우의 수를 처음부터 구한다는 생각으로 구한 후

두 수를 곱해주면 될 것이다.

	1	1	1
	1	2	3

 

그래서 구한 2와 3을 곱하면 6이 되므로

2행 2열 칸을 반드시 거치는 경로의 수는 총 6이 된다.

 

이를 코드로 옮기면 다음과 같다.

n, m, k = map(int, input().split())
dp = [[0] * m for _ in range(n)]

if k == 0:
    for i in range(n):
        for j in range(m):
            if i == 0 or j == 0:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    print(dp[n - 1][m - 1])

else:
    x = (k - 1) // m
    y = (k - 1) % m

    for i in range(x + 1):
        for j in range(y + 1):
            if i == 0 or j == 0:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

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

    print(dp[x][y] * dp[n - 1][m - 1])

위 코드보다 조금 짧고 간결하게 구현을 하고 싶다면,

두 개로 나눈 for문 대신

(x, y)칸과 (n-x, m-y)칸의 값을 곱하는 방식으로 구현해도 된다.

( 어차피 (x, y)칸 부터 새로 시작하는 것과 같기 때문이다 )

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !