알고리즘 문제 풀기

<백준> 17070번 : 파이프 옮기기1

studying develop 2020. 3. 12. 16:16

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

 

근데 내 생각에 이 문제의 포인트는 파이프를 어떻게 저장할 것이냐다. 무슨 말이냐면 두칸다 저장할지, 한쪽 끝만 저장할지?

 

근데 생각해보니, 가로,세로,대각선이냐에 따라서 이동시킬 거니까, 왼쪽 끝 지점이랑, 회전 상태만 저장하면 될거 같다.

 

음 생각 보다, 제한 조건 부분에서 제한을 구현하는게 쉬운거 간다. 

 

나는 전에 파이프가 길이가 2이지 않은가, 그걸 두개다 옮기려고 해서 코드 구현이 복잡해 졌다.

 

이번에는 state를 선언해서 가로,세로,대각선을 나누어 간단하게 표현했다.

 

#define _CRT_SECURE_NO_WARNINGS
#define debug 0
#include <iostream>
#include <algorithm>
#include <vector>
#include<string.h>
using namespace std;

#define NUM 17
#define MAXV 987654321
int N, M;
int arr[NUM][NUM];

int dir_r[4] = { 1,1,-1,-1 };
int dir_c[4] = { -1,1,-1,1 };
int ans = 0;

enum {
	garo, sero, diagnal
};

struct rc {
	int r, c;
};

bool is_bound(int r, int c) {
	if (arr[r][c] == 1)
		return false;

	if (!(r >= 0 && r < N && c >= 0 && c < N)  ) {
		return false;
	}

	return true;
}

bool isOkay(int r, int c,int state) {
	if (!(is_bound(r,c) )) {
		return false;
	}

	if (state == garo) {
		if ( !is_bound(r, c + 1)) {
			return false;
		}
	}
	else if (state == sero) {
		if (!is_bound(r + 1, c)) {
			return false;
		}
	}
	else if (state == diagnal) {
		if (!is_bound(r + 1, c + 1) || !is_bound(r+1,c) || !is_bound(r,c+1)) {
			return false;
		}
	}
	return true;
}

void dfs(int r,int c,int state,int depth) {
	if (!isOkay(r, c, state)) {
		return ;
	}

	if (state == diagnal && r == N - 2 && c == N - 2 ) {
		ans++;
		return;
	}
	else if (state == garo && r == N - 1 && c == N - 2) {
		ans++;
		return;
	}
	else if (state == sero && r == N - 2 && c == N - 1) {
		ans++;
		return;
	}

	if (state == garo) {
		dfs(r, c + 1, garo,depth+1);
		dfs(r, c + 1, diagnal,depth+1);
	}
	else if (state == sero) {
		dfs(r + 1, c, sero, depth+1);
		dfs(r + 1, c, diagnal,depth+1);
	}
	else if (state == diagnal) {
		dfs(r + 1, c + 1, garo,depth+1);
		dfs(r + 1, c + 1, sero,depth+1);
		dfs(r + 1, c + 1, diagnal,depth+1);
	}

	return;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	freopen("input.txt", "r", stdin);

	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
		}
	}

	dfs(0, 0, garo,0);

	cout << ans;


	return 0;
}