[백준 / BOJ] 17069번 : 파이프 옮기기 2 - JAVA

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

17069번: 파이프 옮기기 2

다이나믹 프로그래밍 DP

모든 경우의 수를 찾는 것이므로 DP를 사용하여 풀었다. 파이프가 두 칸을 차지할 수 있기 때문에, 파이프의 r 값이 가장 작은 칸, 만일 r이 같다면 c값이 가장 작은 칸을 기준으로 파이프의 개수를 세도록 했다.

 

어떤 칸 (i, j)에 파이프가 존재할 수 있는 경우는 세 가지이다.

1. (i, j + 1)도 빈 칸이어서 파이프를 가로로 둔다.
2. (i + 1, j)도 빈 칸이어서 파이프를 세로로 둔다.
3. (i, j + 1), (i + 1, j), (i + 1, j + 1)도 모두 빈 칸이어서 파이프를 대각선으로 둔다.

따라서 3차원 배열 pipe를 만들어 (r, c, 파이프가 놓인 타입)으로 개수를 세도록 했다.

 

그럼 각 타입 별 개수를 어떻게 찾을 수 있는가? 앞서 말한 빈 칸 조건을 제외한다면 다음과 같이 생각할 수 있다.

1. 가로 : pipe[i][j][0] = pipe[i][j - 1][0] + pipe[i - 1][j - 1][2]
      => (i, j - 1)에 가로로 놓을 수 있는 파이프의 개수 + (i - 1, j - 1)에 대각선으로 놓을 수 있는 파이프의 개수
2. 세로 : pipe[i][j][1] = pipe[i - 1][j][1] + pipe[i -1][j - 1][2]
      => (i - 1, j)에 세로로 놓을 수 있는 파이프의 개수 + (i - 1, j - 1)에 대각선으로 놓을 수 있는 파이프의 개수
3. 대각선 : pipe[i][j][2] = pipe[i][j - 1][0] + pipe[i - 1][j][1] + pipe[i - 1][j - 1][2]
      => (i, j - 1)에 가로로 놓을 수 있는 파이프의 개수 + (i - 1, j)에 세로로 놓을 수 있는 파이프의 개수 + (i - 1, j - 1)에 대각선으로 놓을 수 있는 파이프의 개수

 

이렇게 파이프의 경우의 수를 두게 되면, (N - 1, N - 1)에서 시작하는 파이프는 둘 수 없다(다른 칸으로 뻗어나갈 수 없으니까). 즉, 다른 칸에서 시작해 현재 칸에서 끝나는 파이프를 구해야 하기 때문에 답은 (i, j - 1)에 가로로 놓을 수 있는 파이프 + (i - 1, j)에 세로로 놓을 수 있는 파이프 + (i - 1, j - 1)에 대각선으로 놓을 수 있는 파이프의 개수를 구하면 된다.

 

전체 코드

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

// 시간 : 84ms
// 메모리 : 11864KB
public class Main {

	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[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());
			}
		}
		
		long[][][] pipe = new long[N][N][3]; // 0 : 가로, 1 : 세로, 2 : 대각선
		pipe[0][0][0] = 1;
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if(map[i][j] == 1) continue;
				// 현재 위치에 가로가 되려면
				if(j > 0 && j < N - 1 && map[i][j + 1] != 1) {
					pipe[i][j][0] += pipe[i][j - 1][0];
					if(i > 0) {
						pipe[i][j][0] += pipe[i - 1][j - 1][2];
					}
				}
				
				//  현재 위치에 세로
				if(i > 0 && i < N - 1 && map[i + 1][j] != 1) {
					pipe[i][j][1] += pipe[i - 1][j][1];
					if(j > 0) {
						pipe[i][j][1] += pipe[i - 1][j - 1][2];
					}
				}
				
				// 대각선
				if(i < N - 1 && j < N - 1 && map[i][j + 1] != 1 && map[i + 1][j] != 1 && map[i + 1][j + 1] != 1) {
					if(j > 0) {
						pipe[i][j][2] += pipe[i][j - 1][0];
						if(i > 0) {
							pipe[i][j][2] += pipe[i - 1][j - 1][2];
						}
					}
					if(i > 0) {
						pipe[i][j][2] += pipe[i - 1][j][1];
					}
				}
			}
		}
		
		System.out.println(pipe[N - 1][N - 2][0] + pipe[N - 2][N - 2][2] + pipe[N - 2][N - 1][1]);
	}

}