[BOJ] 17070 파이프 옮기기 1 (Java)

1. 문제 링크

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

17070번: 파이프 옮기기 1

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

17069번: 파이프 옮기기 2

 

2.1. 접근법 (DFS)

1.

가로 방향: direction 0

세로 방향: direction 1

대각선 방향: direction 2

 

2.

가로 방향으로 놓인 (1, 2)에서 dfs 탐색을 시작해서 (n, n)에 도달하면 ans 값을 1씩 증가시키기

 

3.

dfs(x, y, direction): (x, y)에 도착했는데 파이프 방향이 direction임

direction에 따라 놓을 수 있는 파이프 방향을 설정해줌

대각선 방향으로 파이프를 놓을 경우, board[x + 1][y + 1]뿐만 아니라 board[x][y + 1]과 board[x + 1][y]도 빈 칸이어야 함

 

2.2. 접근법 (Dynamic Programming)

17069번 파이프 옮기기 2 문제인 경우, 시간 제한이 1초에서 0.5초로 줄어들었으며 N의 최댓값이 16에서 32로 증가했다.

따라서 int 대신 long으로 board의 타입을 변경하고 bottom-up 방식의 DP를 사용해서 풀었다.

 

1.

long[][][] dp = new long[3][n + 1][n + 1]

[0][x][y]인 경우, (x, y)에 가로 방향으로 파이프가 놓일 수 있는 경우의 수

[1][x][y]인 경우, 세로 방향

[2][x][y]인 경우, 가로 방향

그러므로 dp[0][1][2] = 1로 초기화해주었다.

 

2.

이중 for문을 순회하며 dp[][][]를 채워주었다.

 

board[i][j]가 벽인 경우 continue하고

방향에 따라 (i, j)에 도달할 수 있는 경우의 수를 합하여 dp[][i][j]에 넣어주었다.

 

가로 방향인 경우,

이전 위치 (i, j -1)에서 가로, 대각선 방향으로 파이프가 놓인 경우의 합

 

세로 방향인 경우,

이전 위치 (i - 1, j)에서 세로, 대각선 방향으로 파이프가 놓인 경우의 합

 

대각선 방향인 경우,

이전 위치 (i - 1, j -1)에서 가로, 세로, 대각선 방향으로 파이프가 놓인 경우의 합

단, 대각선 방향은 (i - 1, j)와 (i, j - 1)이 빈 칸인 경우만 (i, j)에 파이프를 놓을 수 있기에 if문을 걸어주었다.

 

3.

답은 (n, n)에 가로, 세로, 대각선 방향으로 파이프를 놓을 수 있는 경우의 수의 합이므로

dp[0][n][n] + dp[1][n][n] + dp[2][n][n]을 출력했다.

 

3.1. 코드 (DFS)

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

// // 파이프 옮기기 1

public class BJ17070_2 {

    static int n;
    static long ans;
    static boolean[][] board;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        board = new boolean[n + 1][n + 1];

        StringTokenizer st;
        for(int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= n; j++) {
                if(st.nextToken().equals("1")) board[i][j] = true;
            }
        }

        dfs(1, 2, 0);
        System.out.println(ans);
    }

    private static void dfs(int x, int y, int direction) {

        if(x == n && y == n) {
            ans++;
            return;
        }

        if(direction != 1 && y + 1 <= n && !board[x][y + 1]) {
            dfs(x, y + 1, 0);       // 가로 방향
        }
        if(direction != 0 && x + 1 <= n && !board[x + 1][y]) {
            dfs(x + 1, y, 1);       // 세로 방향
        }
        if(x + 1 <= n && y + 1 <= n && !board[x + 1][y + 1] && !board[x][y + 1] && !board[x + 1][y]) {
            dfs(x + 1, y + 1, 2);   // 대각선 방향
        }
    }
}

 

3.2. 코드 (Dynamic Programming)

17070번 파이프 옮기기 1에 제출해도 통과함 (dp의 타입을 long이 아닌 int로 변경해도 무관)

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

// 파이프 옮기기 2

public class BJ17069 {

    static int n;
    static boolean[][] board;
    static long[][][] dp;       // 가로: dp[0][x][y], 세로: dp[1][x][y], 대각선: dp[2][x][y]

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        board = new boolean[n + 1][n + 1];
        dp = new long[3][n + 1][n + 1];
        dp[0][1][2] = 1;

        StringTokenizer st;
        for(int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= n; j++) {
                if(st.nextToken().equals("1")) board[i][j] = true;
            }
        }

        solution();
        long ans = dp[0][n][n] + dp[1][n][n] + dp[2][n][n];
        System.out.println(ans);
    }

    private static void solution() {

        for(int i = 1; i <= n; i++) {
            for(int j = 2; j <= n; j++) {
                
                if(board[i][j]) continue;

                // 가로 방향
                dp[0][i][j] += dp[0][i][j - 1] + dp[2][i][j - 1];
                
                // 세로 방향
                dp[1][i][j] += dp[1][i - 1][j] + dp[2][i - 1][j];
                
                // 대각선 방향
                if(board[i - 1][j] || board[i][j - 1]) continue;
                dp[2][i][j] += dp[0][i - 1][j - 1] + dp[1][i - 1][j - 1] + dp[2][i - 1][j - 1];
            }
        }

    }
}