백준 Gold 2 빵집

빵집 (백준 Gold 2)

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

제빵사 원웅이는 재정위기 때문에
다른 빵집의 가스를 훔쳐(?) 사용하려 한다

가장 왼쪽의 행으로부터 오른쪽의 행까지
연결 가능한 파이프라인의 개수를 구하는 문제

• 파이프라인은 / - \ 의 방향으로 설치 가능
  
• 첫행과 마지막 행은 비어 있음
  
• 파이프라인이 이미 설치된 곳은 다른 파이프를 설치 불가
  
• 건물이 있는 곳도 설치 불가
  

풀이 방법

기본적으로 dfs에 대한 문제라 생각하였다
가장 왼쪽으로부터 깊이 우선 탐색을 진행하고
오른쪽으로 보낸 경우 파이프라인이 완성되면 + 1

따라서 건물과 같이 x 표시를 쳐서
방문 여부를 체크하려 하였다

• 첫 줄부터 ‘위’ ‘중간’ ‘아래’의 방향으로 탐색하면 되기에
  그리디 알고리즘이라 판단하였다
  

• dfs로 못풀줄 알았지만, 점점 탐색 영역이 좁아지기에
  가능할지도 모른다 생각하고 시도해 보았다
  

첫 제출 코드

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

using namespace std;

int r, c;

bool dfs(vector<string>& maps, int nowr, int nowc)
{
	if (nowr < 0 || nowr >= r)
		return false;

	if (maps[nowr][nowc] != '.')
		return false;

	maps[nowr][nowc] = 'x';

	if (nowc == c - 1)
		return true;

	if (dfs(maps, nowr - 1, nowc + 1))
		return true;

	if (dfs(maps, nowr, nowc + 1))
		return true;

	if (dfs(maps, nowr + 1, nowc + 1))
		return true;

	maps[nowr][nowc] = '.';

	return false;
}

int main()
{
	cin >> r >> c;
	vector<string> maps(r);
	for (int i = 0; i < r; i++)
		cin >> maps[i];

	int answer = 0;
	for (int i = 0; i < r; i++)
	{
		if (dfs(maps, i, 0))
			answer++;
	}

	cout << answer;
}

시간초과?

자세히 보면 마지막에 백트래킹 처럼 ‘.’를 통해
다시 재탐색이 가능하게 돌려주는 부분이 있다

하지만 곰곰히 생각해보면,
이미 ‘그 곳’을 밟아서 완성할 수 있었다면
해당 파이프라인이 ‘밟아’ 완성할 수 있지 않았을까? 싶었다

반대로 dfs를 통해 죄다 탐색했지만
불가능하였다면 애초에 그 영역을
밟아서는 안되는 것이라 판단하였고

그냥 해당 부분을 지워버렸다

• ‘불필요한 탐색’을 지워 시간을 절약하기 위함
  

최종 제출 코드

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

using namespace std;

int r, c;

bool dfs(vector<string>& maps, int nowr, int nowc)
{
	if (nowr < 0 || nowr >= r)
		return false;

	if (maps[nowr][nowc] != '.')
		return false;

	maps[nowr][nowc] = 'x';

	if (nowc == c - 1)
		return true;

	if (dfs(maps, nowr - 1, nowc + 1))
		return true;

	if (dfs(maps, nowr, nowc + 1))
		return true;

	return dfs(maps, nowr + 1, nowc + 1);
}

int main()
{
	cin >> r >> c;
	vector<string> maps(r);
	for (int i = 0; i < r; i++)
		cin >> maps[i];

	int answer = 0;
	for (int i = 0; i < r; i++)
	{
		if (dfs(maps, i, 0))
			answer++;
	}

	cout << answer;
}

결과

백트래킹처럼 재탐색의 여지를 주지 않으니 통과할 수 있었다

처음에는 ‘방향’만 고려한 그리디 문제인줄 알았으나
‘재방문’ 여지를 주지 않는 것 또한 ‘탐욕’스럽다고 생각되는 문제였다