백준 15684 : 사다리 조작

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

15684번: 사다리 조작

[ 문제풀이 ]

전형적인 시뮬레이션 문제로써 백트래킹을 통해 0~3개까지의 사다리를 설치할 수 있는 모든 경우를 다 돌려보면 되는 문제이다.

​사다리를 설치 후 가능한지 확인하기 위해 이동할 때 인덱스를 벗어나는 것을 방지하기 위해 넉넉하게 사다리 공간을 좌우로 +1칸씩 잡도록 하자.

​사다리를 설치할 수 있는지를 판단할 때 현재 좌표만 판단하면 안 된다. 사다리가 연속되면 안 되기 때문에 현재 좌표와 다음 좌표를 같이 확인해 줘야 한다.

현재 좌표에서 사다리를 설치할 수 있는지 판단할 경우 다음에 추가할 사다리는 이전 좌표에서는 설치할 필요가 없다.

이미 이전에 설치하는 모든 경우의 수를 다 확인하고 온 것이기 때문이다.

따라서 사다리를 추가한 다음에는 그다음 좌표부터 확인하도록 하자. 계속해서 (1, 1)부터 확인한다면 시간 초과가 발생할 것이다.

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

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;

	static int N, M, H, answer;
	static boolean flag;
	static int[][] map;

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());

		//인덱스 실수를 방지하기 위해 좌/우 공간을 +1 만큰 넉넉하게 잡아줌
		map = new int[H + 2][N + 2];

		for (int i = 0; i < M; ++i) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			map[a][b] = 1;
			map[a][b + 1] = 2;
		}

		//사다리 0~3개 추가
		for (int i = 0; i <= 3; ++i) {
			addLadder(1, 1, i, i);
			if (flag) break;
		}

		bw.write((flag == true ? answer : -1) + "\n");
		bw.flush();bw.close();br.close();
	}

	public static void addLadder(int y, int x, int key, int count) {
		if (flag) return;

		if (count == 0) {
			if (isVaild()) {
				flag = true;
				answer = key;
			}
			return;
		}

		for (int i = 1; i <= H; ++i) {
			for (int j = 1; j <= N - 1; ++j) {
				//이전 좌표는 사다리를 이미 설치해봤기 때문에 확인 x
				if (i == 1 && j == 1) {
					i = y; j = x;
				}
				
				//사다리를 설치할 수 없는 공간
				if (map[i][j] != 0 || map[i][j + 1] != 0) {
					continue;
				}
				
				//사다리 설치
				map[i][j] = 3;
				map[i][j + 1] = 4;
				addLadder(i, j + 1, key, count - 1);
				//설치한 사다리 제거
				map[i][j] = 0;
				map[i][j + 1] = 0;
			}
		}
	}

	public static boolean isVaild() {
		//i번 사다리가 i번에 도달하는지 확인
		for (int i = 1; i <= N; ++i) {
			if (!dfs(i, 1, i)) {
				return false;
			}
		}
		return true;
	}

	public static boolean dfs(int key, int y, int x) {
		if (y == H + 1) return key == x;
		
		if (map[y][x] == 0) {
			return dfs(key, y + 1, x);
		} else if (map[y][x] == 1 || map[y][x] == 3){
			return dfs(key, y + 1, x + 1);
		} else {
			return dfs(key, y + 1, x - 1);
		}
	}
}