BOJ 3109 빵집 / C++

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

3109번: 빵집

아이디어

이 문제는 사실 만족할만큼 이해하지는 못한 것 같습니다.

이 문제의 풀이인 DFS를 통해 간선 카운팅을 하는방식은 가장 처음에 생각했는데 위에서 언급한 부분 때문에 바로 풀이해내지는 못했습니다. 그 외에 BFS를 통해 간선의 한 부분에서 갈 수 있는 최댓값을 구하는 문제인가 등등 접근을 많이 해봤지만 반례가 너무나 쉽게 떠올라 다른분들의 풀이를 보고야 말았죠.

왼쪽에서 오른쪽으로 DFS를 이용하여 도착할때 마다 카운팅을 하는 방식으로 풀이를 할 수 있는데요. 여기서 가장 중요한것은 y축 탐색시 대각선 하단을 가장 먼저 탐색을 해야한다는 것이다. 아래에 주석을 달아놓은것 처럼 아래를 방문할때 더 큰 파이프라인 갯수가 나올 경우를 빠뜨릴 수 있기 때문이라는 것은 알았는데 왜? 가 해결이 안된 상태입니다.

단순히 반례를 보면서 손으로 따라가보는 것 말고는 검증할 방법이 없었는데 혹여 추후에 이해가 된다면 자세한 풀이 남기겠습니다. 또는 아시는분은 지식 공유 부탁드립니다.

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int r, c;
int cnt;
// y의 대각선 축으로 먼저 탐색하게 하는게 포인트
//위를 먼저 방문할 경우에 아래를 먼저 방문할때 더 큰 파이프라인 갯수가 나올경우를 빠뜨림
int my[3] = { -1,0,1 };
int mx[3] = { 1,1,1 };
vector<vector<char>> graph;

void input() {
	cin >> r >> c;
	graph.resize(r, vector<char>(c));
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> graph[i][j];
		}
	}
}

bool dfs(int y, int x) {
	if (x == c - 1) {
		cnt++;
		return true;
	}

	graph[y][x] = 'x';
	for (int i = 0; i < 3; i++) {
		int ny = y + my[i];
		int nx = x + mx[i];
		if (ny >= r || ny<0 || nx>=c || nx < 0 ) continue;
		if (graph[ny][nx] == 'x') continue;
		//탐색을 더 이어갈지 체크
		if (dfs(ny,nx))
			return true;
	}
	return false;

}
void solution() {
	for (int i = 0; i < r; i++) {
		dfs(i, 0);
	}
	cout << cnt;
}

int main(void) {
	input();
	solution();
}