백준 3109번: 빵집

[문제 링크]

3109번: 빵집

---

그리디 알고리즘과 DFS가 섞인 문제였다.

 

파이프를 연결할 수 있는 경우는 오른쪽 대각선 위, 오른쪽 옆, 오른쪽 대각선 아래 세가지가 있고, 파이프가 서로 겹치거나 엇갈리면 안되기 때문에 대각선 위 -> 옆 -> 아래 순으로 탐색 하는 것이 항상 최적해를 보장한다.

성공적으로 파이프를 연결했다면 1을 반환하고, 파이프가 연결되었기 때문에 다른 경우는 고려할 필요 없이 탐색을 종료한다.

 

한번 방문했던 좌표는 그전에 이미 시도해본 좌표이기 때문에 고려해줄 필요가 없다. 따라서 2차원 visit 배열을 선언하여 방문여부를 체크했다.

---

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

string board[10000];
bool visit[10000][500];
int dy[3] = { -1, 0, 1 };

int Greedy(int startY, int startX, int R, int C)
{
	if (startX == C - 1) return 1;

	int ret = 0;

	for (int i = 0; i < 3; i++)
	{
		int nextY = startY + dy[i];
		int nextX = startX + 1;

		if (nextY >= 0 && nextY < R && board[nextY][nextX] != 'x' && !visit[nextY][nextX])
		{
			visit[nextY][nextX] = true;
			ret = Greedy(nextY, nextX, R, C);
		}

		if (ret == 1)
			break;
	}

	return ret;
}

int main(void)
{
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	int R, C;
	cin >> R >> C;

	for (int i = 0; i < R; i++)
		cin >> board[i];

	int cnt = 0;
	for (int i = 0; i < R; i++)
		cnt += Greedy(i, 0, R, C);

	cout << cnt << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 126 day