[삼성기출]백준15684 - 사다리 조작

package sw;

import java.io.*;

public class Main {
	static int N,M,H;
	static int[][] map, dir = {{0,1},{0,-1}};
	static boolean check(int x, int y) {
		if(x>=0 && x<map.length && y>=0 && y<map[x].length)
			return true;
		else return false;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] input = br.readLine().trim().split(" ");
		
		N = Integer.parseInt(input[0]);
		M = Integer.parseInt(input[1]);
		H = Integer.parseInt(input[2]);
		
		map = new int[H][N];
		res = 4;
		int x,y;
		for(int i=1; i<M+1; i++) {
			input = br.readLine().trim().split(" ");
			x = Integer.parseInt(input[0])-1;
			y = Integer.parseInt(input[1])-1;
			map[x][y] = i;
			map[x][y+1] = i;
		}
		
		dfs(0,0,0);
		System.out.println(res==4 ? -1 : res);
	}
	
	static int res;
	static void dfs(int count, int x, int y) {
		if(count > res) return;
		if(checkComplete()) {
			res = count;
			return;
		}
		if(count == 3) return;
		for(int m=x*N+y; m<H*N; m++) {
			x = m/N;
			y = m%N;
			if(y == N-1) continue;
			if(map[x][y] == 0 && map[x][y+1] == 0) {
				map[x][y] = M+count;
				map[x][y+1] = M+count;
				dfs(count+1, x, y+2);
				map[x][y] = 0;
				map[x][y+1] = 0;
			}
		}
	}
	static boolean checkComplete() {
		for(int j=0; j<N; j++) {
			if( j != move(0,j)) return false;
		}
		return true;
	}
	
	static int dx,dy;
	static int move(int x, int y) {
		while(x <= H-1) {
			if(map[x][y] != 0) {
				for(int d=0; d<2; d++) {
					dx = x + dir[d][0];
					dy = y + dir[d][1];
					if(check(dx,dy) && map[dx][dy]==map[x][y]) {
						x = dx;
						y = dy;
						break;
					}
				}
			}
			x++;
		}
		return y;
	}
}