빵집(DFS+Greedy)

 

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

3109번: 빵집

왼쪽에서 오른쪽까지 연결되는 최대한 많은 경로를 구해야한다.

가는 방법은 오른쪽 윗방향 대각선, 오른쪽, 오른쪽 아래방향 대각선 세 가지

 

DFS를 사용하여 맨 끝에 도달한다면 탐색을 멈추어 나머지 가지에 대한 탐색을 하지 않도록 한다.

이차원 배열을 하나 더 사용하여(Visit) 이전에 탐색했던 부분은 추가로 탐색하지 않도록 해야한다.

↗→↘ 순으로 탐색하여 최대한 위쪽으로 경로를 찾도록 해야 함.

이렇게 하면 현재의 경로탐색이 추후 최대다수의 경로를 탐색하는데 있어 영향을 주지 않아서 그리디 방법으로 최적해를 구할 수 있다.

 

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

int r, c;
bool Map[10000][500];
bool Visit[10000][500] = { 0, };
int xpos[3] = { 1, 0, -1 };
int ret = 0;

bool check(int x, int y)
{
	if (x >= 0 && x < r && y >= 0 && y < c && 
		Map[x][y] == true && Visit[x][y] == false) return true;
	else return false;
}

void DFS(int x, int y)
{
	stack<pair<int, int>> stk;
	stk.push(pair<int, int>(x, y));
	bool find = false;
	while (!stk.empty())
	{
		int curx = stk.top().first;
		int cury = stk.top().second;
		stk.pop();
		Visit[curx][cury] = true;
		if (cury == c - 1)
		{
			find = true;
			break;
		}
		for (int i = 0; i < 3; i++)
		{
			if (check(curx + xpos[i], cury + 1))
			{
				stk.push(pair<int, int>(curx + xpos[i], cury + 1));
			}
		}
	}
	if (find) ret++;
}

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

	cin >> r >> c;

	char input;
	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
		{
			cin >> input;
			switch (input)
			{
			case '.':
				Map[i][j] = true;
				break;
			case 'x':
				Map[i][j] = false;
				break;
			default:
				break;
			}
		}
	}

	for (int i = 0; i < r; i++)
	{
		DFS(i, 0);
	}

	cout << ret << '\n';
}