[백준] 빵집_3109 - 공룡 루디

 빵집 3109번 solved.ac 골드 2

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

3109번: 빵집

 

 문제 해석 및 풀이

빵집 문제는

원웅이가 가스관과 자신의 빵집을 연결할 수 있는 파이프라인의 최대 개수를 구하는 문제입니다.

 

왼쪽 첫 번째 열에는 가스관이 있고 가장 오른쪽 열에는 원웅이의 빵집이 있습니다.

 

이 문제에서 중요한 점은 파이프라인은 겹칠 수 없고,

최대로 연결할 수 있는 파이프 라인을 구해야 합니다.

 

첫 번째 열에서 각 행마다 파이프를 연결할 수 있으며

중간에 x표로 된 곳은 건물이 설치된 곳으로 파이프를 놓을 수 없습니다.

또한 파이프 연결은 오른쪽 위, 오른쪽, 오른쪽 아래 3방향으로 파이프를 연결할 수 있습니다.

 

시간제한은 1초, 메모리 제한은 256MB

입력의 조건은 1 <=R <=10,000, 5 <=C <=500입니다.

 

이 문제는 백트래킹과 그리디 알고리즘을 함께 적용해 깊이우선탐색을 해야 합니다.

만약 첫 열의 첫 행에서 마지막 열의 마지막행에 파이프를 대각선으로 연결하게 되면

아무리 행이 많아도 연결할 수 있는 파이프라인은 1개입니다.(다리를 연결하는 문제랑 비슷)

 

이러한 경우를 제외하지 않고 모두 탐색하게 된다면 한 파이프를 설치할 때

최대 약 500의 열마다 3개의 방향으로 분기되기 때문에 시간 초과가 되기 때문입니다.

 

따라서 그리디 알고리즘을 적용하여 오른쪽 위, 오른쪽, 오른쪽 아래로 우선순위를 주어야 합니다.

즉 파이프 라인을 연결할 때 마지막 열(빵집)의 가장 위쪽 행부터 파이프를 연결해야 최대로 연결할 수 있는

상황이 나오게 됩니다.

 

그리고 연결한 파이프는 그대로 유지해야지 다음 행에서 파이프를 연결할 때 겹치는지 안 겹치는지

확인할 수 있고 그리디한 방법으로 연결을 시도하고 연결이 실패한 파이프도 유지해야 다음 행에서 탐색할 때

해당 칸에서 분기를 안 하게 되어 시간 초과가 안나게 됩니다.(이렇게 안했을 때 시간초과가 났습니다.)

 

package b3109_빵집;

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

public class Main {

	static int R, C;
	static char[][] map;
	static boolean isTrue;
	static int max = 0;

	public static void backtracking(int start, int cnt, int id) {
		if (cnt == C - 1) {
			max++; //연결이 되면 개수 증가
			isTrue = true; // 더이상 분기 안되게 설정하는 flag
			return;
		}

		for (int i = start - 1; i <= start + 1; i++) {
			if (i >= 0 && i < R)
				if (map[i][cnt + 1] == '.') {
					map[i][cnt + 1] = 'p';
					backtracking(i, cnt + 1, id);
					if (isTrue) // 설치가 완료됐으면 빠져나가야함
						break;
				}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] inp = br.readLine().split(" ");

		R = Integer.parseInt(inp[0]);
		C = Integer.parseInt(inp[1]);
		map = new char[R][C];
		for (int i = 0; i < R; i++)
			map[i] = br.readLine().toCharArray();

		for (int id = 0; id < R; id++) { // 모든 행마다 설치 시도
			isTrue = false;
			backtracking(id, 0, id);
		}
		System.out.println(max);
	}
}