[JAVA] BOJ 백준 17070 파이프옮기기1

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

17070번: 파이프 옮기기 1

DFS로도 DP로도 풀 수 있는 문제다!

VER. DP

💡 전체 로직
1. 문제에서 파이프를 놓는 방법이 그 전 파이프가 놓여진 형태에 따라 달라지기 때문에 현재 위치와 현재 상태에서 가능한 방법의 수를 저장해야 한다.
(즉, 끝 부분이 (x, y)에 있고 가로로 놓여진 상태로 파이프를 옮기는 방법의 수를 저장해야 함)
2. 3차원 배열을 통해 메모리제이션을 할 것이다. (0-가로, 1-세로, 2-대각선)
3. 문제에서 제시된 비어있어야 하는 공간을 유념하면서 DP 테이블을 갱신한다.

전체 코드

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

public class BOJ_17070{
	static int[][] map;
	static int[][][] d;
	public static void main(String[] args) throws Exception{
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(bf.readLine());
		d = new int[N][N][3]; // 0일때 가로, 1일때 세로, 2일때 대각선
		map = new int[N][N];
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
			for(int j=0; j<N; j++)
				map[i][j] = Integer.parseInt(st.nextToken());
		}	
		for(int i=0; i<N; i++)
			for(int j=0; j<N; j++)
				for(int k=0; k<3; k++)
					d[i][j][k] = -1;
		for(int y=0; y<N; y++) {
			d[0][y][1] = 0;
			d[0][y][2] = 0;
			d[y][0][0] = 0;
			d[y][0][2] = 0;
		}
		d[0][1][0] = 1; // 파이프의 처음 위치
		System.out.println(pipe_ver(N-1, N-1)+pipe_hor(N-1, N-1)+pipe_dia(N-1, N-1));
	}
	static int pipe_ver(int x, int y) {
		if(x < 0 || y < 0) return 0;
		if(d[x][y][0] != -1) return d[x][y][0];
		if(map[x][y] == 0) {
			return d[x][y][0] = pipe_ver(x, y-1) + pipe_dia(x, y-1);
		}
		return 0;
	}
	static int pipe_hor(int x, int y) {
		if(x < 0 || y < 0) return 0;
		if(d[x][y][1] != -1) return d[x][y][1];
		if(map[x][y] == 0) {
			return d[x][y][1] = pipe_hor(x-1, y) + pipe_dia(x-1, y);
		}
		return 0;
		
	}
	static int pipe_dia(int x, int y) {
		if(x < 0 || y < 0) return 0;
		if(d[x][y][2] != -1) return d[x][y][2];
		if(map[x][y] == 0 && map[x-1][y] == 0 && map[x][y-1] == 0) {
			return d[x][y][2] = pipe_dia(x-1, y-1)+pipe_hor(x-1, y-1)+pipe_ver(x-1, y-1);
		}
		return 0;
	}
}

DP 테이블을 어떻게 사용할 지 결정했으면 모든 DP가 그렇듯 풀이는 어렵지 않다!

한 줄 씩 살펴보자!

for(int i=0; i<N; i++)
		for(int j=0; j<N; j++)
			for(int k=0; k<3; k++)
				d[i][j][k] = -1;
	for(int y=0; y<N; y++) {
		d[0][y][1] = 0;
		d[0][y][2] = 0;
		d[y][0][0] = 0;
		d[y][0][2] = 0;
	}
d[0][1][0] = 1;
System.out.println(pipe_ver(N-1, N-1)+pipe_hor(N-1, N-1)+pipe_dia(N-1, N-1));

값이 저장되지 않은 것들은 -1로 세팅해준다.

또 불가능한 값들도 0으로 세팅하고 초기값을 준다.

정답은 가로, 세로, 대각선으로 놓인 것들의 합이기 때문에 더하여 출력한다.

static int pipe_ver(int x, int y) {
	if(x < 0 || y < 0) return 0;
	if(d[x][y][0] != -1) return d[x][y][0];
	if(map[x][y] == 0) {
		return d[x][y][0] = pipe_ver(x, y-1) + pipe_dia(x, y-1);
	}
	return 0;
}

이 함수는 x, y를 파이프의 끝으로 하면서 가로로 놓인 상태를 만드는 방법의 횟수를 return하는 함수이다.

문제를 보면 (x, y)가 벽인 경우에 파이프룰 놓을 수 없기 때문에 그 경우 0을 return 한다.

벽이 아닌 경우 왼쪽 자리를 끝으로 하는 가로, 대각선 파이프가 생성될 수 있는 방법의 개수 합을 저장하고 return한다.

나머지 두 함수도 위의 함수와 비슷하다.