백준 15684 사다리 조작

사다리 조작 링크:https://www.acmicpc.net/problem/15684

15684번: 사다리 조작

다음 문제를 사다리가 주어 졌을때 i번째에서 시작하여 i번째로 가기위해 놓아야할 최소의 선분 갯수를 구하는 문제 입니다.

그림 실력이 너무 하타치라서 ㅈㅅㅈㅅ

쨋든 다음 사다리가 주어 졌을때 모든 i가 i로 가기위해서는 다음과 같이 두개의 선이 필요합니다 

이번문제는 브루트 포스를 이용하여 풀어 보았습니다.

모든 경우의 수를 구해서 최적의 경우의 수를뽑아 보았습니다.

따라서 모든 경우의 수를 구하기 위해 DFS를 사용했습니다.

사실 중복되는 경우를 백트레킹을 사용해서 처리하려고 했는데 생각보다 찔끔 복잡하더라구요..ㅋ

따라서 백트레킹은 다음기회에 풀어보겠습니다.

 

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

public class 사다리조작 {
	static int N, M, H;// 세로 가로 놓을수 있는 위치의 갯수
	static boolean[][] ischecked;// 가로의 선분이 연결되어 있는지 확인
	static boolean pass;
	static int[] movx = { 1, -1 };
	static int minimumAddedLine;

	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());

		ischecked = new boolean[H + 1][N + 1];
		minimumAddedLine = 0;
		pass = false;
		int y = 0, x = 0;

		for (int m = 0; m < M; m++) {
			st = new StringTokenizer(br.readLine());
			y = Integer.parseInt(st.nextToken());
			x = Integer.parseInt(st.nextToken());
			ischecked[y][x] = true;
		}

		for (int i = 0; i <= 3; i++) {
			minimumAddedLine = i;

			dfs(1, 1, 0);
			if (pass) {
				System.out.println(i);
				return;
			}
		}
		System.out.println(-1);
	}

	private static void dfs(int y, int x, int count) {
		if (count == minimumAddedLine) {
			for (int i = 1; i <= N; i++) {
				if (!iToi(i)) {
					return;
				}
				if (i == N) {
					pass = true;
				}
			}
		}

		for (int i = 1; i < N; i++) {
			for (int j = 1; j <= H; j++) {
				if (pass) {
					return;
				}

				if (ischecked[j][i]) {
					continue;
				}
				if (i == 1) {
					int newx = i + movx[0];
					if (!ischecked[j][newx]) {
						ischecked[j][i] = true;
						dfs(j, i, count + 1);
						ischecked[j][i] = false;
					}
				} else if (i == N) {
					int newx = i + movx[1];
					if (!ischecked[j][newx]) {
						ischecked[j][i] = true;
						dfs(j, i, count + 1);
						ischecked[j][i] = false;
					}
				} else {
					int newx1 = i + movx[0];
					int newx2 = i + movx[1];
					if (!ischecked[j][newx1] && !ischecked[j][newx2]) {
						ischecked[j][i] = true;
						dfs(j, i, count + 1);
						ischecked[j][i] = false;
					}
				}
			}
		}
	}

	private static boolean iToi(int x) {
		int origin = x;
		for (int i = 1; i <= H; i++) {
			if (x == 1) {
				if (ischecked[i][x]) {// 연결이되있다면 이동
					x = x + 1;
				}
			} else if (x == N) {
				if (ischecked[i][x - 1]) {
					x = x - 1;
				}
			} else {
				if (ischecked[i][x]) {
					x = x + 1;
				} else if (ischecked[i][x - 1]) {
					x = x - 1;
				}
			}

			if (i == H) {
				if (origin == x) {
					continue;
				} else {
					return false;
				}
			}
		}
		return true;
	}
}

dfs함수에서 i와 j가 계속 1부터 시작하게 해놔가지고 시간초과날까봐 조마조마했는데 골드5라서그런지 시간을 널널하게 주더라구요ㅎ...(풀어도 푼것같지않은 느낌적인 느낌)

다음번에 다시풀게되면 i와 j에 대해서도 최적화를 해줘야 겠네요