BOJ No.15684[사다리 조작]

1. 언어 : JAVA

 

2. 난이도 : Gold 4

15684번: 사다리 조작

 

www.acmicpc.net

3. 풀이

생각해보면 쉬운 문제다 2개의 함수의 구현이 필요하다.

DPS와 check 함수

dps 는 말그래도 depth 탐색 함수고

check는 사다리가 정답(1->1, 2->2, 3->3 .. N->N)인지 확인해주는 함수이다.

또한 map[][] 에 넣을때 오른쪽으로 갈수 있는 아이는 1, 왼쪽으로 갈수있는 아이는 -1로 저장하였다.

그리고 알아야 할 점은, 브루트포스이며 백트래킹을 사용한다.

소스코드는 다음과 같다.

 

4. 소스코드

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

public class Main {
	public static BufferedReader br = null;
	public static BufferedWriter bw = null;
	public static int N = 0;
	public static int M = 0;
	public static int H = 0;
	public static int result = 4;
	public static void main(String [] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String [] input = br.readLine().split(" ");
		N = Integer.parseInt(input[0]);
		M = Integer.parseInt(input[1]);
		H = Integer.parseInt(input[2]);
		
		int [][] map = new int[H+2][N+1];
		
		for(int i=0; i<M; i++) {
			input = br.readLine().split(" ");
			int a = Integer.parseInt(input[0]);
			int b = Integer.parseInt(input[1]);
			map[a][b] = 1;
			map[a][b+1] = -1;
		}

		dfs(1, 1, map, 0);			
		
		if(result <= 3) {
			bw.write(result + "\n");
		}
		else {
			bw.write("-1");
		}
		bw.flush();
	}
	public static void dfs(int y, int x, int [][] map, int ladder) throws IOException {
		if(ladder > 3) {
			return;
		}
		
		if(check(map)) {
			result = Math.min(result, ladder);
		}
		
		for(int i=y; i<=H; i ++) {
			for(int j=1; j<=N-1; j ++) {
				if(map[i][j] == 0 && map[i][j+1] == 0) {
					map[i][j] = 1;
					map[i][j+1] = -1;
					dfs(i, j, map, ladder+1);
					map[i][j] = 0;
					map[i][j+1] = 0;
				}
			}
		}
	}
	public static int [][] copy(int [][] map) {
		int [][] copy = new int[H+2][N+1];
		for(int i=0; i<H+2; i++) {
			for(int j=0; j<N+1; j++) {
				copy[i][j] = map[i][j];
			}
		}
		return copy;
	}
	
	public static boolean check(int [][] map) throws IOException {
		int y = 0;
		int x = 0;
		for(int n=1; n<=N; n++) {
			y = 1;
			x = n;
			while(true) {
				if(map[y][x] == 1) {
					y ++;
					x ++;
				}
				else if (map[y][x] == -1) {
					y ++;
					x --;
				}
				else if(map[y][x] == 0) {
					y ++;
				}
				
				if(y == H+1) {
					if(x == n) {
						
					}
					else {
						return false;
					}
					break;
				}
			}
		}
		
		return true;
	}
}