[BOJ] 백준 15684 사다리 조작

[문제]

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

 

 

[소스 코드]

import java.io.*;
import java.util.*;

import javax.print.attribute.standard.NumberUpSupported;
public class Main {
	static int n,h;
	static boolean[][] ladder;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		h = Integer.parseInt(st.nextToken());
		ladder = new boolean[h+1][n+1];
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			ladder[a][b] = true;
		}
		for(int i=0;i<=3;i++) {
			find(0,1,i);
		}
		System.out.println(-1);
	}
	private static void find(int cnt,int startH,int limit) {
		if(cnt>limit) return;
		if(possible()) {
			System.out.println(cnt);
			System.exit(0);
		}
		for(int i=startH;i<=h;i++) {
			for(int j=1;j<n;j++) {
				if(!ladder[i][j] && !ladder[i][j-1] && !ladder[i][j+1]) {
					ladder[i][j] = true;
					find(cnt+1,i,limit);
					ladder[i][j] = false;
				}
			}
		}
	}
	private static boolean possible() {
		for(int j=1;j<=n;j++) {
			int line = j;
			for(int i=1;i<=h;i++) {
				if(ladder[i][line])
					line++;
				else if(ladder[i][line-1])
					line--;
			}
			if(line!=j) return false; 
		}
		return true;
	}
}