[BOJ] 17070 - 파이프 옮기기 1

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

난이도: 골드 5

사용언어: JAVA

 

풀이

이 문제는 다이나믹 프로그래밍으로 접근할 수 있습니다. 상황에 따라 옮길 수 있는 위치가 다 다르므로 (직각으로 꺾을 수 없다던지...), 배열을 3개 선언하여, 오른쪽 칸으로 보내줄 수 있는 경우의 수, 아래쪽 칸으로 보내줄 수 있는 경우의 수, 대각선으로 보낼 수 있는 경우의 수를 따로 저장하였습니다.

 

또한 벽이 있으면 이동할 수 없으므로, 해당 조건도 고려해주었습니다. 

 

예제를 예로 들어보겠습니다.

 

 

위와 같은 입력이 있으면, 3개의 배열은 다음과 같이 채워집니다.

 

 

참고로 계산의 편의를 위해 행렬의 네 변을 0으로 감싸주었습니다.

 

import java.io.*;
import java.util.StringTokenizer;
 
class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int N;
        N = Integer.parseInt(br.readLine());
        String s;
        StringTokenizer st;
        int[][] arr = new int[N + 2][N + 2];
        int[][] right = new int[N + 2][N + 2]; // 오른쪽으로 보내줄 수 있는 경우의 수
        int[][] down = new int[N + 2][N + 2]; // 아래쪽으로 보내줄 수 있는 경우의 수
        int[][] diag = new int[N + 2][N + 2]; // 대각선으로 보내줄 수 있는 경우의 수
        int i, j;
        for (i = 1; i <= N; i++) {
            s = br.readLine();
            st = new StringTokenizer(s);
            for (j = 1; j <= N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        if (arr[1][3] == 0) // 처음 파이프가 있는 공간은 오른쪽과 대각선으로만 밀 수 있음.
            right[1][2] = 1;
        if (arr[1][3] == 0 && arr[2][2] == 0 && arr[2][3] == 0)
            diag[1][2] = 1;
 
        for (i = 1; i <= N; i++) {
            for (j = 1; j <= N; j++) {
                if (arr[i][j] == 0) { // 벽이 아니면 실행
                    if (arr[i - 1][j] == 0) { // 바로 위 칸에서 받아올 수 있으면
                        down[i][j] += down[i - 1][j]; // 윗 칸의 아래칸으로 보내는 경우의 수를 아래쪽으로 보내주는 경우의 수에 합산
                        diag[i][j] += down[i - 1][j]; // 대각선으로도 줄 수 있으니 합산
                        if (arr[i - 1][j - 1] == 0 && arr[i][j - 1] == 0)
                            down[i][j] += diag[i - 1][j - 1]; // 대각선 방향에서 받아올 수 있으면, 그것도 합산
                    }
                    if (arr[i][j - 1] == 0) { // 왼쪽 칸에서 받아올 수 있으면
                        right[i][j] += right[i][j - 1]; // 오른쪽으로 보낼 수 있는 경우의 수에 합산
                        diag[i][j] += right[i][j - 1]; // 대각선으로도 줄 수 있으니 합산
                        if (arr[i - 1][j - 1] == 0 && arr[i - 1][j] == 0)
                            right[i][j] += diag[i - 1][j - 1]; // 대각선 방향에서 받아올 수 있으면, 그것도 합산
                    }
                    if (arr[i - 1][j] == 0 && arr[i][j - 1] == 0 && arr[i - 1][j - 1] == 0) {
                        diag[i][j] += diag[i - 1][j - 1]; // 대각선에서 받아올 수 있으면, 받아와서 합산
                    }
                }
            }
        }
        bw.write(String.valueOf(diag[N][N])); // (N,N)에 올 수 있는 경우의 수는 (N,N)에서 대각선으로 줄 수 있는 경우의 수와 같다.
        bw.flush();
    }
}