백준 - 사다리 조작 (15684)

1. 문제

문제 링크

2. 풀이

2-1. 조건

1. 가로선을 연속해서 설치할 수 없다.
2. 가로선을 4개 이상 설치할 수 없다.

2-2. 풀이

사다리를 설치하는 모든 경우의 수를 탐색해서
모든 세로선이 매칭되는지 확인하는 문제입니다.

계획을 세우고 차근차근 하나씩 구현해 나갑시다.

계획 1 - 사다리 가로선의 설치 정보를 2차원 boolean배열에 저장합니다.

일단 제가 가장 중요하게 생각하는 부분부터 처리를 해보죠.
현실의 사다리 게임을 어떻게 컴퓨터 데이터화 시킬 것인가?

이전부터 강조했었지만 여기서 절반은 풀었다고 생각해도 과언이 아닙니다.
현실의 복잡한 문제를 컴퓨터가 이해할 수 있는 데이터화 하는 작업은
어떤 자료구조를 쓰느냐에 따라 문제가 어려워지기도 하고 쉬워지기도 합니다.
저는 2차원 boolean배열을 선언한 다음 설치된 가로선을 저장하겠습니다.

boolean[][] ladders = new boolean[H][N];

for (int i = 0; i < M; i++) {
   	stk = new StringTokenizer(br.readLine());
   	int a = Integer.parseInt(stk.nextToken()) - 1;
   	int b = Integer.parseInt(stk.nextToken()) - 1;
			
   	ladders[a][b] = true;
}

계획 2 - 사다리를 설치하는 모든 경우의 수를 탐색합니다.

백트래킹을 이용해서 구현합니다.
이 때 이미 설치돼있거나,
설치하려는 부분의 왼쪽이나 오른쪽에 사다리가 이미 설치된 경우는 제외합니다. (1번 조건)
그리고 이전 재귀에서 두 번째 가로 라인부터 탐색했다면
다음 재귀에서도 두 번째 가로 라인부터 탐색하도록 horizonLine을 인자로 넘겼습니다.

for (int i = horizonLine; i < H; i++) {
	for (int j = 0; j < N - 1; j++) {
		// 사다리가 이미 설치돼있을 때
		if (ladders[i][j]) continue;
				
		// 왼쪽에 사다리가 있거나, 오른쪽에 사다리가 있는 경우 (연속해서 설치 불가)
		if ((j - 1 >= 0 && ladders[i][j - 1]) || ladders[i][j + 1]) continue;
				
		ladders[i][j] = true;
		ret = Math.min(ret, min(fitCount + 1, i));
		ladders[i][j] = false;
	}
}

계획 3 - 세로선이 서로 매핑하는지 확인합니다.

첫 번째 반복문은 세로선을 하나씩 탐색하는 용도고
두 번째 반복문은 세로선에 대해서 설치된 가로선에 따라 이동시킵니다.
이동시킨 위치가 세로선과 매핑되지 않는다면 루프를 빠져나갑니다.
이 때, N - 1번 세로선까지 매핑이 된다면
N번째 세로선은 당연히 매핑되기 때문에 굳이 검사하지 않습니다.

// 사다리 검사
boolean flag = true;
		
for (int i = 0; i < N - 1; i++) {
	int pos = i;
			
	for (int j = 0; j < H; j++) {
		if (ladders[j][pos]) {
			pos++;
		}
		else if (pos - 1 >= 0 && ladders[j][pos - 1]) {
			pos--;
		}
	}
			
	if (pos != i) {
		flag = false;
		break;
	}
}

3. 전체 코드

import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static int N, M, H;
	static final int INF = 4;
	static boolean[][] ladders;
	
	static int min(int fitCount, int horizonLine) {
		// 기저 사례 3번 안에 성공시켜야 함
		if (fitCount > 3) return INF;
		
		// 계획 3 - 세로선이 서로 매핑하는지 확인합니다.
		// 사다리 검사
		boolean flag = true;
		
		for (int i = 0; i < N - 1; i++) {
			int pos = i;
			
			for (int j = 0; j < H; j++) {
				if (ladders[j][pos]) {
					pos++;
				}
				else if (pos - 1 >= 0 && ladders[j][pos - 1]) {
					pos--;
				}
			}
			
			if (pos != i) {
				flag = false;
				break;
			}
		}
		
		// 매핑된다면 설치 개수 리턴
		if (flag) return fitCount;
		
		int ret = INF;
		
		// 계획 2 - 사다리를 설치하는 모든 경우의 수를 탐색합니다.
		for (int i = horizonLine; i < H; i++) {
			for (int j = 0; j < N - 1; j++) {
				// 사다리가 이미 설치돼있을 때
				if (ladders[i][j]) continue;
				
				// 왼쪽에 사다리가 있거나, 오른쪽에 사다리가 있는 경우 (연속해서 설치 불가)
				if ((j - 1 >= 0 && ladders[i][j - 1]) || ladders[i][j + 1]) continue;
				
				ladders[i][j] = true;
				ret = Math.min(ret, min(fitCount + 1, i));
				ladders[i][j] = false;
			}
		}
		
		return ret;
	}
	
	public static void main(String[] args) throws Exception {
		StringTokenizer stk = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(stk.nextToken());
		M = Integer.parseInt(stk.nextToken());
		H = Integer.parseInt(stk.nextToken());
		
		ladders = new boolean[H][N];
		
		// 계획 1 - 사다리 가로선의 설치 정보를 2차원 boolean배열에 저장합니다.
		for (int i = 0; i < M; i++) {
			stk = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(stk.nextToken()) - 1;
			int b = Integer.parseInt(stk.nextToken()) - 1;
			
			ladders[a][b] = true;
		}
		
		int ans = min(0, 0);
		
		bw.write((ans == INF ? -1 : ans) + "");
		bw.close();
	}
}

비슷한 문제로는 백준 - 연구소가 있습니다.