[BOJ3109/ Java]빵집

문제 요약

3109번: 빵집

3109번: 빵집

빵집?

가스관 훔치기아닌가?ㅋㅅㅋ

문제에서의 이동은 항상 첫번째열에서 출발해서 마지막 열로 이동한다.

즉, 우상 대각선, 오른쪽, 우하 대각선으로만 이동한다.

또한 가스관은 서로 겹칠 수 없다. 각 칸을 지나는 파이프는 하나이어야 한다.

입/출력

입력

지도의 크기 R과 C

빵집 근처의 모습이 ‘.’과 ‘x’로 나타난다.

‘.’은 지나갈 수 있는 곳, ‘x’는 건너갈 수 없는 곳이다.

처음과 마지막열은 항상 모두 ‘.’이다.

출력

첫째 줄에 원웅이가 놓을 수 있는 파이프라인의 최대 개수를 출력한다.

입력 제한 크기

배열의 크기가 최대 10000*500 = 5,000,000

접근 아이디어

1. 출발하는 첫 번째 열의 제일 위의 행에서부터 마지막 행까지 순서대로 마지막 열까지 도달할 수 있는지 dfs를 통해서 체크한다.
2. 이 때 탐색 순서가 중요한데, 항상 우상 대각선, 오른쪽 , 우하 대각선의 순으로 체크해야한다.
   • WHY? 제일 위의 행부터 탐색을 하는데, 위에서 출발한 파이프라인이 필드를 가로질러버리면 아래쪽에서는 아예 마지막 열까지 접근을 할 수가 없다.(파이프라인이 서로 겹칠 수 없기 때문)
3. 또한 이미 지나간 길은 아래쪽에서 출발할 때도 마찬가지로 다시 지나갈 필요가 없다.
   • 어짜피 글로 가면 시간낭비임…
   • 즉 dfs에서 visited를 체크를 하고 그걸 푸는 작업을 할 필요가 없다는 것이다.
   • → 만약 visited 체크를 하고 푸는 작업을 했으면 시간 초과가 났을 것…
4. 이미 끝까지 도착했다면 다음 방향을 볼 필요가 없음.
   • 우상 대각선, 오른쪽, 우하 대각선을 순서로 보는데, 오른쪽 하단 대각선을 선택하게 되는 경우는 아래쪽 행에서 출발하는 파이프 라인에 방해가 됨. 그래서 우하 대각선이 최선의 경우가 되는 상황은 없음.
   • 즉 끝까지 도착했다면 더 이상 해당 행에 대해서는 탐색을 진행하지 않고 dfs를 종료 해야 한다.

시간 복잡도

O(R*C)가 최악이지 않나…

구현 코드

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

public class B3109_빵집_조다민 {

	static int R, C, cnt;
	static char[][] field;
	static int[] direction = {-1, 0, 1};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		field = new char[R][C];
		
		for(int i = 0; i<R; i++) {
			field[i] = br.readLine().toCharArray();
		}
		cnt = 0;
		
    //모든 행에 대해서 탐색을 진행한다.
		for(int i = 0; i<R; i++) {
			dfs(i, 0);
		}
		
		System.out.println(cnt);
	}
	
	static boolean dfs(int r, int c) {		
		
		//제일 끝 행에 도달한 경우
		if(c == C-1) {
			cnt++;
			return true;
		}
		
		int nr, nc;
		
		for(int i = 0; i<3; i++) {
			nr = r+direction[i];
			nc = c+1;
			//범위 밖이거나, 이미 방문했거나, 건물이거나 -> 다음 방향 보자
			if(nr < 0 || nr>= R || nc <0 || nc>=C || field[nr][nc] != '.') {
				continue;
			}
			//파이프 체크하고
			field[nr][nc] = '-';
			//dfs로 다음 위치를 계속해서 탐색
			if(dfs(nr, nc)) { //만약 제일 끝 열에 도달했다면
				return true;
			}
		}
		
		return false;
	}
}