백준 15684번: 사다리 조작

문제 설명

• https://www.acmicpc.net/problem/15684
• N개의 세로선이 존재하며 H개의 다리를 그을 수 있는 점선이 존재합니다.
• 현재까지 M개의 회색실선 가로선을 그은 상태입니다.
• 이 상태에서 0~3개의 다리를 더 그어서 모두가 자기자신의 원래위치를 뽑을 수 있는지를 구하는 문제입니다.

접근법

• 사다리를 어떻게 표현하는지가 중요합니다.
  • 저는 1번 세로줄과 2번 세로줄이 첫번째 가로줄에 연결되어 있다는 걸 다음과 같이 표현했습니다.
    • board[가로줄 번호-1][from 세로줄 번호 -1] = to세로줄 번호
  • 사다리는 양방향이기 때문에 반대의 경우도 표현해줘야 합니다.
    • board[1번 가로줄 인덱스][1번 세로줄 인덱스] = 2(번 세로줄)
    • board[1번 가로줄 인덱스][2번 세로줄 인덱스] = 1(번 세로줄)
  • 우변의 값을 인덱스로 쓰면 0의 의미가 모호해 집니다.
    • 1번 세로줄의 인덱스 값은 0이 됩니다. 2번 세로줄에서 1번세로줄로의 이동을 인덱스로 표현하면 board[가로줄][1] = 0 이 됩니다.
    • 이 0이 옆으로 가는 줄이 없다는 의미의 0인지, 1번에서 0번으로 가는 0인지 알 수 없기 때문에 우변은 인덱스로 쓰지 않았습니다.

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;
	}
}