[백준] 15684. 사다리 조작 - 골드4

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

15684번: 사다리 조작

 

문제 요약

세로 선의 개수 N, 가로 선의 개수 M, 세로 선마다 가로 선을 놓을 수 있는 위치의 개수 H가 주어진다.

현재 그어져 있는 가로 선의 정보가 주어질 때 (a b는 b번 세로선과 b+1번 세로선을 a번 점선 위치에서 연결했다는 의미이다) i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려고 한다. 추가해야 하는 가로선 개수의 최솟값을 출력하시오. 만약 정답이 3보다 큰값이면 -1을 출력한다.

 

문제 해결 아이디어

정답은 0, 1, 2, 3 중에 하나만 가능하다. 따라서 추가하는 가로선 수가 0일 때부터 3일 때까지 M개의 가로 선을 추가하여 가능한 경우 해당 가로선 수를 출력하고, 불가능하면 -1을 출력해 준다.

입력받는 방식은 주어진 가로선 정보에 따라 2차원 배열에 1과 2를 저장하게 되는데, 1을 만나면 오른쪽으로 가라는 뜻이고, 2를 만나면 왼쪽으로 가라는 뜻으로 저장해 준다.

입력받은 2차원 배열을 탐색할 때 1과 2를 만나거나(해당 위치에 가로선이 있는 경우) 이미 다음 칸에 1이 있다면(바로 옆에 가로선이 있는 경우) 가로선을 추가할 수 없으므로 continue를 해 주고, 가로선을 추가할 수 있는 경우에는 추가한 뒤에 재귀를 돌린다. 모든 경우에 대해 살펴 볼 것이기 때문에 재귀가 끝나면 해제도 해 준다. 

그렇게 원하는 정답까지 가로선을 추가했을 때 i가 i로 가는지 확인을 하고, 모두 간다면 최솟값을 갱신해 준다. 우리가 구해야 하는 건 최솟값이기 때문에 만약 추가해야 하는 가로선 수가 1일 때 정답이 되었다면 2와 3은 볼 필요가 없으니 break 해 준다.

정답인지 체크하는 check() 메소드는 current라는 변수를 두고 그 값을 왼쪽 오른쪽으로 움직이면서 사다리를 탄다. 가로선 끝까지 갔을 때 current가 i랑 값이 다르다면 실패한 것이다.

 

완성된 코드

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

public class Main {
	/*
	 * 1104ms
	 */
	static int N, M, H, ladder[][], min;

	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 int[H + 1][N + 1];

		for (int i = 0; i < M; i++) { // 가로선 입력받기
			st = new StringTokenizer(br.readLine(), " ");
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());

			ladder[r][c] = 1;
			ladder[r][c + 1] = 2; // 1을 만나면 오른쪽으로 2를 만나면 왼쪽으로
		}

		min = Integer.MAX_VALUE;
		for (int i = 0; i <= 3; i++) {
			dfs(1, 1, 0, i);
			if (min != Integer.MAX_VALUE)
				break;
		}
		System.out.println(min != Integer.MAX_VALUE ? min : -1);
	}

	private static void dfs(int r, int c, int drawCnt, int totalCnt) { // 현재까지 그린 횟수, 총 그릴 수 있는 횟수
		// i가 i로 가는지 확인해서 되면 끝
		if (drawCnt == totalCnt) {
			if (check()) {
				min = totalCnt;
				return;
			}
			return;
		}

		for (int i = r; i <= H; i++) {
			for (int j = c; j < N; j++) {
				if (ladder[i][j] == 1 || ladder[i][j] == 2 || ladder[i][j+1] == 1)
					continue;
				ladder[i][j] = 1;
				ladder[i][j + 1] = 2;
				dfs(r, c + 2, drawCnt + 1, totalCnt);
				ladder[i][j] = 0;
				ladder[i][j + 1] = 0;
			}
			c = 1;
		}
	}

	// 사다리를 내리는 과정 r = 1부터 H까지
	// 1을 만나면 c++, 2를만나면 c--
	// 하나라도 i가 i로 오는게 아니라면 안됨
	private static boolean check() {
		for (int i = 1; i <= N; i++) {
			int current = i;
			for (int r = 1; r <= H; r++) {
				if (ladder[r][current] == 1) {
					current = current + 1;
				} else if (ladder[r][current] == 2) {
					current = current - 1;
				}
			}

			if (current != i) {
				return false;
			}
		}
		return true;
	}
}