[백준/BOJ] 백준 3109번 : 빵집

www.acmicpc.net/problem/3109

3109번: 빵집

위에서부터 순서대로 오른쪽 끝 열에 도달할 수 있는지 탐색한다 탐색할 때는 오른쪽 위 대각선, 오른쪽 직선, 오른쪽 아래 대각선 순서로 탐색한다. 그리고 열에 끝에 도달했을 때는 1을 반환하여 문제를 해결한다. 탐색을 하면서 해당 위치에 파이프라인을 연결하면서 탐색을 진행하는데, 파이프라인 연결한것을 탐색이 끝난 뒤 지울 필요가 없다 위쪽 행 부터 최적으로 연결할 수 있는 위치에 연결한 파이프 라인이라서 다른 행에서 오는 파이프 라인과 겹치면 안 되고, 비록 열의 끝에 도달하지 못하는 파이프 라인일지라도 다른 행에서 이 파이프로 오면 열의 끝에 도달하지 못하기 때문이다.

 

코드

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

int r, c;
vector<string> board;
vector<vector<int>> board_check(10000, vector<int>(500, 0));
int dxdy[3][2] = { {-1,1},{0,1},{1,1} }; //오른쪽 위 대각선, 오른쪽 직선, 오른쪽 아래 대각선 순서로 탐색

int Solve(pair<int, int> here)
{
	board_check[here.first][here.second] = 1; //해당 위치 파이프라인 연결
	//파이프라인 연결한것을 탐색이 끝난뒤 지울 필요가 없다
	//위쪽 행 부터 최적으로 연결할 수 있는 위치에 연결한 파이프 라인이라서 다른 행에서 오는 파이프 라인과 겹치면 안된다
	//비록 열의 끝에 도달하지 못하는 파이프 라인일지라도 다른 행에서 이 파이프로 오면 열의 끝에 도달하지 못한다

	//열의 끝에 도달 했을때
	if (here.second == c - 1)
		return 1;

	int ret = 0;

	//오른쪽 위 대각선, 오른쪽 직선, 오른쪽 아래 대각선 순서로 탐색
	for (int i = 0; i < 3; i++)
	{
		pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

		if (there.first >= 0 && there.first < r && there.second >= 0 && there.second < c && board[there.first][there.second] == '.' && board_check[there.first][there.second] == 0)
		{
			ret = Solve(there);

			if (ret == 0) //there쪽으로 가면 경로가 없을때
				continue;

			else //there쪽으로 가면 경로가 있을때
				return 1;
		}
	}

	//경로가 없을때
	return 0;
}

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

	cin >> r >> c;

	for (int i = 0; i < r; i++)
	{
		string input;
		cin >> input;

		board.push_back(input);
	}

	int result = 0;
	for (int i = 0; i < r; i++)
	{
		result += Solve(make_pair(i, 0));
	}

	cout << result;

	return 0;
}