[BAEKJOON] 15684. 사다리 조작

 

문제링크

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

15684번: 사다리 조작

 

1. 사다리는 최대 3개까지 놓을 수 있다.
2. 사다리를 놓을 수 있는 모든 경로에 사다리를 설치하고 다음 재귀로 넘어간다.
3. 정해 놓은 최대 갯수(0, 1, 2, 3) 만큼 사다리가 설치되면 check() 함수를 통해 i 번의 도착지가 i 번인지 확인한다.

 

package acmicpc.Gold4;

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

public class 사다리_조작 {

	static int n, m, h, map[][], ans;
	static boolean success = false;
	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());
		m = Integer.parseInt(st.nextToken());
		h = Integer.parseInt(st.nextToken());
		
		map = new int[h + 1][n + 1];
		ans = 0;
		// 설치된 사다리가 없으면 ans = 0
		if(m > 0) {
			
			for(int i = 0 ; i < m ; i++) {
				st = new StringTokenizer(br.readLine());
				
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());

				// 자신 기준 사다리가 오른쪽에 설치되어 있으면 1, 반대는 2
				map[a][b] = 1;
				map[a][b + 1] = 2;
			}
			
			ans = -1;
			// 설치 가능한 사다리 수는 3이므로 0부터 3까지 확인
			for(int i = 0 ; i <= 3 ; i++) {
				
				dfs(1, 0, i);
				if(success) {
					ans = i;
					break;
				}
			}
			
		}
		System.out.println(ans);
		
	}
	public static void dfs(int start, int cnt, int max) {
		
		// 기존의 과정에서 success 가 확인되면 return
		if(success) return;
		
		// 설치된 사다리 수와 max 값이 같으면 check() 검사하고 return
		if(cnt == max) {
			if(check()) success = true;
			return;
		}
		
		for(int j = start ; j < n ; j++) {
			for(int i = 1 ; i <= h ; i++) {
				// 설치 가능한 구역이 있다면 사다리를 설치하고 다음 재귀로
				// 그 다음 설치한 사다리를 0으로 취소하고 다음 반복문 실행
				if(map[i][j] == 0 && map[i][j + 1] == 0) {
					map[i][j] = 1;
					map[i][j + 1] = 2;
					dfs(j, cnt + 1, max);
					map[i][j] = map[i][j + 1] = 0;
				}
			}
		}
	}
	
	public static boolean check() {
		for(int i = 1 ; i <= n ; i++) {
			int start = i;
			for(int j = 1 ; j <= h ; j++) {
				// 1이면 오른쪽으로 이동, 2이면 왼쪽으로 이동
				if(map[j][start] == 1) start++;
				else if(map[j][start] == 2) start--;
			}
			if(start != i) return false;
		}
		
		return true;
	}
}