1-B-E 백준 17070번 파이프 옮기기 1 (+ 파이프 옮기기 2)

알고리즘 캠프에서 풀었던 다른 문제들:

알고리즘 캠프 인덱스

문제 링크:

17070번: 파이프 옮기기 1

최단거리를 구하는 것이 아니라 가능한 모든 경로를 구하는 것이기 때문에 BFS를 사용할 수 없다.

상하좌우로 움직일 수 있는 DFS와는 달리, 이미 갔던 위치에 다시 돌아갈 수 없는 3방향으로만 움직일 수 있다.

따라서 중복 방문을 방지하기 위한 visited를 사용할 필요가 없다. 즉, BF 문제인 것이다.

/* 39분 소요 */

/* 1. visited처리는 queue push와 항상 함께 */
/* 2. 수정된 좌표계에 맞게 좌표 입력하기 : (0,0) -> (1, 1) */
/* 3. 이미 놓여져있는 가로 파이프의 오른쪽 끝 부터 시작 : (1, 1) -> (1, 2) */
/* 4. (N, N)에 도착하기만 하면 되고, 최소 경로일 필요가 없기 때문에 DFS로 풀어야 한다. */

#include <iostream>
#include <queue>

using namespace std;

int N;
bool map[18][18];
int ans;

void DFS(int r, int c, int dr) {	/* 4 */
	if (r == N && c == N) {
		++ans;
		return;
	}

	// 가로로 이동
	if (dr != 2) 
		if (!map[r][c + 1]) 
			DFS(r, c + 1, 0);

	// 대각선 이동
	if (!map[r][c + 1] && !map[r + 1][c] && !map[r + 1][c + 1]) 
		DFS(r + 1, c + 1, 1);

	// 세로로 이동
	if (dr != 0) 
		if (!map[r + 1][c]) 
			DFS(r + 1, c, 2);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	for (int c = 1; c < N + 1; ++c) map[0][c] = 1;
	for (int r = 1; r < N + 1; ++r) {
		map[r][0] = map[r][N + 1] = 1;
		for (int c = 1; c < N + 1; ++c)
			cin >> map[r][c];
	}
	for (int c = 1; c < N + 1; ++c) map[N + 1][c] = 1;

	DFS(1, 2, 0);	/* 1 */ /* 2 */	/* 4 */

	cout << ans;
	return 0;
}

이 방법은 도달하지 못 하는 경우까지 모두 탐색해야 하기 때문에 시간이 오래걸린다.

---

17069번: 파이프 옮기기 2

파이프 옮기기 2는 N의 크기는 더 커진 반면, 제한시간이 더 짧아져 DP로 해결해야 한다.

diagonal traversal을 구현하는데 시간이 꽤 오래 걸렸다.

/* 2시간 45분 소요 */

/* 1. diagonal traversal 중 좌표를 (1, 1) ~ (N, N)에 맞게 설정하기 */
/* 2. 답은 첫번째 가로파이프에설 놓을 수 있는 가로 파이프의 경우의수와 대각선 파이프의 경우의수를 합한 것이다. */

#include <iostream>
#define IN(r, c) (0 <= (r) && (r) < N && 0 <= (c) && (c) < N)

using namespace std;

int N;
bool map[34][34];
long long cst[34][34][3];

void DP() {
	cst[N][N][1] = 1;

	for (int b = 2; b <= N; ++b) {
		int r = N, c = N + 1 - b;
		for (int i = 0; i < b; ++i) {
			if (!map[r][c + 1])
				cst[r][c][0] = cst[r][c + 1][0] + cst[r][c + 1][1];
			if (!map[r][c + 1] && !map[r + 1][c + 1] && !map[r + 1][c])
				cst[r][c][1] = cst[r + 1][c + 1][0] + cst[r + 1][c + 1][1] + cst[r + 1][c + 1][2];
			if (!map[r + 1][c])
				cst[r][c][2] = cst[r + 1][c][1] + cst[r + 1][c][2];
			--r, ++c;
		}
	}

	for (int b = N - 1; b >= 1; --b) {
		int r = b, c = 1;
		for (int i = 0; i < b; ++i) {
			if (!map[r][c + 1])
				cst[r][c][0] = cst[r][c + 1][0] + cst[r][c + 1][1];
			if (!map[r][c + 1] && !map[r + 1][c + 1] && !map[r + 1][c])
				cst[r][c][1] = cst[r + 1][c + 1][0] + cst[r + 1][c + 1][1] + cst[r + 1][c + 1][2];
			if (!map[r + 1][c])
				cst[r][c][2] = cst[r + 1][c][1] + cst[r + 1][c][2];
			--r, ++c;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;

	for (int c = 1; c < N + 1; ++c) map[0][c] = 1;
	for (int r = 1; r < N + 1; ++r) {
		map[r][0] = map[r][N + 1] = 1;
		for (int c = 1; c < N + 1; ++c)
			cin >> map[r][c];
	}
	for (int c = 1; c < N + 1; ++c) map[N + 1][c] = 1;

	DP();

	cout << cst[1][2][0] + cst[1][2][1];
	return 0;
}