백준 3109번 빵집

- 문제 설명

 

유명한 제빵자 김원웅은 빵집을 운영하고 있다. 원웅이는 지출을 줄이고자 근처 빵집의 가스관에 몰래 파이프를 설치하기로 하였고, 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다. (빵집이 있는 곳은 R*C 격자로 표현 가능)

 

원웅이가 설치할 수 있는 가스관과 빵집을 연결하는 파이프라인의 최대 개수를 구하는 프로그램을 작성해보자

 

 

- 입력

 

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

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

 

* 추가 조건

1) 빵집과 가스관 사이에는 건물이 있을 수도 있다. 건물이 있는 경우에는 파이프를 놓을 수 없다.

 

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

 

3) 가스관과 빵집을 연결하는 파이프라인의 경로는 겹칠 수 없고 서로 접할 수도 없다.

 

 

- 출력

 

원웅이가 놓을 수 있는 파이프라인의 최대 개수 출력

 

 

* 문제 풀이의 핵심

 

0. 알고리즘 : DFS 알고리즘

 

첫째 열의 첫 행부터 마지막 행까지 파이프를 DFS를 통한 재귀적 탐색을 통해 최적의 경로로 일일이 탐색해본다.

 

- 탐색 방향은 오른쪽위, 오른쪽, 오른쪽 아래 순으로 탐색해야, 추가조건 3)을 만족하면서 탐색할 수 있을 것이라 생각해 순서를 미리 정하였다. (배열을 통해 순서를 정하였음)

 

// (y,x) : 오른쪽위, 오른쪽, 오른쪽아래
int dir[3][2] = { {-1,1},{0,1},{1,1} };

 

 

1. 시간초과 해결

 

DFS를 통해 첫째 열의 모든 행을 재귀적으로 탐색하면서 파이프가 설치된 경로 순서에 따라 최대 개수를 탐색한다면 시간초과가 발생한다.

 

- 항상 최적의 경로를 탐색한다고 가정하고 경로를 이동할 때마다 파이프를 설치하고, 끝까지 도달할 수 있다면 놓을 수 있는 파이프라인의 개수를 세는 식으로 탐색한다.

 

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

map[ny][nx] = 'x';
ret = max(ret, dfs_search(r, c, ny, nx));

 

파이프라인이 설치되지 않았고 범위 내이면 파이프를 설치하고 다음 경로에도 설치 가능한지 재귀적으로 확인하였다.

 

 

- 소스코드

 

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

string map[10001];

// (y,x) : 오른쪽위, 오른쪽, 오른쪽아래
int dir[3][2] = { {-1,1},{0,1},{1,1} };

int dfs_search(int r, int c, int y, int x) {
	if (c - 1 == x) return 1;

	int ret = 0;

	int i;
	for (i = 0; i < 3; i++) {
		int ny = y + dir[i][0];
		int nx = x + dir[i][1];

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

		map[ny][nx] = 'x';
		ret = max(ret, dfs_search(r, c, ny, nx));

		if (ret) return ret;
	}

	return ret;
}

int install_pipe(int r, int c) {
	int ret = 0;

	int i;
	for (i = 0; i < r; i++) {
		ret += dfs_search(r, c, i, 0);
	}

	return ret;
}

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

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

	int i;
	for (i = 0; i < R; i++) {
		string str;
		cin >> str;

		map[i] = str;
	}

	cout << install_pipe(R, C) << "\n";
}

 

 

- 문제링크 : www.acmicpc.net/problem/3109

3109번: 빵집

 

 

- 제출한 코드

 

 

>  백준 아이디 : canoe726

>  사용언어 : C++

>  에디터 : Visual Studio 2017

>  궁금한점은 댓글로 남겨주세요