[백준] 골드2 : (3109) 빵집

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

 

파이프를 연결하는 방향이 무조건 X가 증가하는 방향으로만 있다. (오른 대각 위, 오른쪽, 오른 대각 아래)

DFS를 사용해 풀이를 한다.

 

한 파이프를 연결할 때, 이후에 다른 파이프들의 연결에 최대한 지장을 주면 안 된다.

따라서, 항상 위쪽으로 먼저 DFS 탐색을 해야 한다.

 

한 번 탐색한 위치에서 파이프 연결이 실패했다면, 해당 위치로는 파이프 연결이 불가능하다는 의미이기 때문에, 꼭 방문 처리를 해줘야 한다.

 

어차피 방문 처리를 하나, 해당 좌표가 'X'이거나 같으므로, 방문 처리를 해당 위치를 'X'로 초기화하는 것으로 한다.

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

// 방향 [오른 대각 위, 오른쪽, 오른 대각 아래]
int dy[]{ -1, 0, 1 };
int dx[]{ 1, 1, 1 };

bool Func(vector<vector<char>>& Map, pair<int, int> Pos, const int& End, int& Answer)
{
	int y = Pos.first, x = Pos.second;

	// X값이 마지막 열에 닿으면, 파이프 연결 성공
	if (x == End)
	{
		Map[y][x] = 120;	// 연결된 파이프 위치는 다른 파이프가 가지 못하도록 X로 초기화
		Answer++;
		return true;
	}

	// 각 방향 [대각 위, 오른쪽, 대각 아래]으로 DFS 수행
	for (int i = 0; i < 3; ++i)
	{
		int ny = y + i[dy], nx = x + dx[i];
		if (ny < 0 || ny >= Map.size() || nx > End || Map[ny][nx] == 120) continue;
		if (Func(Map, { ny, nx }, End, Answer)) { Map[y][x] = 120; return true; }
	}

	// 해당 위치에서 파이프 연결이 실패했다는 의미는 다른 파이프가 와도 연결을 못한다는 의미이다.
	// 따라서, 해당 위치를 X로 초기화 한다.
	Map[y][x] = 120; // 이 부분이 없으면, 실패하는 경로도 이후로 계속 반복 탐색해서 시간 초과가 난다.
	return false;
}

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

	int r, c, Answer = 0;
	cin >> r >> c;

	vector<vector<char>> Map(r, vector<char>(c, 120));	// 맵 배열 (전부 X로 초기화)

	for (int i = 0; i < r; ++i)
		for (int j = 0; j < c; ++j)
			cin >> Map[i][j];

	for (int i = 0; i < r; ++i)
		Func(Map, { i, 0 }, Map[0].size() - 1, Answer);	// 각 열의 첫 번째 칸을 시작으로 DFS 수행

	cout << Answer << "\n";
}