15684. 사다리 조작

문제 개요

기존에 있는 사다리에 다리를 추가해서 본래 자리로 돌아올 수 있도록 하는 최소의 다리수를 구하는 문제입니다.

문제 접근

문제 조건을 잘못봐서 다리가 최대 3개까지라는 것을 모르고 2²⁷⁰개의 조합을 어떻게 브루트포스로 풀지라는 생각 때문에 삽질을 했습니다.
사다리에 다리를 추가하는 과정을 백트래킹으로 구현하면 해결되는 문제입니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;

class Pos{
    private int number;
    private int height;
    public Pos(int height, int number){
        this.number = number;
        this.height = height;
    }
    public int getNumber() {
        return number;
    }
    public void setNumber(int number) {
        this.number = number;
    }
    public int getHeight() {
        return height;
    }
    public void setHeight(int height) {
        this.height = height;
    }

    @Override
    public boolean equals(Object obj) {
        if(obj == this){
            return true;
        }
        if(obj == null || obj.getClass() != this.getClass()){
            return false;
        }
        Pos pos = (Pos)obj;
        return pos.number == this.number && pos.height == this.height;
    }

    @Override
    public int hashCode() {
        return Objects.hash(number, height);
    }
}

public class Main {
    static int N;
    static int M;
    static int H;
    static int[][] ladder;
    static List<Pos> pos;
    static int result;

    static void makeLine(int height, int number){

    }

    static void input()throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] settings = bf.readLine().split(" ");
        N = Integer.parseInt(settings[0]);
        M = Integer.parseInt(settings[1]);
        H = Integer.parseInt(settings[2]);
        ladder = new int[H][N];
        pos = new ArrayList<>();

        for(int i=0;i<H;i++){
            for(int j=0;j<N-1;j++){
                pos.add(new Pos(i, j));
            }
        }

        for(int i=0;i<M;i++){
            int[] nums = Arrays.stream(bf.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            ladder[nums[0]-1][nums[1]-1] = 1;
            ladder[nums[0]-1][nums[1]] = -1;
            pos.remove(new Pos(nums[0]-1, nums[1]-1));
            pos.remove(new Pos(nums[0]-1, nums[1]));
        }

        result = 9999;
    }

    static int getLandingNum(int curNum){
        for(int i=0;i<H;i++){
            curNum += ladder[i][curNum];
        }
        return curNum;
    }

    static boolean isOk(){
        for(int i=0;i<N;i++){
            if(getLandingNum(i) != i){
                return false;
            }
        }
        return true;
    }

    static void backtracking(int curNum, int lines){
        if(lines > 3){
            return;
        }
        if(isOk()){
            result = Math.min(result, lines);
            return;
        }
        for(int i=curNum; i < pos.size();i++){
            if(ladder[pos.get(i).getHeight()][pos.get(i).getNumber()+1] != 0){
                continue;
            }
            if(ladder[pos.get(i).getHeight()][pos.get(i).getNumber()] != 0){
                continue;
            }
            ladder[pos.get(i).getHeight()][pos.get(i).getNumber()] = 1;
            ladder[pos.get(i).getHeight()][pos.get(i).getNumber()+1] = -1;
            backtracking(i+1, lines+1);
            ladder[pos.get(i).getHeight()][pos.get(i).getNumber()] = 0;
            ladder[pos.get(i).getHeight()][pos.get(i).getNumber()+1] = 0;
        }
    }

    static void process(){
        backtracking(0, 0);
        if(result == 9999){
            System.out.println(-1);
            return;
        }
        System.out.println(result);
    }

    public static void main(String[] args) throws IOException {
        input();
        process();
    }
}

문제

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