[백준] 15684 사다리 조작

문제

---

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

15684번: 사다리 조작

 

풀이

---

우선 사다리를 놓는 경우는 모든 경우를 탐색했다.

놓은 사다리 개수가 3개를 넘어가면 바로 return 하여 끝내줬다.

static void permutation(int r, int c, int cnt) {
	if(cnt > 3) {
		return;
	}
	
	
	if(gameStart()) {
		if(answer == -1) {
			answer = cnt;
			return;
		}			
		answer = Math.min(answer, cnt);
		return;
	}
	
	for(int j = c ; j < N - 1 ; j++) {
		for(int i = 0 ; i < H ; i++) {
			if(j == c && i == 0) {
				i = r;
			}
			
			if(map[i][j]) { continue;}
			
			if(j != 0 && map[i][j - 1]) {continue;}
			
			if(j != N - 2 && map[i][j + 1]) {continue;}
			
			map[i][j] = true;
			permutation(i, j, cnt + 1);
			map[i][j] = false;
		}
	}
}

위와 같이 풀이를 하였다.

해당 위치에 놓을 수 있다면 놓고 아니면 넘어간다.

놓을 수 있는지는 해당 위치에 사다리가 없고 양쪽에 사다리가 없으면 된다.

 

이렇게 사다리를 놓고, 게임을 시작하여 찾는다.

static boolean gameStart() {
	
	for(int i = 0 ; i < N ; i++) {
		int origin = i;
		
		for(int j = 0 ; j < H ; j++) {
			if(origin != 0) {
				if(map[j][origin -1]) {
					origin--;
					continue;
				}
			}	
			
			if(origin != N - 1) {
				if(map[j][origin]) {
					origin++;
				}
			}
		}			
		
		if(origin != i) {
			return false;
		}
	}
	
	return true;
}

사다리 게임하는건 해당 origin - 1열의  값이 true 면 origin-- 을 해서 줄을 왼쪽으로 이동한다.

origin 열의 값이 true 면 origin++ 을 하여 줄을 오른쪽으로 이동한다.

 

이렇게 해서 시작했을때 열과 현재 열과 같으면 넘어간다.

 

 

 

<전체코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	
	static boolean[][] map;
	static int N, H, M;
	static int answer;
	
	public static int parseInt(String string) {
		return Integer.parseInt(string);
	}
	
	public static void main(String[] args) throws IOException{	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = parseInt(st.nextToken());
		M = parseInt(st.nextToken());
		H = parseInt(st.nextToken());
		
		map = new boolean[H][N - 1];
		for(int i = 0 ; i < M ; i++) {
			st = new StringTokenizer(br.readLine());
			
			int h = parseInt(st.nextToken()) - 1;
			int n = parseInt(st.nextToken()) - 1;
			
			map[h][n] = true;
		}		
		
		answer = -1;
		permutation(0, 0, 0);
		
		System.out.println(answer);
	}
	
	static void print() {
		
		System.out.println("map: ");
		for(int i = 0 ; i < H ; i++) {
			for(int j = 0 ; j < N - 1 ; j++) {
				if(map[i][j]) {
					System.out.print("- ");
				}
				else {
					System.out.print(". ");
				}
			}
			System.out.println();
		}
	}
	
	static boolean gameStart() {
		
		for(int i = 0 ; i < N ; i++) {
			int origin = i;
			
			for(int j = 0 ; j < H ; j++) {
				if(origin != 0) {
					if(map[j][origin -1]) {
						origin--;
						continue;
					}
				}	
				
				if(origin != N - 1) {
					if(map[j][origin]) {
						origin++;
					}
				}
			}			
			
			if(origin != i) {
				return false;
			}
		}
		
		return true;
	}
	
	static void permutation(int r, int c, int cnt) {
		if(cnt > 3) {
			return;
		}
		
		
		if(gameStart()) {
			if(answer == -1) {
				answer = cnt;
				return;
			}			
			answer = Math.min(answer, cnt);
			return;
		}
		
		for(int j = c ; j < N - 1 ; j++) {
			for(int i = 0 ; i < H ; i++) {
				if(j == c && i == 0) {
					i = r;
				}
				
				if(map[i][j]) { continue;}
				
				if(j != 0 && map[i][j - 1]) {continue;}
				
				if(j != N - 2 && map[i][j + 1]) {continue;}
				
				map[i][j] = true;
				permutation(i, j, cnt + 1);
				map[i][j] = false;
			}
		}
	}
}