boj, 백준) 3109 빵집 ( C++)

1. 문제 링크

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

3109번: 빵집

2. 문제 개요

 R x C크기의 칸이 있고 가장 왼쪽 열에서 가장 오른쪽 열까지 연결할 수 있는 파이프의 수를 계산.

 

3. 문제 힌트

 시간초과 -> C가 '20'만 되더라도 아무런 추가 조작 없이 순수 DFS로만 풀면 경우의 수는 3^19가 된다. 

( 시작에서 3가지로, 3가지가 또 3가지로.....3^(C-1) )

어떻게 하면 O(R*C)로 문제를 해결할것인지. 생각해보기.

 

Greedy -> 순서가 올바르지 못하면 갈 수 있음에도 불구하고 못 가는 경우가 생길 수 있다. 어떤 순서로 탐색을 해야 이런 일이 안 생길지 생각해보기.

 

4. 문제 풀기 

우선, DFS를 사용하여 탐색을 해야한다. 3번의 Greedy알고리즘을 적용하기 위해 가장 위쪽 행부터, 오른쪽 위, 오른쪽, 오른쪽 아래로 가는 순서대로 탐색을 한다.

 

그리고 막다른 길을 여러번 탐색할 필요는 없다.

보통 backtracking을 할 때는 방문했다가 다시 되돌아 갈 때 visited과 같이 방문 여부를 체크하고 원래대로 돌려놓는데 이 문제에서 backtracking 한다는 의미는 이미 막 다른 곳으로 가서 갈 길이 없어서 backtracking 한 것이므로 이 경우에는 방문을 취소하지 않고 그대로 남겨둔다. 그러면 거의 O(R*C)로 탐색이 가능해진다.

 

마지막으로, 파이프를 성공적으로 연결하면 DFS함수에서 true를 반환하여 재귀함수를 빠져나갈 때 추가 연산 없이 빠져나갈 수 있도록 한다.

 

main에서는 각 열당 1번씩 dfs함수를 실행하도록 한다.

 

5. 코드

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

int r, c;
string map[10000];
bool visited[10000][500] = { false, };
int ret = 0;
const int dx[] = { 1,1,1 };
const int dy[] = { -1,0,1 };


bool dfs(int cy, int cx)
{
	visited[cy][cx] = true;
	if (cx == c - 1)
	{
		ret++;
		return true;
	}

	for (int dir = 0; dir < 3; ++dir)
	{
		int nx = cx + dx[dir];
		int ny = cy + dy[dir];

		if (ny < 0 || ny >= r || visited[ny][nx]|| map[ny][nx] == 'x')
			continue;

		if (dfs(ny, nx))
			return true;
	}
	return false;
}

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

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

	for (int i = 0; i < r; ++i)
		dfs(i, 0);
	
	cout << ret;

	return 0;
}

6. 결과 사진

 

지적, 댓글 언제나 환영입니다~