[백준][15684][자바] 사다리 조작

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

15684번: 사다리 조작

문제풀이

생각보다 처리할게 많고 복잡해서 오래 걸렸다. (약 2시간...)

일단 사다리의 정보를 담는 2차원 map 배열을 만들었다. 사다리를 최대 3개까지 구하기 때문에 반복문을 통해 사다리의 개수를 조금씩 증가시켜주면서 최솟값을 찾으면 끝내도록 하였다.

 

DFS로 들어가면 이중반복문을 통해 해당 자리에 사다리를 놓을 수 있는지 검사하였다. 해당 자리에 놓을 수 있다면 사다리를 설치하고 재귀를 반복하였다.

 

그러다가 limit(사다리 놓을 수 있는 개수에 걸리면 첫 번째 자리부터 차례대로 자기 자신의 자리에 올 수 있는지 검사를 진행하였는데, y는 현재 사다리의 자리 x는 위에서 내려오는 것을 체크하는 변수를 선언하여 if문을 통해 맨 왼쪽과 맨 오른쪽 등을 고려하여 이동한 자리에 사다리가 존재하면 이동(y를 증가, 감소)하였다.

 

그리고 맨 밑으로 이동이 끝나면 i(시작한 자리)와 y(도착한 자리)가 같지 않다면 끝내고 같다면 끝까지 반복을 진행해 최솟값을 저장하였다.

 

코드

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

public class Main {
	static int N, M, H, min;
	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());
		H = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		min = Integer.MAX_VALUE;
		
		map = new int[M][N-1];
		
		for(int i=0; i<H; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			map[a-1][b-1] =1;
		}
		
		//0~3 추가 가로수 반복 -> 3보다 크면 -1 이니깐
		for(int i =0; i<=3; i++) {
			dfs(0,i,0);
			if(min != Integer.MAX_VALUE) break;
		}
		
		if(min == Integer.MAX_VALUE) min = -1;
		System.out.println(min);
	}
	private static void dfs(int cnt, int limit ,int start_x) {
		if(cnt == limit) {
			for(int i=0; i<N; i++) {
				//현재 자리하고 있는 사다리 
				int y =i;
				//지나간 사다리
				int x =0;
				while(true) {
					
					//맨 왼쪽
					if(y ==0) {
						//오른쪽 사다리 존재 검사
						if(map[x][y] == 1) y++;
					}
					//맨 오른쪽
					else if(y == N-1) {
						//왼쪽 사다리 존재 검사
						if(map[x][y-1] == 1) y--;
					}
					else {
						if(map[x][y] == 1) y++;
						else if(map[x][y-1] ==1) y--;
					}
					
					x++;
					if(x == M) break;
				}
				if(y != i) return; 
			}
			
			min = limit;
			return;
		}
		
		for(int i=start_x; i<M; i++) {
			for(int j=0; j<N-1; j++) {
				//해당 자리에 사다리 놓을 수 있는지 체크
				if(checkLadder(i,j) == false) continue;
				
				//사다리 설치
				map[i][j] = 1;
				dfs(cnt+1, limit, i);
				//사다리 제거
				map[i][j] = 0;
			}
		}
	}
	private static boolean checkLadder(int i, int j) {
		int[] dy = {1,0,-1};
		
		for(int k=0; k<3; k++) {
			int y = j+dy[k];
			
			if(y<0 || y>=N-1) continue;
			if(map[i][y] == 1) return false;
		}
		
		return true;
	}
}