[백준BOJ] 3109번 빵집.java

 

백준 저지에서 빵집을 자바를 통해 풀어 보았다. 

 

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

3109번: 빵집

3109번 빵집.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

3109번 빵집

문제

유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다.
원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 중에, 가스비가 제일 크다는 것을 알게되었다. 따라서 원웅이는 근처 빵집의 가스관에 몰래 파이프를 설치해 훔쳐서 사용하기로 했다.
빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다.
원웅이는 가스관과 빵집을 연결하는 파이프를 설치하려고 한다. 빵집과 가스관 사이에는 건물이 있을 수도 있다. 건물이 있는 경우에는 파이프를 놓을 수 없다.
가스관과 빵집을 연결하는 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 한다. 각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할 수 있고, 각 칸의 중심끼리 연결하는 것이다.
원웅이는 가스를 되도록 많이 훔치려고 한다. 따라서, 가스관과 빵집을 연결하는 파이프라인을 여러 개 설치할 것이다. 이 경로는 겹칠 수 없고, 서로 접할 수도 없다. 즉, 각 칸을 지나는 파이프는 하나이어야 한다.
원웅이 빵집의 모습이 주어졌을 때, 원웅이가 설치할 수 있는 가스관과 빵집을 연결하는 파이프라인의 최대 개수를 구하는 프로그램을 작성하시오.

설명

어렵고 짜증났던 문제이다. 천천히 살펴보자.

 

가스관부터 빵집까지 여러 개의 경로가 존재할 수 있는데 이 중 중복되지 않으면서 설치하는 있는 최대의 파이프라인 개수를 구해야 한다. 존재할 수 있는 모든 경로를 구하게 되면 시간 초과를 피할 수 없다. 

 

파이프라인은 오른쪽 위 대각선, 오른쪽, 오른쪽 아래 대각선으로 연결할 수 있다. 파이프라인을 최대한 많이 설치하려면 파이프라인을 최대한 빽빽하게 설치해야한다. 그래서 오른쪽 위 대각선, 오른쪽, 오른쪽 아래 대각선 순서로 연결시켰다.

 

파이프라인이 지나가는 경로는 두 가지 종류가 있다. 빵집까지 연결되는 경로와 그렇지 않는 경로이다. 어떠한 상황이든 이미 존재하는 경로라면 다른 파이프라인이 올 이유가 없다. 빵집까지 연결되는 경로라면 중복으로 설치할 수 없으므로 다른 파이프라인이 올 수 없다. 연결되지 않는 경로라면 해당 경로에 접근해도 어차피 연결되지 못하기 때문에 파이프라인이 올 필요가 없다. 따라서 의미 없는 반복을 줄이기 위해 파이프라인의 설치 위치마다 '.'대신 'o'로 표시해줬다. 파이프라인이 이미 지나간 위치라면 다른 파이프라인이 접근하지 못하게 하기 위함이다.

 

만약 파이프라인이 빵집에 연결되었다면 해당 경로의 출발점으로부터 출발하는 모든 경로 또한 멈춰야한다. 한 출발점에서는 오직 하나의 경로만 존재할 수 있기 때문이다. 만약 멈추지 못하면 출발점은 하나인데 경로를 따라 도착지점은 두 개 이상이 되어 정확한 정답을 구할 수 없게 된다.

코드

//3109번 빵집.java
package com.ssafy.boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 빵집_3109 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static String line;
		
	static int R;
	static int C;
	static char[][] road;
	static int dI[] = {-1,0,1};
	static int dJ[] = {1,1,1};
	static int answer;
	static boolean check;
	
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine(), " ");
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		road = new char[R][C];
		answer=0;		
		for(int i=0;i<R;i++) {
			line = br.readLine();
			for(int j=0;j<C;j++) {
				road[i][j] = line.charAt(j);
			}
		}
		
		for(int i=0;i<R;i++) {
			check=false;
			pipeLine(i,0);
		}
		System.out.println(answer);
	}
	
	static void pipeLine(int i, int j) {
		if(j==C-1) {
			answer++;
			check=true;
			return;
		}
		for(int d=0;d<3;d++) {
			int nextI = i+dI[d];
			int nextJ = j+dJ[d];
			if(0<= nextI && nextI<R && 0<=nextJ && nextJ < C) {
				if(road[nextI][nextJ]=='.') {
					if(check)return;
					road[nextI][nextJ]='o';
					pipeLine(nextI,nextJ);
				}
			}
		}
	}
}