백준 15684번 사다리조작 (JAVA)

역시나 삼성 기출문제답게 시뮬레이션 + 완탐이지만, 생각보다 첫 발상이 까다로워서 꽤 오랜 시간 푼 문제이다. 왼쪽으로 가는 사다리를 1, 오른쪽으로 가는 사다리를 2로 놓고 모든 경우의 수에 사다리를 놓아 완탐을 돌면 답을 구할 수 있다.

 

1. 사다리를 놓을 위치를 완전탐색으로 정한다.

	private static void buildLadder(int x, int cnt) {
		if (flag) {
			return;
		}
		if (cnt == result) { // 기저조건
			if (check()) {
				flag = true;
			}
			return;
		}

		for (int i = x; i <= H; i++) {
			for (int j = 1; j < N; j++) {
				if (map[i][j] == 0 && map[i][j + 1] == 0) {
					map[i][j] = 1;
					map[i][j + 1] = 2;
					buildLadder(i, cnt + 1);
					map[i][j] = 0;
					map[i][j + 1] = 0;
				}
			}
		}
	}

2. 사다리를 놓은 후 사다리게임을 시작하여 모두 자기 자리로 들어가는지 확인한다.

	private static boolean check() {
		for (int i = 1; i <= N; i++) {
			int x = 1;
			int y = i;
			for (int j = 0; j < H; j++) {
				switch (map[x][y]) {
				case 1:
					y++;
					break;
				case 2:
					y--;
					break;
				}
				x++;
			}
			if (y != i) {
				return false;
			}
		}
		return true;
	}

코드 전문

package samsung;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_15684_사다리조작 {
	static int N, M, H, map[][];
	static Function<String, Integer> stoi = Integer::parseInt;
	static boolean flag = false;
	static int result = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = stoi.apply(st.nextToken());
		M = stoi.apply(st.nextToken());
		H = stoi.apply(st.nextToken());

		map = new int[H + 1][N + 1];

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = stoi.apply(st.nextToken());
			int y = stoi.apply(st.nextToken());
			map[x][y] = 1; // 왼
			map[x][y + 1] = 2; // 오
		}
		for (int i = 0; i <= 3; i++) {
			result = i;
			buildLadder(1, 0);
			if (flag) {
				break;
			}
		}
		System.out.println(flag ? result : -1);
	}

	private static void buildLadder(int x, int cnt) {
		if (flag) {
			return;
		}
		if (cnt == result) { // 기저조건
			if (check()) {
				flag = true;
			}
			return;
		}

		for (int i = x; i <= H; i++) {
			for (int j = 1; j < N; j++) {
				if (map[i][j] == 0 && map[i][j + 1] == 0) {
					map[i][j] = 1;
					map[i][j + 1] = 2;
					buildLadder(i, cnt + 1);
					map[i][j] = 0;
					map[i][j + 1] = 0;
				}
			}
		}
	}

	private static boolean check() {
		for (int i = 1; i <= N; i++) {
			int x = 1;
			int y = i;
			for (int j = 0; j < H; j++) {
				switch (map[x][y]) {
				case 1:
					y++;
					break;
				case 2:
					y--;
					break;
				}
				x++;
			}
			if (y != i) {
				return false;
			}
		}
		return true;
	}

}