[백준 17069] 파이프 옮기기 2 C++ (Top-down 방식)

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

17069번: 파이프 옮기기 2

파이프 옮기기 1에 이어

이번에는 파이프 옮기기 2를 풀이하려고 합니다.

문제풀이

앞에서 나온 '파이프 옮기기 1'의 경우, 출력 조건에 '방법의 수는 항상 1,000,000보다 작거나 같다.'의 조건이 있어 1초 이내로 다 풀 수 있는 문제였습니다. 브루트 포스로 경우의 수를 다 지정하여 갈 수 있는 모든 방법을 다 탐색하면 됐었습니다.

 

하지만, 이번에는 입력 값이 무려 32X32가 최대값이고, 출력 값에도 제한이 없습니다. 즉, 결과 값이 1억이 넘어갈 수 있고, 심지어는 결과 값이 10억이 넘어 갈 수 있기 때문에 자료형도 int가 아닌 long long을 사용해야 할 것같은 생각이 들었습니다.

 

먼저, 다이나믹 알고리즘에 대해 설명하자면, 큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말입니다. 즉, 계산 했던 값들을 배열이나 저장공간에 저장하여 그 값을 다시 재사용할 수 있습니다. 

 

다이나믹에는 

Top-down방식과 Bottom-up 방식이 있습니다.

1. Top-down 방식 

큰문제를 작은문제로 나누고, 작은문제를 풀고 큰문제를 푸는 순으로 갑니다.

재귀 호출을 이용하는 푸는 방식을 Top-down 방식이라고 합니다.

 

2. Bottom-up 방식

문제를 크기가 작은 문제부터 차례대로 풀고, 문제의 크기를 조금씩 크게 만들면서 문제를 점점 푸는 형식.

그래서, 작은 문제를 풀면서 왔기 때문에, 큰 문제를 항상 풀 수 있어야 합니다. 이런 매커니즘을 계속 반복하여 가장 큰 문제를 풀 수 있어야 합니다. 

Bottom-up 방식의 경우 아래 링크를 참고 해주시기 바랍니다.

https://rolypolytoy.tistory.com/18

[백준 17069] 파이프 옮기기 2 C++ (Bottom-up 방식)

 

 

 

제가 푼 방식은 Top-down방식을 이용하여 풀었습니다. 즉, 재귀 호출을 이용하여 푸는 방식입니다.

재귀를 이용한 이유는, 문제에서 나오는 1,2부터 좌표가 시작하여 N, N 좌표까지 나와야하고, 각 조건에 맞게 다시 함수를 호출하여 깊이 탐색을 해야하기 때문입니다. 이때 깊이 탐색으로 N, N 좌표가 나올 때가지 탐색하면서 N,N 좌표를 만났을 때 return을 해주면서 왔던 길의 횟수들을 누적시켜 DP 다이나믹 배열에 저장해주면 됩니다. 

 

저는 DP[x][y][dir] 배열을 만들었고, x,y,dir가 의미하는 것은 x,y 가 dir방향에서 N, N까지 가는데 갈 수 있는 모든 경우의 수를 의미합니다. 그 뒤에 dir는 시작하는 방향을 의미하고요!

 

이렇게 한다면 만약 5,5가 N,N 이라면, (4, 4), (3, 4), (4, 3), (3, 3), (2, 3), (3, 2) ......등등 이렇게 작은 문제들을 나누어서 누적하여 (1, 2)까지 해결한다면, 결국, 결과값은 (1,2)에서 N,N까지 갈 수 있는 모든 경우의 수를 다 구할 수 있습니다.

 

앞에서 '파이프 옮기기 1' 과 비교했을 때 '파이프 옮기기 2'는 시간이 현저하게 줄어들게 됩니다. 그 이유는 '파이프 옮기기 1'에서는 계산 했던 값을 중복해서 계산하기 때문입니다. (1, 2)에서 (10,10)인 N,N까지 갈 때, 예를 들어, 중간에 (3, 3)을 지나치게 되는데, 각 각 경우의 수를 계산할 때마다 (3,3)을 지나치게 되면 다시 DFS으로 깊이 탐색을 해서 N,N까지 경우의 수를 구하기 때문에 중간에 (3,3) 을 여러번 계산하게 됩니다. 사실, 3,3에서 N,N으로 가는 방법의 수는 정해져 있기 때문에 DP배열에다가 DP[3][3][dir]로 갈 수 있는 방법들을 저장해서, memorization 하여 구하면, 

 

중복 계산값을 피할 수 있다는 점이죠.

 

전체 코드는 다음과 같습니다.

#include <iostream>
#include <cstring>

using namespace std;

#define input_max 32 + 1  //입력의 최대값
#define dir_max 3         // 방향은 총 3가지 가로 대각선 세로
int n;

int a[input_max][input_max];

int dx[] = { 0, 1, 1 };
int dy[] = { 1, 1, 0 };

long long d[input_max][input_max][dir_max];  //DP 배열 선언

bool ok(int x, int y, int dir) {

	if (dir == 0) { //진행하려는 방향이 가로일 때 가능한 공간 체크
		
		for (int k = 0; k < 1; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];

			if (!(nx > 0 && nx <= n && ny > 0 && ny <= n && a[nx][ny] == 0)) {
				return false;
			}
		}

	}

	else if (dir == 1) { //진행하려는 방향이 대각선일 때 가능한 공간 체크
		for (int k = 0; k < 3; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];

			if (!(nx > 0 && nx <= n && ny > 0 && ny <= n && a[nx][ny] == 0)) {
				return false;
			}
		}

	}

	else if (dir == 2) { //진행하려는 방향이 세로일 때 가능한 공간 체크
		for (int k = 2; k < 3; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];

			if (!(nx > 0 && nx <= n && ny > 0 && ny <= n && a[nx][ny] == 0)) {
				return false;
			}
		}

	}

	return true;

}

long long dfs(int x, int y, int dir) {
	 
	if (x == n && y == n) {
		

		return 1; //반환하면서 카운트를 계산
		
	}

	long long &result = d[x][y][dir];  // x,y, dir방향에서 N,N까지 가는 모든 방법의 수를 대입

	if (result != -1) return result;   //만약에 방법의 수가 대입이 되어있다면 중복계산할 필요가 없음.

	result = 0;                        // d[x][y][dir] 값이 -1 즉, 아직 구하지 않았다면 0부터 다시 계산함.

	
	if (dir == 0) { //진행중인 방향이 가로일 때

		for (int k = 0; k < 2; k++) {
			if (ok(x, y, k)) {
				result += dfs(x + dx[k], y + dy[k], k);

			}
		}

	}
	else if (dir == 1) { //진행중인 방향이 대각선일 때

		for (int k = 0; k < 3; k++) {
			if (ok(x, y, k)) {
				result += dfs(x + dx[k], y + dy[k], k);

			}

		}

	}
	else if (dir == 2) { //진행중인 방향이 세로일 때
		for (int k = 1; k < 3; k++) {
			if (ok(x, y, k)) {
				result += dfs(x + dx[k], y + dy[k], k);

			}
			
		}

		
	}

	return result;
	
}
void solution() {

	cin >> n;
	
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			cin >> a[i + 1][j + 1];
		}

	
	
	memset(d, -1, sizeof(d));           //초기값 -1 설정, -1은 아직 계산 안한 배열

	cout << dfs(1, 2, 0) << '\n';       // 1, 2부터 시작

}
int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);


	solution();


	return 0;
}