[브루트포스] 사다리 조작

백준 15684 사다리 조작 (삼성 SW역량테스트 기출)

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

package 사다리조작;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N; //사다리 수
    static int M; //놓여져 있는 가로선 수
    static int H; //한줄당 놓을 수 있는 가로선 수

    static List<Row> rows = new ArrayList<>();

    static int[][] ladder;

    static int minLadder=10;

    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 int[H+1][N];

        for(int i=1; i<=M; i++){
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            ladder[n][m] = 1;
        }


        //놓을 수 있는 곳들의 좌표를 구한다
        for(int i=1; i<=H; i++){
            for(int j=1; j<N; j++){
                if(ladder[i][j]==0){
                    rows.add(new Row(i,j));
                }
            }
        }


        //원본 확인
        if(checkLadder(ladder)){
            System.out.println(0);
            return;
        }

        //1~3개 확인
        int size = rows.size();
        if (size>3) size = 3;

        for(int i=1; i<=size; i++){
            rec(0, i, 0, ladder);
            if(minLadder < i) break; //이미 종결나서 해봐야 소용없음
        }

        if(minLadder!=10) System.out.println(minLadder);
        else System.out.println(-1);


    }


    static void rec(int n, int limit, int target, int[][] ladder){
        
        if(n==limit){
            if(checkLadder(ladder)==true) minLadder = limit;
            return;
        }

        for(int i=target; i<rows.size(); i++){
            ladder[rows.get(i).n][rows.get(i).m]=1;
            rec(n+1, limit, i+1, ladder);
            ladder[rows.get(i).n][rows.get(i).m]=0;
        }
    }


    //입력받은 사다리의 적합성을 검사
    static boolean checkLadder(int[][] laddder){

        for(int i=1; i<=N; i++){
            if(go(i, laddder)!=i){
                return false;
            }
        }
        return true;

    }


    //사다리 출발(1~N)
    static int go(int start, int[][] ladder){

        int pos = start;

        for(int i=1; i<=H; i++){

            if(pos==1){

                if(ladder[i][1]==1) pos++;
            }
            else if(1<pos&&pos<N){

                if(ladder[i][pos-1]==1) pos--;
                else if(ladder[i][pos]==1) pos++;
            }
            else if(pos==N){

                if(ladder[i][N-1]==1) pos--;
            }
        }
        return pos;
    }

    //추가로 가로선을 놓을 수 있는 곳의 위치
    static class Row{
        int n;
        int m;

        Row(int n, int m){
            this.n = n;
            this.m = m;
        }
    }
}

틀렸던 부분1

static void rec(int n, int limit, int target, int[][] ladder){

    if(n==limit){
        if(checkLadder(ladder)==true) minLadder = limit;
        return;
    }

    for(int i=target; i<rows.size(); i++){
        ladder[rows.get(i).n][rows.get(i).m]=1;
        rec(n+1, limit, target+1, ladder);
        ladder[rows.get(i).n][rows.get(i).m]=0;
    }
}

target+1이 아니라 i+1을 해야함.

target+1을 하면 첨부터 싹 다 하는거. 헷갈리지 않도록 조심.

개선한 부분

[변경전]

static void rec(int n, int limit, int target, Stack<Row> s){

    if(n==limit){
        int[][] cLadder = copyLadder();
        for(Row r: s){
            cLadder[r.n][r.m] = 1;
        }

        if(checkLadder(cLadder)==true){
            minLadder = limit;
        }
        return;
    }


    for(int i=target; i<rows.size(); i++){
        s.push(rows.get(i));
        rec(n+1, limit, i+1, s);
        s.pop();
    }
}

//입력받은 사다리의 적합성을 검사
static boolean checkLadder(int[][] laddder){

    for(int i=1; i<=N; i++){
        if(go(i, laddder)!=i){
            return false;
        }
    }
    return true;
}

Queue에 추가해볼 곳들의 좌표(Row객체)조합을 담음 -> 복사된 맵에 할당 -> 맵을 검사

[변경후]

static void rec(int n, int limit, int target, int[][] ladder){

    if(n==limit){
        if(checkLadder(ladder)==true) minLadder = limit;
        return;
    }

    for(int i=target; i<rows.size(); i++){
        ladder[rows.get(i).n][rows.get(i).m]=1;
        rec(n+1, limit, i+1, ladder);
        ladder[rows.get(i).n][rows.get(i).m]=0;
    }
}

백트래킹을 이용해서 맵에 바로 할당.

ladder[rows.get(i).n][rows.get(i).m]=0;

할당 후 다음 턴에 지워주면서 재활용

3864ms -> 492ms

copyLadder매소드가 매번 실행되지 않으므로 속도가 빨라진다.