白駿15684号:はしご操作

問題の説明

方法

pseudocode

Main(){
	for(0개부터 3개까지의 선을 추가해 봅니다){
    	SelectBridge();
    }
    if(0~3개의 선을 추가해도 정답을 얻을 수 없다면){
    	sysout(-1);
    }else{
    	sysout(최솟값);
    }
}
SelectBridge(){ // 백트래킹을 실행합니다.
	if(h개의 선을 다 그엇다면){
    	if(Go(h개의 선을 추가한 board)){ // 모든 출발점이 자기자신에서 끝난다면
        	최솟값을 갱신합니다.
        }
    }
}

Go(){
	for(j는 1번째 세로줄부터 N번째 세로줄까지){
    	now = j번째 세로줄의 현재 column좌표
    	for(i는 1번째 점선부터 H번째 점선까지){
        	if(현재 위치가 0이 아니라면){
            	옆으로 이동합니다.(board[i][now]가 적힌 값 -1, -1은 인덱스라서)
            }
        }
        if(j번째 세로줄이 자기자신으로 도착하지 않는다면) return false // 하나의 j라도 틀리면 더 이상 검사할 필요 없이 false입니다.
    }
    return true;
}

正解

import java.util.*;

public class Main {
	static int N, M, H;
	static int MinVal = Integer.MAX_VALUE;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		H = sc.nextInt();
		int[][] BridgeBoard = new int[H][N]; // 문제를 유심히 읽어야 합니다. int[N][M]도 아니고 int[M][N]도 아니고 int[H][N]입니다.
		for (int m = 0; m < M; m++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			BridgeBoard[a - 1][b - 1] = b + 1; // 좌변은 인덱스이기 때문에 -1이 들어갔습니다. 1번다리에서 0번다리로 넘어갈 수 있다는 표시를 인덱스값 그대로 0을 하면 내려가는 0인지 옆으로가는 0인지 구분이 불가능합니다.  
			BridgeBoard[a - 1][b] = b; // 다리는 양방향입니다. b에서 b+1로 갈 수 있다는 건 b+1에서 b로도 갈 수 있다는 뜻입니다.
		}

		for (int h = 0; h <= 3; h++) { // 0개에서 3개까지의 다리를 새로 만들어봅니다.
			SelectBridge(h, 0, BridgeBoard);
		}
		
		if (MinVal == Integer.MAX_VALUE) { // 3개까지의 다리를 만들어봤지만 정답을 얻지 못했다면
			System.out.println(-1); // -1을 리턴합니다.
		} else { // 3개까지의 다리를 만들면서 최솟값이 갱신되었다면
			System.out.println(MinVal); // 갱신된 값을 출력합니다.
		}
	}

	public static void SelectBridge(int h, int depth, int[][] board) { // 사다리를 놓지 않은 곳에 h개의 사다리를 놓습니다.
		if (depth == h) {
			if (Go(board)) {
				MinVal = Math.min(MinVal, h);
			}
			return;
		}

		for (int i = 0; i < H; i++) {
			for (int j = 0; j < N - 1; j++) {
				if (board[i][j] == 0 && board[i][j + 1] == 0) {
					board[i][j] = j + 2;
					board[i][j + 1] = j + 1;
					SelectBridge(h, depth + 1, board);
					// 백트래킹
					board[i][j] = 0;
					board[i][j + 1] = 0;
				}
			}
		}

	}

	public static boolean Go(int[][] board) {
		for (int j = 0; j < N; j++) {
			int now = j; // j번째 사다리를 검사합니다.
			for (int i = 0; i < H; i++) {
				if (board[i][now] != 0) {
					now = board[i][now] - 1;
				}
			}
			// j번째 사다리가 재대로 도착하니 않았으면 false를 반환합니다.
			if (now != j) return false;
		}
		return true;
	}
}