[BOJ] 3109: 빵집 (C++)

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

3109번: 빵집

걸린 시간 : 37분 55초

---

문제가 무슨 소리인지 생각하는데 조금 걸렸지만, 문제가 무슨 말을 하는지 이해하고, 가능한 경우를 생각해보면 어떤 방식으로 코딩해야 하는지는 쉽다.

 

제일 왼쪽부터 시작해서 제일 오른쪽까지 대각선 혹은 직진으로 진행하면서 가능한 경로를 모두 세면 되는 것이다. 제일 위쪽부터 생각하면서 모든 경로를 생각하면 된다.

 

하지만, 보통의 백트래킹 생각대로 하면 실패한다. 보통, 현재 상황에서 체크를 하고 재귀함수를 호출한 후에 가능성이 없는 경로라면 체크를 해제하고 다른 경우를 탐색한다.

그러나 이 문제에서는 가능성이 없는 경로라서 되돌아왔던 경우라 하더라도 체크를 해제하면 안된다. 그 경우는 어차피 다른 경우에도 실패할 경로이기 때문이다! 만약 체크를 해제하게 된다면 어차피 실패할 경로를 계속해서 탐색하게 된다.

 

따라서 밑의 코드에서 주석처리된 부분만을 없애주면 시간복잡도가 엄청나게 개선된다.

(그래도 골드 2보다는 쉬운 문제라고 생각된다.)

 

#include <bits/stdc++.h>
using namespace std;

int R, C, cnt;
int dir[3] = {-1, 0, 1};
string board[10001];
bool vis[10001][501];

bool push_pipe(int r, int c) {
	if (c == C-1) {
		return true;
	}
	vis[r][c] = true;
	for (int k = 0; k < 3; k++) {
		int nr = r + dir[k];
		int nc = c + 1;
		if (nr < 0 || nr >= R || board[nr][nc] == 'x' || vis[nr][nc] == true)
			continue;
		if (push_pipe(r+dir[k], c+1)) {
			return true;
		}
	}
//	vis[r][c] = false;
	return false;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> R >> C;
	for (int i = 0; i < R; i++)
		cin >> board[i];
	for (int i = 0; i < R; i++) {
		if (push_pipe(i, 0)) cnt++;
	}
	cout << cnt;
	return 0;
}