[BOJ 3109] 빵집

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

3109번: 빵집

 

- 문제 요약

 

유명한 제빵사 김원웅은 빵집을 운영 중이다.

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

빵집이 있는 곳은 R*C 격자로 표현할 수 있다.

첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다.

원웅이는 가스관과 빵집을 연결하는 파이프를 설치하려고 한다.

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

가스관과 빵집을 연결하는 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 한다.

각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할 수 있고, 각 칸의 중심끼리 연결하는 것이다.

원웅이는 가스를 되도록 많이 훔치려고 한다. 따라서, 가스관과 빵집을 연결하는 파이프라인을 여러 개 설치할 것이다.

이 경로는 겹칠 수 없고, 서로 접할 수도 없다. 즉, 각 칸을 지나는 파이프는 하나이어야 한다.

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

 

 

- 알고리즘 정리

 

DFS를 활용한 그리디 문제입니다.

파이프라인을 연결할 때 visited[][] 배열을 활용해서 방문 여부를 확인해줘야 합니다.

(이렇게 하지 않으면 한 가스관에 여러 개의 파이프라인이 생성될 수도....)

문제에서 김원웅의 빵집은 첫째 열에 있고, 마지막 열에서 끝나야 한다고 했으므로 dx[], dy[] 배열의 방향을 왼쪽아래 대각선, 아래, 오른쪽아래 대각선으로 설정해 주면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 200001
int r,c,arr[10001][501],result,dx[]={-1,0,1},dy[]={1,1,1};
bool flag,visited[10001][501];

void dfs(int x,int y){
	visited[x][y]=true;
	if(y==c){
		result++;
		flag=true;
		return;
	}
	for(int i=0;i<3;i++){
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx>=1&&nx<=r&&ny>=1&&ny<=c){
			if(arr[nx][ny]==1&&!visited[nx][ny]){
				dfs(nx,ny);
				if(flag){
					return;
				}
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>r>>c;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			char a;
			cin>>a;
			if(a=='.'){
				arr[i][j]=1;
			}
			else{
				arr[i][j]=0;
			}
		}
	}
	for(int i=1;i<=r;i++){
		flag=false;
		dfs(i,1);
	}
	cout<<result;
}

코드 제출 결과