[백준] 3109. 빵집

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

3109번: 빵집

이 문제는 해답이 너무 뻔했다.

 

왼쪽에서 오른쪽으로 가는 경로는 여러개 있다. 문제는 한번 지나간 점은 다시 지날 수 없다는 것인데, 이 점이 핵심이 된다. 경로가 서로 겹쳐질 수 없기 때문이다.

 

따라서 경로를 하나의 실로 표현을 하자면, 위부터 차곡차곡 쌓아나가야 경로를 최대한 많이 만들 수 있다. 하나라도 겹쳐지는 순간 미래에 경로를 만들 때 문제가 될 수 있기 때문이다. 

 

결론적으로 시작점을 맨 위부터 아래방향으로 잡고 경로를 만드는 경우, 경로는 항상 오른쪽 위, 오른쪽, 오른쪽 아래 방향을 보면서 만들어야한다. 반대로 맨 아래부터 위 방향으로 잡는 경우는 경로도 반대로 오른쪽 아래, 오른쪽, 오른쪽 위 방향을 보면서 만들면 최대한 많이 만들 수 있다.

 

근데 처음에 제출했을 때, 시간초과가 났다. 이유는 탐색할 때, 만약 어떤 점에서 경로를 만들지 못할 경우 그 점을 다시 탐색 가능한 점으로 만들었기 때문이다. 이렇게 만들 경우, 어떤 방향으로든 그 점에 도달하게 되면 경로를 못만든다는 것을 이미 확인했음에도 불구하고 또 같은 짓을 반복하게 되기 때문에 시간초과가 나게된다. 탐색하며 체크한 점들은 다시 지우지 않도록 하더라도 이후 탐색에 영향을 주지 않기 때문에 그냥 계속 탐색한 점들을 체크해도 된다.

 

다음은 코드이다.

#include <iostream>
#include <utility>
using namespace std;

typedef pair<int, int> pii;

pii pos[3] = {{-1, 1}, {0, 1}, {1, 1}};
char board[10000][500];
int R, C;

int dfs(int y, int x) {
	if(board[y][x] != '.') return 0;
	
	board[y][x] = 'x';
	if(x == C-1) return 1;
	
	bool flag = false;
	for(int i=0; i<3; i++) {
		int nextY = y + pos[i].first;
		int nextX = x + pos[i].second;
		if((nextY >= 0) && dfs(nextY, nextX) == 1) {
			flag = true;
			break;
		}
	}
	
	if(flag) return 1;
	else return 0;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> R >> C;
	for(int i=0; i<R; i++) cin >> board[i];
	
	int count = 0;
	for(int i=0; i<R; i++) count += dfs(i, 0);
	
	cout << count << "\n";
}