BOJ - 17070번 파이프 옮기기(C++)

문제 출처: https://www.acmicpc.net/problem/17070

문제 난이도

Gold 5

문제 접근법

파이프 범위가 한정적이기 때문에 여러 경우의 수를 생각하지 않아도 됐다.
깊이 탐색을 이용해서 파이프 끝이 (N,N)에 닿았으면 counting 했다.

통과 코드

#include <iostream>
#include <algorithm>

using namespace std;

int N;
int arr[17][17];
int res;
bool ch[17][17];

struct pipe {
	int x1, x2, y1, y2;
	int state;
};

void dfs(pipe now) {
	int s = now.state;
	int x = now.x2;
	int y = now.y2;
	if (x == N && y == N ) {
		res++;
		return;
	}
	if (s == 0) {
		//가로
		pipe next;
		if (x <= N && y + 1 <= N && !ch[x][y + 1] && arr[x][y + 1]==0) {
			next.x1 = x;
			next.y1 = y;
			next.x2 = x;
			next.y2 = y + 1;
			next.state = 0;
			ch[x][y + 1] = true;
			dfs(next);
			ch[x][y + 1] = false;
		}
		if (x +1 <= N && y + 1 <= N && !ch[x+1][y+1] && arr[x][y + 1] == 0  && arr[x + 1][y] == 0 && arr[x+1][y + 1] == 0) {
			next.x1 = x;
			next.y1 = y;
			next.x2 = x + 1;
			next.y2 = y + 1;
			next.state = 2;
			ch[x + 1][y + 1] = true;
			dfs(next);
			ch[x + 1][y + 1] = false;
		}
	}
	else if (s == 1) {
		//세로
		pipe next;
		if (x +1 <= N && y  <= N && !ch[x+1][y] && arr[x+1][y] == 0) {
			next.x1 = x;
			next.y1 = y;
			next.x2 = x + 1;
			next.y2 = y;
			next.state = 1;
			ch[x+1][y] = true;
			dfs(next);
			ch[x + 1][y] = false;
		}
		if (x+1 <= N && y + 1 <= N && !ch[x + 1][y + 1] && arr[x][y + 1] == 0 && arr[x + 1][y] == 0 && arr[x + 1][y + 1] == 0) {
			next.x1 = x;
			next.y1 = y;
			next.x2 = x + 1;
			next.y2 = y + 1;
			next.state = 2;
			ch[x + 1][y+1] = true;
			dfs(next);
			ch[x + 1][y+1] = false;
		}
	}
	else if (s == 2) {
		//대각선
		pipe next;
		if (x <= N && y + 1 <= N && !ch[x][y + 1] && arr[x][y + 1] == 0) {
			next.x1 = x;
			next.y1 = y;
			next.x2 = x;
			next.y2 = y + 1;
			next.state = 0;
			ch[x][y + 1] = true;
			dfs(next);
			ch[x][y + 1] = false;
		}
		if (x + 1 <= N && y <= N && !ch[x + 1][y] && arr[x + 1][y] == 0) {
			next.x1 = x;
			next.y1 = y;
			next.x2 = x+1;
			next.y2 = y;
			next.state = 1;
			ch[x + 1][y] = true;
			dfs(next);
			ch[x + 1][y] = false;
		}
		if (x + 1 <= N && y + 1 <= N && !ch[x + 1][y + 1] && arr[x][y + 1] == 0 && arr[x + 1][y] == 0 && arr[x + 1][y + 1] == 0) {
			next.x1 = x;
			next.y1 = y;
			next.x2 = x + 1;
			next.y2 = y + 1;
			next.state = 2;
			ch[x + 1][y + 1] = true;
			dfs(next);
			ch[x + 1][y + 1] = false;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N; 
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> arr[i][j];
		}
	}
	pipe cur;
	cur.x1 = 1;
	cur.y1 = 1;
	cur.x2 = 1;
	cur.y2 = 2;
	cur.state = 0;
	dfs(cur);
	cout << res << "\n";
	return 0;
}

피드백

너무 하드코딩으로 풀었다 경우의 수가 적길래 하나하나 if 걸어줬더니 효율적이지 못한 코드가 됐다. 걍 { {0, 1}, {1, 0}, {1, 1} }; 배열 줘서 for문 걸어서 기본 dfs처럼 코드 짜도 될 것 같다.