백준 10164번 - 격자상의 경로

문제

백준 10164번 - 격자상의 경로

---

아이디어

최대 N x M범위가 작아 DFS로 모든 경로를 탐색해도 시간 초과는 발생하지 않지만 DP배열을 사용한 반복문으로 효율적으로 해결할 수 있다.

1. 입력

int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());

int ox = -1, oy = -1;

if (k != 0) {
    ox = (k - 1) / m;
    oy = (k - 1) % m;
}

• N과 M, 그리고 O가 표시된 칸의 좌표 위치를 구한다.

2. DP 배열 초기화

//(x, y, 0) = (x, y) 위치에 O로 표시된 칸을 지나지 않은 경로 수
//(x, y, 1) = (x, y) 위치에 O로 표시된 칸을 지나간 경로 수
int[][][] dp = new int[n][m][2];

dp[0][0][0] = 1;

• 3차원 배열의 마지막 값 0과 1로 O로 표시된 칸을 지난 경우와 지나지 않은 경우를 관리한다.

3. 반복문으로 DP 배열 값 채우기

int[][] dir = {{1, 0}, {0, 1}};

for (int x = 0; x < n; x++) {
    for (int y = 0; y < m; y++) {
    
        //오른쪽 또는 아래로 이동
        for (int[] d : dir) {
        
            int nx = x + d[0];
            int ny = y + d[1];
            
            if (nx >= n || ny >= m) continue;
            
            //다음 칸이 O로 표시된 칸인 경우
            if (nx == ox && ny == oy) {
                dp[nx][ny][1] += dp[x][y][0];
            } else {
                dp[nx][ny][0] += dp[x][y][0];
                dp[nx][ny][1] += dp[x][y][1];
            }
        }
    }
}

• 이동 중 이동할 칸이 O로 표시된 칸이라면, 전까지 O를 지나지 않은 경로를 더해준다. (전이시킨다.)
• 일반 칸이라면 지난 경로, 지나지 않은 경로 그대로 경로를 더해준다.

4. 결과 출력

System.out.println(dp[n - 1][m - 1][(k == 0) ? 0 : 1]);

• k == 0이면 O를 지나지 않은 경로 수를 출력하고, 아니면 O를 지난 경로 수를 출력한다.

---

예상 시간 복잡도

• 예상 시간 복잡도 : O(N x M)

---

코드 구현 - 자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ_10164 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int ox = -1, oy = -1;

        if (k != 0) {
            ox = (k - 1) / m;
            oy = (k - 1) % m;
        }

        //(x, y, 0) = (x, y) 위치에 O로 표시된 칸을 지나지 않은 경로 수
        //(x, y, 1) = (x, y) 위치에 O로 표시된 칸을 지나간 경로 수
        int[][][] dp = new int[n][m][2];

        dp[0][0][0] = 1;

        int[][] dir = {{1, 0}, {0, 1}};

        for (int x = 0; x < n; x++) {
            for (int y = 0; y < m; y++) {

                //오른쪽 또는 아래로 이동
                for (int[] d : dir) {

                    int nx = x + d[0];
                    int ny = y + d[1];

                    if (nx >= n || ny >= m) continue;

                    //다음 칸이 O로 표시된 칸인 경우
                    if (nx == ox && ny == oy) {
                        dp[nx][ny][1] += dp[x][y][0];
                    } else {
                        dp[nx][ny][0] += dp[x][y][0];
                        dp[nx][ny][1] += dp[x][y][1];
                    }
                }
            }
        }

        System.out.println(dp[n - 1][m - 1][(k == 0) ? 0 : 1]);
    }
}

코드 구현 - 파이썬

n, m, k = map(int, input().split())

ox, oy = -1, -1

if k != 0:
    ox, oy = divmod(k - 1, m)

dp = [[[0, 0] for _ in range(m)] for _ in range(n)]

dp[0][0][0] = 1

for x in range(n):
    for y in range(m):

        for dx, dy in [(1, 0), (0, 1)]:
            nx = x + dx
            ny = y + dy

            if nx >= n or ny >= m:
                continue

            if (nx, ny) == (ox, oy):
                dp[nx][ny][1] += dp[x][y][0]
            else:
                dp[nx][ny][0] += dp[x][y][0]
                dp[nx][ny][1] += dp[x][y][1]

print(dp[n - 1][m - 1][0 if k == 0 else 1])