15684 사다리 조작

 

사다리 표시할 때,

만약 1번 세로선 -> 2번 세로선

사이에 가로선이 있다면 

배열에 map[1][2] = 1 표시를 해준다.

 

그래서 만약 1번 세로선에서 사다리를 타고 내려오면, 

오른쪽 (2번 세로선)으로  이동하면 되고,

 

2번 세로선에서 사다리를 타고 내려오면,

왼쪽(1번 세로선)으로 이동하면 된다.

 

 

 

 

 

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

public class Main {
	
	static int value;
	static int H;
	static int N;
	static int map[][];
	
	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());
		value = Integer.MAX_VALUE;
		map= new int[H+2][N+2];
		
		for(int i =0 ; i<M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b= Integer.parseInt(st.nextToken());
			
			map[a][b] = 1;
		}	
			
		int result = 0;
		
		// 가로선이 없다면 사다리 타고 쭉 내려가면 됨.
		if(M==0) {
			result = 0;
			
		}else {
			dfs(0,1);			
			result = (value==Integer.MAX_VALUE? -1 : value);
			
		}
	
		System.out.println(result);
	}	
	
	
	public static void dfs(int count, int number) {			
	
		// 3보다 큰 값이면
		if(count>3) {			
			return;
		}		
		
		
		// 최소 개수 value 가 이미 정해졌는데, 그보다 더 큰 개수(count)를 찾는다면 그만 함. 
		if(count>value) {
			return;
		}
		
		boolean flag = true;		
	
		for(int i=1; i<=N; i++) {
			
			// i번 세로선에서 사다리 타기 결과가 i인지 여부 			
			if(!game(i)) {
				flag = false;
			}			
		}
		
		// 모든 i번 세로선의 결과가 i번이 나왔을 때 더 큰 개수를 찾을 필요 없으니, 그만함. 
		if(flag) {			
			value = count;
			return;
		}

		
		// i = number 인 곳부터 진행함. 
		// 즉 점점 사다리를 아래 방향으로 만든다고 생각하면 됨.
		for(int i=number; i<=H; i++) {
			
			for(int j= 1; j<N; j++) {
				
				// 1) 현재 자리에도 사다리가 없고 => map[i][j]== 0	
				// 2) 양 옆에 사다리가 없을 때 => map[i][j-1] == 0 , map[i][j+1] == 0 
				if(map[i][j]==0 && map[i][j-1]==0 && map[i][j+1]==0) {
					
					map[i][j] = 1;
					dfs(count+1, i);
					map[i][j] = 0;
					
				}			
			}
		}		
	}
	
	// 사다리 타고 내려가기
	public static boolean game(int a) {
		
		// 사다리 타기 맨 윗줄부터 시작 
		int x = 1;
		int y = a;		
	
		while(x <=H) {			
			
			
			// 현재 위치에 사다리가 있으면 오른쪽 이동
			if(map[x][y]==1) {
				y++;
				
			// 현재 위치 왼쪽에 사다리가 있으면 왼쪽 이동 
			}else if(map[x][y-1]==1 ) {
				y--;
				
			}
			x++;
		}
		
	
		// i번 세로선의 결과가 i가 나옴 
		if(a== y) {			
			return true;
		}else {
			
			return false;
		}
		
	}	
}

 

참고 블로그 : https://infinitecode.tistory.com/29

[PS] 백준15684 : 사다리 조작(Java)