[BOJ/백준 3109/C++] 빵집

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

3109번: 빵집

 

[문제 요약]

- 원웅이는 근처 빵집의 가스관에 몰래 파이프를 설치해 훔쳐서 사용하기로 했다.

 

- 빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다.

원웅이는 가스관과 빵집을 연결하는 파이프를 설치하려고 한다. 빵집과 가스관 사이에는 건물이 있을 수도 있다. 건물이 있는 경우에는 파이프를 놓을 수 없다.

 

- 가스관과 빵집을 연결하는 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 한다. 각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할 수 있고, 각 칸의 중심끼리 연결하는 것이다.

 

- 원웅이는 가스를 되도록 많이 훔치려고 한다. 따라서, 가스관과 빵집을 연결하는 파이프라인을 여러 개 설치할 것이다. 이 경로는 겹칠 수 없고, 서로 접할 수도 없다. 즉, 각 칸을 지나는 파이프는 하나이어야 한다.

원웅이 빵집의 모습이 주어졌을 때, 원웅이가 설치할 수 있는 가스관과 빵집을 연결하는 파이프라인의 최대 개수를 구하는 프로그램을 작성하시오.

 

[문제 조건]

- 첫째 줄에 R과 C가 주어진다. (1 ≤ R ≤ 10,000, 5 ≤ C ≤ 500)

- 다음 R개 줄에는 빵집 근처의 모습이 주어진다. '.'는 빈 칸이고, 'x'는 건물이다. 처음과 마지막 열은 항상 비어있다

- 시간 제한 : 1초

- 메모리 제한 : 256MB

 

[문제 풀이]

이 문제는 그리디 + 탐색 문제다.

 

mp[0][0] ~ mp[R-1][0]을 하나씩 확인하면서 가장 오른쪽 열까지 dfs방식을 이용하여 ( → , ↗ , ↘  과 같이 이동) 가장 오른쪽 열까지 도달 할 수 있으면 ans를 하나 증가시키고 지나온 경로를 ck배열에 체크해주면서 모든 mp[i][0]에 대하여 가장 오른쪽 열까지 도달한 횟수를 출력해주면 정답이 된다.

 

[소스 코드]

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

#define INF 987654321
#define pii pair<int,int>

using namespace std;

bool flag = false;
int R, C;
int ans = 0;
int dx[3] = { 1,1,1 };
int dy[3] = { -1,0,1 };
vector<vector<char>> mp;
vector<vector<bool>> ck;

void dfs(int row, int col)
{
	if (col == C - 1) { ans++; flag = true; return; }

	for (int i = 0; i < 3; i++)
	{
		int nrow = row + dy[i];
		int ncol = col + dx[i];

		if (nrow < 0 || ncol < 0 || nrow >= R || ncol >= C) continue;
		if (ck[nrow][ncol]) continue;
		if (mp[nrow][ncol] == 'x') continue;
		ck[nrow][ncol] = true;

		dfs(nrow, ncol);

		if (flag) return;
	}
}

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

	cin >> R >> C;
	mp.resize(R);
	for (int i = 0; i < R; i++) mp[i].resize(C);
	ck.resize(R);
	for (int i = 0; i < R; i++) ck[i].resize(C);

	for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++)
			cin >> mp[i][j];

	
	for (int i = 0; i < R; i++)
	{
		ck[i][0] = true;
		dfs(i, 0);
		flag = false;
	}

	cout << ans;
	return 0;
}

굳