[백준] 15684 - 사다리 조작

[문제링크]

15684번: 사다리 조작

 

0. 사다리게임의 모든 시작점이 자기 자신의 지점으로 끝나도록 조작하는 문제

 

1. 문제 조건에 3보다 큰 값이면 -1을 출력하게 되어 있으므로, 3까지만 검사해도 된다

 

2. 재귀를 통해 모든 가능한 경우의 수를 진행한다

• 현 위치와 좌/우 양쪽에 다 사다리가 없으면, 사다리를 설치한다 (isBridgeBuildAble)

 

3. 설치한 사다리가 3개가 되면, 문제의 조건인 i번 선수가 i번으로 가게 되는지 검사한다 (isLadderValid)

• 하나라도 실패하면 실패이므로, 즉시 반환한다

 

4. 설치한 사다리가 3개보다 적더라도 답이 나올 수 있다

• 1, 2개의 사다리에도 valid 여부를 검사한다
• 재귀함수의 인자에 사다리 설치 여부를 나타내는 isChanged flag를 두어 사다리 상태가 변경되었을때만 검사한다

 

5. 나온 결과값이 있다면 출력, 없다면(fail) -1을 출력한다

 

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

public class Main {
	
	static int fail = 500;
	static int[][] map;
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		int h = pint(st.nextToken());
		
		map = new int[h][n-1];
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			map[pint(st.nextToken())-1][pint(st.nextToken())-1]=1;
		}
		int ans = rec(0, 0, true);
		
		System.out.println(ans==fail?-1:ans);
	}
	
	static int rec(int cnt, int cur, boolean isChanged) {
		int ret = fail;
		int x = cur/map[0].length;
		int y = cur%map[0].length;
		if(isChanged && cnt<=3) {
			if(isLadderValid(map)) {
				return cnt;
			}
		}
		if(cnt>=3 || x>=map.length) {
			return fail;
		}
		
		//put if possible
		if(isBridgeBuildAble(map, x, y)) {
			map[x][y]=1;
			ret = Math.min(ret, rec(cnt+1, cur+2, true));
			map[x][y]=0;
		}

		//don't put
		ret = Math.min(ret, rec(cnt, cur+1, false));

		return ret;
	}
	
	static boolean isBridgeBuildAble(int[][]map, int x, int y) {
		if(map[x][y]==1
			|| (y-1>=0 && map[x][y-1]==1)
			|| (y+1<map[0].length && map[x][y+1]==1)) {
			return false;
		}
		return true;
	}
	
	static boolean isLadderValid(int[][] map) {
		for(int i=0; i<map[0].length; i++) {
			int cur = i;
			for (int j = 0; j < map.length; j++) {
				if(cur < map[0].length && map[j][cur]==1)cur++;
				else if(cur-1 >= 0 && map[j][cur-1]==1)cur--;
			}
			if(cur != i)return false;
		}
		
		return true;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}