백준 / 3109 빵집 C++

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

3109번: 빵집

dfs와 그리디를 합친 문제였습니다. 처음에는 dfs만으로 생각해서 풀려했는데 간단히 경로 찾기 개념만을 적용하면 겹치는 구간이 많고 복잡해졌습니다.

좀만 더 생각하니 해당 경로는 대각선 오른 위, 오른쪽, 대각선 오른 아래 방향으로만 움직일 수 있으므로 맨 위의 점부터 탐색을 하며 최대한 위쪽으로 가스관을 연결하면 됨을 깨달았습니다.

 

그리하여 dfs를 1,1 위치부터 r,1 위치 순으로 진행하며 dfs 내부에서는 오른쪽 대각선 위, 오른쪽, 오른쪽 대각선 아래 순으로 진행시킵니다. 

(처음에 계속 진행할 수 있는지 여부를 전역으로 처리했는데 좀 맞다가 틀렸다 그런다. 전역으로 처리해서 에러처리한 거랑 불린으로 리턴한 거랑 뭐가 다르지? 테스트케이스는 다 맞던데...)

 

코드는 다음과 같습니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>

using namespace std;

int r, c;
char map[10001][501];
bool visited[10001][501];
int dy[3] = { -1,0,1 };
int dx[3] = { 1,1,1 };
int result = 0;

void make_map()
{
	cin >> r >> c;
	for (int i = 1; i <= r; i++) {
		string s;
		cin >> s;
		for (int j = 1; j <= s.size(); j++) {
			map[i][j] = s[j - 1];
			visited[i][j] = false;
		}
	}
}

// 1,1 부터 최대한 대각선 위로 그 다음에 우로 그 다음에 대각선 아래로 진행
// 리턴 값이 false면 더 이상 갈 수 없음
// x 위치 c일때만 경로가 된 것
bool dfs(int y, int x)
{
	visited[y][x] = true;

	if (x == c) {
		result++;
		return true;
	}

	for (int i = 0; i < 3; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 1 || ny > r || nx < 1 || nx > c)
			continue;

		if (map[ny][nx] == 'x')
			continue;

		if (visited[ny][nx] == false && map[ny][nx] == '.') {
			if(dfs(ny, nx))
				return true;
		}
	}

	return false;
}

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

	make_map();

	for (int i = 1; i <= r; i++) {
		visited[i][1] = true;
		dfs(i, 1);
	}

	cout << result;
}