[백준 3109] 빵집

문제

www.acmicpc.net/problem/3109

3109번: 빵집

 

풀이

 

 

1. 파이프의 가능한 경로를 찾기위해서 위부터 아래로 진행방향을 고정하고 끝점까지 도착 할 수 있는지의 여부를 체크하는 dfs를 진행합니다.

 

2. 위의 그림에서 파이프의 경로가 되는 빨간점에서 파란점들로 가는 상황에 대해서 생각해보면 아래와 같은 결론을 낼 수 있습니다.

 

• 1번 빨간점이 다음 열로 이동할 때 1번 파란점이아닌 2번 파란점으로 이동한다면 2번 빨간점이 이동할 수 없습니다. 따라서 윗점에서 파이프의 경로가 아래 점에서 파이프의 경로에 영향을 줍니다.

• 결국 위의 그림에서와 같이 핵심이 되는 파란 1번, 2번점은 개수가 한정되어 있고, 위부터 아래로 방향을 고정하였기에 dfs를 진행할 때 다음 점이 되는 방향을 위 대각선, 오른쪽, 아래 대각선으로 진행을 한다면 각각의 경로가 최적경로가 되어 파이프경로의 최대개수를 구할 수 있습니다. 

코드

#include <bits/stdc++.h>
using namespace std;
const int dir[3][2] = { {-1,1},{0,1},{1,1} };

int R, C, cr, cc, nr, nc, ans;
string m[10001];
bool flag, vis[10001][501];

void dfs(int r, int c) {
	if (flag) return;
	if (c == C - 1) {
		flag = 1;
		return;
	}
	for (int i = 0; i < 3; i++) {
		nr = r + dir[i][0], nc = c + dir[i][1];
		if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
		if (!vis[nr][nc] && m[nr][nc] != 'x') {
			vis[nr][nc] = 1;
			dfs(nr, nc);
			vis[nr][nc] = 0;
		}
	}
}

int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> R >> C;
	for (int i = 0; i < R; i++) cin >> m[i];
	for (int i = 0; i < R; i++) {
		flag = 0;
		dfs(i, 0);
		if (flag) ans++;
	}
	cout << ans;
}