[백준 15684] 사다리 조작

문제 링크 : https://www.acmicpc.net/problem/15684

이 문제는 백트래킹을 이용하여 풀 수 있습니다. 이 문제는 문제 특성상 일반 백트래킹과 살짝 다른 방식으로 접근합니다. 주어진 문제에서 가로선의 개수가 모든 가로선의 개수가 아니라 a번과 a+1번을 연결하는 가로선의 개수만 보여주고 대신 세로선마다 가로선을 놓을 수 있는 개수가 주어지기 때문에 한 세로선을 기준으로 놓을 수 있는 위치에 모두 사다리를 놓아보고 해제하는 방식으로 백트래킹을 진행합니다. 이후 정답이 3보다 작거나 같으므로 0부터 3까지 가능한 정답을 반복문을 돌려 해당 수만큼 사다리를 추가했다면 모든 세로선이 자기 자신으로 도착하는지를 체크합니다. 이 때 체크 방식은 각 세로선 별로 가능한 모든 사다리를 탐색하면서 사다리가 왼쪽에 있다면 세로선을 -1만큼 이동하고 사다리가 오른쪽에 있다면 세로선을 1만큼 이동시켜 모든 사다리를 탐색 완료했을 때 현재 세로선이 초기의 i값과 같다면 통과하는 방식으로 체크합니다.

다음은 코드입니다.

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

class Main{
    static int N,M,H;
    static boolean[][] ladder;
    static boolean canMake = false;

    public static void main(String[] args) throws Exception{
        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());
        ladder = new boolean[N+2][H+1];

        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            ladder[b][a] = true;
        }

        for(int i=0;i<=3;i++){
            backtracking(i,0,1);
            if(canMake){
                System.out.println(i);
                return;
            }
        }
        System.out.println(-1);
    }

    static void backtracking(int targetLadderNum, int currLadderNum, int idx){
        if(currLadderNum > targetLadderNum) return;
        if(currLadderNum == targetLadderNum){
            for(int i=1;i<=N;i++){
                int row = i;
                for(int j=1;j<=H;j++){
                    if(ladder[row][j]) row++;
                    else if(ladder[row-1][j]) row--;
                    if(j==H && row!=i) return;
                }
            }
            canMake = true;
            return;
        }

        // 1부터 N까지의 세로줄에 사다리를 현재 놓을 수 있는 개수민큼 놓기
        for(int i=1;i<=N;i++){
            for(int j=idx;j<=H;j++){
                if(ladder[i][j] || ladder[i+1][j] || ladder[i-1][j]) continue;

                ladder[i][j] = true;
                backtracking(targetLadderNum,currLadderNum+1,j);
                ladder[i][j] = false;
            }
        }
    }
}