[backjoon]15684 사다리 조작 java

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

15684번: 사다리 조작

삼성 문제 특성상 시키는 대로만 하면 되는데... 나의 고질적인 row/col의 헷갈림과 쓸데없는 반복문 돌림으로 고생했던 문제

문제는 백트래킹을 이용해서 풀면 된다.

삼성 문제의 경우 최대 횟수가 정해져있어서 이것을 잘 고려한다면 생각보다 백트래킹으로 인해 시간초과가 뜨진 않을까의 걱정을 덜 수도 있다.

풀이 포인트를 정리하자면, 

1. 사다리 게임을 통해 결과 확인 (처음부터 원하던 결과여서 조작이 필요하지 않는 경우도 있기에 제일 앞서 검증해야한다.)

2. 게임 조작 : 백트래킹으로 3번 안으로 검증하면 된다.

3. 시간 초과에 주의 하고자 최소 횟수가 나오면 바로 return 처리해서 빨리 끝내자.

추가로 사다리를 어떤 식으로 생각할지도 중요포인트라고 생각이 든다. 나는 사다리 선이 있는지 없는 지를 boolean 타입의 2차원 배열을 이용하였다. 

사다리를 만들때는 양 옆을 확인해주었고, 사다리 게임을 진행할 때는 도착한 지점에 왼쪽에 사다리가 있으면 오른쪽으로 가로 이동(<-)을, 오른쪽에 사다리가 있으면 왼쪽으로 이동하여(->) 세로 선을 변경하는 방식으로 진행하였다.

import java.io.*;
import java.util.*;

public class Main {
	static boolean[][] marked;
	static int N, M, H;
	static int answer;

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());// 세로선
		M = Integer.parseInt(st.nextToken());// 가로선
		H = Integer.parseInt(st.nextToken());// 세로선마다 가로선을 놓을 수 있는 위치의 개수

		marked = new boolean[H + 1][N + 1];
		answer = Integer.MAX_VALUE;
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());

			marked[r][c] = true;
		}
		controlLadder(1, 0);

		if (answer == Integer.MAX_VALUE)
			answer = -1;

		System.out.println(answer);
	}

	public static void controlLadder(int curIdx, int cnt) {
		if (cnt >= 4)
			return;
		
		if (ladderGame()) {
			answer = Math.min(answer, cnt);
			return;
		}
		for (int i = curIdx; i <= H; i++) {
			for (int j = 1; j < N; j++) {
				if (marked[i][j])
					continue;
				if (marked[i][j + 1])
					continue;
				if (marked[i][j - 1])
					continue;

				marked[i][j] = true;
				controlLadder(i, cnt + 1);
				marked[i][j] = false;
			}
		}
	}

	public static boolean ladderGame() {
		for (int i = 1; i <= N; i++) {// 가로 col
			int curCol = i;
			for (int j = 1; j <= H; j++) {// 세로 row
				if (marked[j][curCol])
					curCol++;
				else if (marked[j][curCol - 1])
					curCol--;
			}
			if (curCol != i)
				return false;
		}
		return true;
	}
}