[백준] 17070번 - 파이프 옮기기 1 [Java]

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

 

[백준] 17070번 - 파이프 옮기기 1 [Java]

[백준] 17070번 - 파이프 옮기기 1 [Java]

[백준] 17070번 - 파이프 옮기기 1 [Java]

---

1.  아이디어

 

파이프 옮기기 2에서 경우의 수가 줄어든 문제로 동일하게 다이나믹 프로그래밍으로 해결할 수 있다.

Top-Down 방식과 Bottom-Up 방식 두가지로 해결했다.

([코딩테스트 준비/백준] - [백준] 17069번 - 파이프 옮기기 2 [Java])

---

2. 문제풀이

 

두 가지 방식 모두 오른쪽 끝단의 정보를 갖고 dp 테이블을 갱신했다. dp는 위치와 파이프가 놓인 방향까지 고려해야해서 3차원 배열로 행, 열, 방향을 모두 고려했다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main_TopDown_DP {

    private static int N;
    private static int[][] map;
    private static long[][][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dp = new long[N][N][3];

        long cnt = recur(0, 1, 0);
        System.out.println(cnt);
    }

    private static long recur(int r, int c, int d) {
        if (dp[r][c][d] != 0) return dp[r][c][d];
        if (r == N - 1 && c == N - 1) return 1;

        long cnt = 0;

        // 현재 방향이 세로 방향이 아니면 가로 방향 탐색
        if ((d != 1) && (c + 1 < N) && (map[r][c + 1] == 0)) {
            cnt += recur(r, c + 1, 0);
        }

        // 현재 방향이 가로 방향이 아니면 세로 방향 탐색
        if ((d != 0) && (r + 1 < N) && (map[r + 1][c] == 0)) {
            cnt += recur(r + 1, c, 1);
        }

        // 대각선 방향 탐색
        if ((r + 1 < N) && (c + 1 < N) && (map[r][c + 1] == 0) && (map[r + 1][c] == 0) && (map[r + 1][c + 1] == 0)) {
            cnt += recur(r + 1, c + 1, 2);
        }

        // 반환하면서 dp 테이블 갱신
        return dp[r][c][d] = cnt;
    }

}

import java.io.*;
import java.util.*;

public class Main_BottomUp_DP {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        int[][] map = new int[1 + N][1 + N];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 1; j <= N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        long[][][] dp = new long[1 + N][1 + N][3];
        dp[1][2][0] = 1;

        for (int i = 1; i <= N; i++) {
            for (int j = 3; j <= N; j++) {
                if (map[i][j] == 1) continue;

                dp[i][j][0] = dp[i][j - 1][0] + dp[i][j - 1][2];
                dp[i][j][1] = dp[i - 1][j][1] + dp[i - 1][j][2];

                if (map[i][j - 1] == 1 || map[i - 1][j] == 1) continue;

                dp[i][j][2] = dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2];
            }
        }

        System.out.println(dp[N][N][0] + dp[N][N][1] + dp[N][N][2]);
    }
}

---

4. 후기

 

- Top Down

- Bottom Up