BOJ - 사다리 조작 15684번 (JAVA)

❓ 문제 - 백준 사다리 조작 15684번 - JAVA 풀이법

출처 

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

 

📝 문제해결법

1. 이 문제는 DFS+구현으로 풀었다.

• 사다리가 이미 존재하는 곳엔 map엔 true 처리해준다.
• map에서 x, y가 true라면 x ~ x, y ~ y+1 에 사다리가 놓아져있다는 의미이다.
• dfs(조합)의 경우로 사다리가 존재하지 않는 구간에서 사다리를 1~3개까지 놓을 수 있는 경우의 수를 구한다.
• 만약 놓으려는 사다리 자리가 왼쪽 (x,y-1)에 사다리가 놓아져 있지 않고, 오른쪽(x, y+1)에도 사다리가 놓아져 있지 않으면 사다리를 놓을 수 있기 때문에 사다리를 놓는다.
• 만약 (depth = 사다리를 놓은 갯수) 가 현재 ans(사다리 최소값)보다 높게 탐색을 할 경우라면 return 한다.
• check1() 이라는 함수를 활용하여 현재 사다리가 놓여진 상태에서 모든 열에 대해 현재 i번쨰 열이 사다리를 통해 이동해서 i번째에 도달할 수 있는지 체크한다. 구현 방식은 하나의 열부터 차례대로 밑의 행으로 이동하면서 만약 현재 열 -1에 사다리가 놓여져 있다면 왼쪽으로 이동 후 밑의 행으로 이동하고, 만약 현재 열 + 1에 사다리가 놓여져 있다면 오른쪽으로 이동하고 밑의 행으로 이동한다.
• 모든 행까지 이동한 후에 현재 나의 열과 처음나의 열이 값이 일치하지 않다면 false를 반환하고, 모든 열이 사다리 이동 후 자신의 처음 열과 같은 곳에 도착한다면 true를 반환한다.

 

 

💻 소스코드

// BOJ - 사다리 조작 (15684번)
// DFS

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

public class Main_15684 {

	public static int n, m, ans;	
	public static class Node {
		int x;
		int y;

		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	public static ArrayList<Node> list; 
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
			n = Integer.parseInt(st.nextToken());
			list = new ArrayList<>();
			boolean[][] map = new boolean[n+2][m+2];
			for(int i=0;i<k;i++) {
				st = new StringTokenizer(br.readLine(), " ");
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				map[x][y] = true;
			}



			ans = 4;
			list = new ArrayList<>();

			for(int i=1;i<=n;i++) {
				for(int j=1;j<=m;j++) {
					if(!map[i][j]) {
						list.add(new Node(i, j));
					}
				}
			}

			boolean[][] map_copy = new boolean[n+1][m+1];

			for(int p=1;p<=n;p++) {
				map_copy[p] = map[p].clone();
			}

			dfs(0, 0, map_copy);

			if(ans == 4) {
				System.out.println(-1);
			} else {
				System.out.println(ans);
			}


	}

	public static void dfs(int depth, int start, boolean[][] map_copy) {
		if(depth >= ans) return;

		if(check1(map_copy)) {
			ans = depth;
			return;
		}

		for(int i=start;i<list.size();i++) {
			Node node= list.get(i);
			if(map_copy[node.x][node.y-1] || map_copy[node.x][node.y+1]) continue;
			map_copy[node.x][node.y] = true;
			dfs(depth+1, i+1, map_copy);
			map_copy[node.x][node.y] = false;
		}
	}

	public static boolean check1(boolean[][] map_copy) {
		for(int j=1;j<=m;j++) {
			int now = j;

			for(int i=1;i<=n;i++) {
				if(map_copy[i][now-1]) {
					now -= 1; 
				} else if(map_copy[i][now]) {
					now += 1;
				}
			}

			if(now != j) {
				return false;
			}
		}


		return true;
	}

}