[ 알고리즘 ] 코딩 - 백준 15684 - 사다리 조작. java

---

문제 링크

www.acmicpc.net/problem/15684

15684번: 사다리 조작

---

문제 개요

BOJ 15684 - (자바) 사다리 조작 - 구현 / DFS / 완전탐색

사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다.

예시 그림

사다리에 가로선을 추가해서, 사다리 게임의 결과를 조작하려고 한다. 이때, i번 세로선의 결과가 i번이 나와야 한다. 그렇게 하기 위해서 추가해야 하는 가로선 개수의 최솟값을 구하는 프로그램을 작성하시오.

 만약, 정답이 3보다 큰 값이면 -1을 출력한다. 또, 불가능한 경우에도 -1을 출력한다.

 

---

로직

Step 00. 입력을 받을 때 이미 이어져 있는 사다리의 방향을 정해서 저장하자. 예를 들어 1 2번 사이 연결이 되어 있다면 dir_map[1][2] = 1 ( 오른쪽 ) dir_map[2][1] = 2 ( 왼쪽 ) 과 같은 형식이다.

Step 01. 3보다 크면 더 진행 하지 않으므로, 0~3까지의 설치횟수를 제한한다. 이렇게 안하고 설치 / 비설치를 나누어서 했더니 시간초과를 만났다

Step 02. DFS를 수행한다. 현재 자신의 위치에 사다리가 없다면 설치를 해준다. 설치 / 파괴에는 2차원 배열을 이용해야한다. DFS에 넘기는 파라미터를 주의하자! idx는 높이를 의미하고 설치는 가로방향으로 해나가므로 다음 설치 높이는 현재 설치 중인 높이가 된다. ( i +1 이 아니다 ). 이 부분떄문에 시간을 많이 잡아먹었다..

Step 03. Step 01에서 정한 설치 횟수와 같은 경우에 전체 사다리를 체크한다.

Step 04. 과정을 수행하며 나온 최솟값이 정답!

 

---

코드

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

public class Main {
	private static int MIN;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stt = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(stt.nextToken()); // 가로 길이
		int M = Integer.parseInt(stt.nextToken());
		if (M == 0) {
			System.out.println(0);
			return;
		}
		int H = Integer.parseInt(stt.nextToken()); // 세로 높이

		int[][] dir_map = new int[H + 1][N + 1];
		for (int j = 1; j <= M; j++) {
			stt = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(stt.nextToken());
			int x = Integer.parseInt(stt.nextToken());
			dir_map[y][x] = 1; // 오른쪽
			dir_map[y][x + 1] = 2; // 왼쪽
		} // input end
		MIN = Integer.MAX_VALUE;
		boolean flag = false;
		for (int i = 0; i <= 3; i++) {
			int ans = i;
			process(1, 0, ans, N, M, H, dir_map);
			if (MIN != Integer.MAX_VALUE) {
				flag = true;
				break;
			}
		}
		if(flag)
			System.out.println(MIN);
		else
			System.out.println(-1);
	}

	private static void process(int idx, int cnt, int ans, int n, int m, int h, int[][] dir_map) {
		if (ans == cnt) {
			if (checkLedder(dir_map, n, h)) {
				MIN = MIN < cnt ? MIN : cnt;
			}
			return;
		}
		// 사다리 설치
		for (int i = idx; i <= h; i++) {
			for (int j = 1; j < n; j++) {
				if (dir_map[i][j] != 0 || dir_map[i][j + 1] != 0) { // 사다리 이미 존재 설치 x
					continue;
				} else { // 설치 가능
					dir_map[i][j] = 1;
					dir_map[i][j + 1] = 2;
					process(i, cnt + 1, ans, n, m, h, dir_map); // 설치
					dir_map[i][j] = 0;
					dir_map[i][j + 1] = 0;
				}
			}
		}
	}

	private static boolean checkLedder(int[][] dir_map, int n, int h) {
		int[] dx = { 0, 1, -1 }; // 우 좌

		for (int i = 1; i <= n; i++) {
			int y = 1;
			int x = i;
			while (y <= h) {
				if (dir_map[y][x] != 0) { // 연결된 곳 확인
					int dir = dir_map[y][x];
					int next_x = x + dx[dir];
					x = next_x;
				}
				y++;
			}
			if (x != i)
				return false;
		}
		return true;

	}
}