[백준]5569: 출근 경로 - JAVA

[백준]5569: 출근 경로

5569번: 출근 경로

풀이

🪑 전형적인 DP유형의 문제라고 볼 수 있다. 그러나 교차로와 관련된 추가 조건이 있었기에 조금 더 생각을 요하는 DP문제였다.

 

📝 문제를 정리해 보자!

• 1, 1에서 W,H로 가는 모든 경로의 수를 찾는다.
• 이때 문제에서는 동쪽, 북쪽으로만 이동 가능하다고 되어 있다. 나는 뒤집어 생각하여 문제를 풀 것이기 때문에 동쪽, 남쪽으로만 이동이 가능하다고 생각하고 풀었다.
• 교차로를 돈 차량은 그 다음 교차로에서 다시 방향을 바꿀 수 없다

 

 

🙋‍♀️ DP스럽게 문제를 생각해 보자.

• 교차로라는 추가 조건이 없었다면 단순히 현재 좌표의 위치에서 왼쪽에서 오는 경우, 위쪽에서 오는 경우의 수를 누적하여 더해주듯이 풀면 된다.
• 이 문제도 비슷하다. 그러나 현재 교차로에서 방향을 변경할지에 따라 더해줘야 하는 값이 달라진다.
• 그래서 누적하여 더해줄 때, 현재 방향과 현재 교차로를 돌 것인지 여부를 함께 고려해 주어야 한다!

 

 

🔧 문제를 풀어 보자!

1. DP 배열을 만든 후 초기화 해 준다.
2. 배열에 모든 경우의 수에 해당하는 방법을 더해준다.
3. W, H좌표에 해당하는 모든 값을 더하여 결과를 출력한다.

 

 

🔹 DP 배열을 만든 후 초기화 해 준다.

• DP배열은 4차원으로 만든다. [X좌표][Y좌표][현재방향][교차로에서 방향을 바꾸는지 여부]
• DP배열을 아래와 같이 초기화 해준다. 

x/y	1	2	3	4
1	1	1	1	1
2	1
3	1

• 위와 같이 초기화 해 주는 이유는 1로 초기화된 좌표에 해당하는 경우의 수는 1가지 밖에 존재하지 않기에 2, 2좌표부터 DP를 진행해 주기 위해서이다.
• 초기화 하지 않고 DP연산에 해당 좌표를 포함해 버리면 모든 경우의 수를 다 더해주는 연산 때문에 원하지 않는 값도 포함된다.
• 색칠된 좌표는 오로지 경우의 수가 1가지 이므로 따로 처리를 해 준 것이다.
• 물론, 다른 방법으로 풀었다면 위와 같이 초기화 해 주지 않아도 된다.

 

 

🔹 배열에 모든 경우의 수에 해당하는 방법을 더해준다.

• DP[X][Y][오른쪽][꺾기X]일 때에는 DP[X - 1][Y][오른쪽][꺾기X] + DP[X - 1][Y][오른쪽][꺾기O]이다. 현재 꺾지 않을 것 이므로, 같은 방향에서 오는 경우의 수 중에 이전에 바로 꺾은 경우도 함게 더해준다.
• DP[X][Y][오른쪽][꺾기O]일 때에는 DP[X - 1][Y][위쪽][꺾기X]인 값을 저장해 주면 된다. 꺾어 주어야 하므로 방향을 변경해 주었으며, 변경된 방향에서 이전에 바로 꺾지 않았던 경우만 저장해 주어야 한다.
• 위쪽에서 오는 경우도 마찬가지로 계산해 주면 된다.

 

 

🔹 W, H좌표에 해당하는 모든 값을 더하여 결과를 출력한다.

• 결과값은 마지막 좌표인 DP[W][H]에 저장된다.
• 그러므로 4가지의 모든 경우의 수에 해당하는 값을 모두 더하여 출력해 주면 된다.

 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int mod = 100000;
 
    public static void main(String[] args) throws IOException {
        //입력
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String str = bf.readLine();
        StringTokenizer st = new StringTokenizer(str);
 
        int w = Integer.parseInt(st.nextToken());
        int h = Integer.parseInt(st.nextToken());
        //입력 끝
 
        int[][][][] dp = new int[w + 1][h + 1][2][2]; //3인덱스:방향, 0은 오른 1은 아래, 4인덱스:방향 변경 여부, 0은 꺾지 않은경우 1은 꺾은 경우
        for(int i = 1; i <= w; i++) {
            dp[i][1][0][0] = 1;
        } 
        for(int i = 1; i <= h; i++) {
            dp[1][i][1][0] = 1;
        }
 
        for(int i = 2; i <= w; i++) {
            for(int j = 2; j <= h; j++) {
                dp[i][j][1][0] = (dp[i][j - 1][1][1] + dp[i][j - 1][1][0]) % mod;
                dp[i][j][1][1] = dp[i][j - 1][0][0] % mod;
                dp[i][j][0][0] = (dp[i - 1][j][0][0] + dp[i - 1][j][0][1]) % mod;
                dp[i][j][0][1] = dp[i - 1][j][1][0];
            }
        }
        int result = (dp[w][h][0][0] + dp[w][h][0][1] + dp[w][h][1][0] + dp[w][h][1][1]) % mod; 
        System.out.println(result);
    }
}