Boj 17070) 파이프 옮기기

문제

백준 17070

BFS

설명

문제에서 방법의 수가 항상 1.000.000 보다 작다고 하기 때문에 가능한 풀이이다. BFS 는 대개 방문체크를 하지 않으면 경우의 수가 기하급수적으로 커지는데, 브루트포스 방법으로 풀라고 만든 제한으로 보인다.

시간 복잡도

O(\(3 ^ {\mathrm{N}}\))

코드

int arr[17*17];
int n;

int main()
{
	cin >> n;
	for (int i = 0; i < n * n; i++)
		cin >> arr[i];

	int ans = 0;
	queue<pair<int, int>> q; // {head, dir}, dir=> {0:좌우, 1:상하, 2:대각}
	q.push({ 1, 0 });
    
	while (q.size())
	{
		auto cur = q.front(); q.pop();

        // 장애물 체크
		if (arr[cur.first] || arr[cur.second]) continue;
		if (cur.second == 2) {
			if (arr[cur.first - 1] || arr[cur.first - n])
				continue;
		}
        
        // 도착 체크
		if (cur.first == n * n - 1) {
			ans++;
			continue;
		}

		int x = cur.first % n, y = cur.first / n;
		if (cur.second == 0)
		{
			if (x + 1 >= n) continue;
			q.push({ cur.first + 1, 0 });
			q.push({ cur.first + n + 1, 2 });
		}
		else if (cur.second == 1) {
			if (y + 1 >= n) continue;
			if (x + 1 < n) 
				q.push({ cur.first + n + 1, 2 });
			q.push({ cur.first + n, 1 });
		}
		else {
			if (x + 1 < n) {
				q.push({ cur.first + 1, 0 });
				if (y + 1 < n) {
					q.push({ cur.first + 1 + n, 2 });
					q.push({ cur.first + n, 1 });
				}
			}
			else if(y + 1 < n){
				q.push({ cur.first + n, 1 });
			}
		}
	}

	cout << ans;
}

DP

설명

만약 대각선 이동이 존재하지 않았다면 BFS 를 수행하면서 다이나믹 프로그램을 수행해도 좋았을 것이다. 하지만 대각선은 십자 이동의 2번이 함축된 것으로, 1칸씩 움직이면서 수행하는 BFS 에서는 점화식을 짜기가 힘들다.

하지만 파이프 옮기기 작업은 항상 인덱스가 커지는 방향으로 이루어진다. (인덱스를 좌->우, 상->하 방향으로 커지도록 둔다면). 이를 이용하면 점화식을 아래처럼 간단히 세울 수 있다.

시간 복잡도

O(\(\mathrm{N} ^ {2}\))

코드

int arr[17*17];
int dp[17 * 17][3];
int n;

int main()
{
	cin >> n;
	for (int i = 0; i < n * n; i++)
		cin >> arr[i];

	dp[1][0] = 1;
	for (int i = 1; i < n * n; i++)
	{
		if (arr[i]) continue;
		int x = i % n, y = i / n;
		bool bX = x > 0, bY = y > 0;
		if (bX && !arr[i - 1]) {
			dp[i][0] += dp[i - 1][0] + dp[i - 1][2];
		}
		if (bY && !arr[i - n]) {
			dp[i][1] += dp[i - n][1] + dp[i - n][2];
		}
		if (bX && bY && !arr[i - 1] && !arr[i - n] && !arr[i - 1 - n]) {
			dp[i][2] += dp[i - n - 1][0] + dp[i - n - 1][1] + dp[i - n - 1][2];
		}
	}

	cout << dp[n * n - 1][0] + dp[n * n - 1][1] + dp[n * n - 1][2];
}