[Java] 백준 15684번 사다리 조작

사다리 타기에서 시작하는 위치가 끝나는 위치가 같도록 만드는 문제입니다. (1-1, 2-2, 3-3 ...)

추가적으로 사다리의 가로선을 최대 3개까지 놓을 수 있는데
최소한의 사다리를 사용하여야 하며, 불가능한 경우 -1을 출력합니다.

사다리의 가로선은 연속해서 나올 수 없습니다.

사다리 가로선을 놓을 수 있는 곳들을 찾습니다.
놓으려고 하는 좌, 우에 가로선이 있는지 확인

없는 경우 DFS를 사용해서 사다리를 놓아줍니다.
놓은 상태에서 사다리타기를 진행하고 성공적으로 나오는지 확인합니다.

시간초과를 막기위해서 성공적인 케이스가 나올 경우 해당 값으로 최대치를 바꿔줘서
반드시 3번까지 탐색하지 않을 수 있게 해주었습니다.

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

public class Main {
	static int n;
	static int m;
	static int h;
	static int ans = 4;
	static boolean[][] map;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		h = Integer.parseInt(st.nextToken());
		
		map = new boolean[h+1][n+1];		
		for(int i=0; i<m; ++i) {
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			map[y][x] = true;
		}
		addLadder(0, 1, 1);
		ans = ans==4?-1:ans;
		bw.write(ans + "");
		bw.flush();
		bw.close();
	}
	public static void addLadder(int cnt, int y, int x) {
		boolean init = false;
		if(cnt >= ans) { // 가지치기
			return;
		}
		if(go()) {
			ans = Math.min(ans, cnt);
			return;
		}
		for(int i=1; i<=h; ++i) {
			for(int j=1; j<n; ++j) {
				if(!init) {
					i = y;
					j = x;
					init = true;
					if(j >= n) {
						continue;
					}
				}
				if(map[i][j] || map[i][j-1] || map[i][j+1]) {
					continue;
				}
				map[i][j] = true;
				addLadder(cnt + 1, i, j + 1);
				map[i][j] = false;
			}
		}
	}
	public static boolean go() {
		int[] arr = new int [n+1];
		for(int i=1; i<=n; ++i) {
			arr[i] = i;
		}
		for(int i=1; i<=h; ++i) {
			for(int j=1; j<n; ++j) {
				if(map[i][j]) {
					int tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
				}
			}
		}
		for(int i=1; i<=n; ++i) {
			if(arr[i] != i) {
				return false;
			}
		}
		return true;
	}
}