[백준] 3109 빵집 / 자바(Java)

문제

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

3109번: 빵집

 

---

해설

주어진 2차원 배열에서 1열과 마지막 열을 잇는 줄을 겹치지 않고 얼마나 많이 만들 수 있는가에 대한 문제입니다.

가장 많은 줄을 만들기 위해서 가장 위의 행부터 시작해 가능한 한 위쪽으로 줄을 만드는게 효율적이라 판단하는 그리디 방식을 통해 해결합니다.

 

DFS를 통해 가장 위쪽을 통해 넘어가는 줄을 만들고 진행 여부를 2차원 배열에 표시해 해당 위치로 중복해서 넘어가지 않도록 지정해줍니다. 또한 중간에 return을 통해 성공했다면 밑의 빈 칸을 건들이지 않도록 하여 최대한 위쪽에 파이프를 연결하는게 가능하도록 하였습니다.

주의점

• 파이프는 서로 겹치거나 접할 수 없다

---

코드

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

public class Main{
static int count=0;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		//입력부
		int R = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		
		char [][] arr = new char [R][C];
		for(int i=0;i<R;i++) {
			arr[i] = br.readLine().toCharArray();
		}
		
		int ans = 0;
		
		for(int i=0; i<R;i++) {
			if(calc(i, 0, arr)) ans++;
		}
		System.out.println(ans);
	}
	
	
	// 교차가안됨 -> 이상의 값만 사용 가능하도록
	static boolean calc(int r, int c, char [][] arr) {
		count++;
		int end = arr[0].length-1;
		arr[r][c] = 'p';
		int nextc = c+1;
		// 다음 이동 (상우, 우, 하우)
		if(0<=r-1 && arr[r-1][nextc]=='.' ) {
			if(nextc==end) {
				arr[r-1][nextc] = 'p';
				return true;
			}
			if(calc(r-1, nextc, arr)) return true; // 상우가 성공한 경우
		}
		
		if(arr[r][nextc]=='.' ) {
			if(nextc==end) {
				arr[r][nextc] = 'p';
				return true;
			}
			if(calc(r, nextc, arr)) return true;// 우 가 성공한경우
		}
		
		if(r+1<arr.length && arr[r+1][nextc]=='.' ) {
			if(nextc==end) {
				arr[r+1][nextc] = 'p';
				return true;
			}
			if(calc(r+1, nextc, arr)) return true; // 하우가 성공한 경우
		}
		
		// 상, 우, 하가 모두 실패한 경우
		return false; 
	}

	static boolean isInArray(int r, int c, char [][]arr) {
		if(0<=r && 0<=c && r<arr.length && c<arr[0].length) return true;
		else return false;
	}
}