[백준 17070] 파이프 옮기기 1 C++

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

17070번: 파이프 옮기기 1

문제풀이

 

이 문제는 입력이 16이 제한이므로 느낌에, 가능한 모든 경우의 수를 구해서 푸는 브루트포스 문제라고 느낌이 들었습니다. 

1초를 약 for문 1억번을 돌린다고 생각했을 때,

16x16은 256칸이지만, 

1, 2에서 시작하기 때문에 15 x 15 = 225

사실 벽이 없을 때 가정을 하면, 약 O(2^225)라고 생각하지만, 이 수는 천문학적인 수라서 안되고,

아마 벽이 중 간에 적절히 있고, 벽에 부딪히는 상황이 있다면 1초안에 구할 수 있다고 생각했습니다.

 

다행이도..!! 출력 조건에 '방법의 수는 항상 1,000,000보다 작거나 같다.' 라는 조건이 붙어있습니다.

즉, 모든 수를 구해도 100만보다 작기 때문에 모든 경우의 수를 구하더라도 0.1초 밖에 안나온다는 사실 입니다.

 

입력 제한이 16까지가 아니라 16 이상이고, 출력 값이 정해져 있지 않으면 다이나믹으로 풀어야 된다고 생각했을것 같습니다.

파이프가 1, 2에서 시작을 하는데 앞으로 나아가야할 때마다 방향에 따라서 갈 수 있는 방법을 구하고, 가능한 영역을 구하는 문제입니다. 

 

문제에 약간의 이해가 안되는 부분이 있었는데, 문제 그대로 따라만 하면 금방 풀렸습니다.

주의 할점은, 파이프가 이동할 때마다 가로, 대각선, 세로 일 때 진행할 수 있는 방향을 미리 구한다음 진행을 해야한다는 것입니다.

가로로 진행 중일 때 갈 수 있는 방법은 가로, 대각선입니다.

가로 - 가로로 진행할 때는 오른쪽이 비어있어야하고요,

가로-대각선으로 진행할 떄는 오른쪽, 대각선, 아래가 비어있어야합니다.

 

대각선으로 진행 중일 때 갈 수 있는 방법은 가로, 대각선, 세로 모두입니다.

대각선-가로는 오른쪽이 비어있어야하고요.

대각선-대각선은 오른쪽, 대각선, 아래가 비어있어야합니다.

대각선-세로 는 아래가 비어있어야합니다.

 

세로로 진행 중일 때 갈 수 있는 방법은 대각선, 세로 입니다.

세로-대각선으로 진행할 때는 진행하는 방향의 오른쪽, 대각선, 아래가 비어있어야하고요.

세로-세로로 진행할 떄는 진행하는 방향의 아래쪽이 비어있어야합니다. 

 

위와 같은 로직으로 저는 구현했습니다. 물론 비어있다고 확인할 때 N x N 배열 안에있는지도 항상 확인을 해야하고요.

 

저는 이문제를 재귀함수를 통해 풀었습니다. for문이나 if문을 확실하게 줄여줘서

가독성이 좋고 코드를 금방 짤 수 있다는 장점이 있습니다. 

 

백준은 메모리가 512MB까지 대부분 지원하기 때문에, 이 메모리는 대부분 알고리즘으로 다 돌아갑니다. 

 

따라서, 재귀에서 계속 경우의 수를 나눠서 호출했습니다.

 

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

 

#include <iostream>

using namespace std;

#define input_max 16 + 1
int n;

int a[input_max][input_max];

int dx[] = { 0, 1, 1 }; // 가로 대각선 세로 순
int dy[] = { 1, 1, 0 }; // 가로 대각선 세로 순
int result;

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;

}

void dfs(int x, int y, int dir) {
	 
	if (x == n && y == n) { // N x N 에 도착했을 때 카운트 1추가
		result++;

		return;
		
	}


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

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

			}
		}

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

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

			}

		}

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

			}

		}

		
	}
	
}
void solution() {

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

	dfs(1, 2, 0); // 1, 2 좌표에서 시작! 방향은 가로 즉, dir = 0


	cout << result << '\n';

}
int main() {

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


	solution();


	return 0;
}