백준(15684번) - 사다리 조작(Java) (구현)

 내가 푼 방식은 0개부터 3개까지 사다리를 임의로 배치하고, 일일이 내려가보는 노가다 식으로 풀었지만,  dfs 식으로 푸는 방법도 존재할 것이라고 생각하지만 무식한 방법도 통과가 되었으니 다시 해야하는 고생은 없어져서 다행이다.

<문제>

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

15684번: 사다리 조작

---

<소스코드>

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


public class Main
{
	static int n, m, h;
	static int ans = 4;
	static boolean[][] ladder;
	
	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());
		
		ladder = new boolean[h+1][n+1];
		
		for(int i = 0 ; i < m ; i++)
		{
			st = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			ladder[a][b] = true;
		}
		
		for(int i = 0 ; i <= 3 ; i++)
		{
			Combination(0, i);
		}
		
		if(ans == 4) ans = -1;
		
		System.out.println(ans);
	}
	
	public static void Combination(int cnt, int lim)
	{
		if(cnt == lim)
		{
			//사다리 타기 시작
			if(down()) ans = Math.min(ans, cnt);
			return;
		}
		
		for(int i = 1 ; i <= h ; i++)
		{
			for(int j = 1 ; j <= n ; j++)
			{
				if(!ladder[i][j] && !link(i, j))
				{
					ladder[i][j] = true;
					
					Combination(cnt+1, lim);
					
					ladder[i][j] = false;
				}
			}
		}
	}
	
	public static boolean link(int x, int y)
	{
		if(y > 1 && ladder[x][y-1]) return true;
		
		if(y+1 <= n && ladder[x][y+1]) return true;
		
		return false;
	}
	
	public static boolean down()
	{
		for(int p = 1 ; p <= n ; p++) //사다리 선택
		{
			int now = p;
			for(int d = 1 ; d <= h ; d++)
			{
				if(now < n && ladder[d][now]) now++;
				else if(now > 1 && ladder[d][now-1]) now--;
			}
			
			if(now != p) return false;
		}
		
		return true;
	}
}