구현, 백트래킹 (15684 사다리 조작)

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

15684번: 사다리 조작

 

 

풀이과정

check() :i번 세로선의 결과가 i번이 나오는지 확인하는 함수

 

사다리 0개 놓고 check()하기

사다리 1개를 놓는 모든 경우에 대해 check()하기

사다리 2개를 놓는 모든 경우에 대해 check()하기

사다리 3개를 놓는 모든 경우에 대해 check()하기

만약 사다리 1개를 놓는 과정에서 check()==true가 된다면 사다리 2개, 3개 놓는 과정은 필요하지 않다. 왜냐하면 문제에서 최소값을 요구하기 때문이다.

---

그러면 사다리 1개, 2개를 모든 경우에 대해서 어떻게 놓을까?

백트래킹을 사용

static boolean solve(int n, int row, int cnt){

        if(n==cnt){
            if(check()){
                ans = Math.min(ans,n);
                return true;
            }
            return false;
        }


        for(int i=row;i<H+1;i++){
            for(int j=1;j<N;j++){
                if(arr[i][j]==0 && arr[i][j+1]==0){
                    // 다리 놓기
                    arr[i][j]=1; // 1을 만나면 오른쪽으로 이동
                    arr[i][j+1]=2; // 2를 만나면 왼쪽으로 이동
                    if(solve(n+1,i,cnt)) return true;
                    arr[i][j]=0;
                    arr[i][j+1]=0;
                }
            }
        }
        return false;
    }

 

cnt가 놓을 사다리 갯수이고, n이 현재 놓은 사다리 갯수이다.

그리고 사다리는 1과 2로 나타냈다.

1을 만나면 오른쪽으로 이동

2를 만나면 왼쪽으로 이동해야 한다.

또 백트래킹 함수의 return 값으로 boolean을 줬는데, check()가 true이면 사다리를 더 놓아보지 않아도 되기 때문이다.

이렇게 해서 실행시간을 단축시킬 수 있었다.

1744ms 경우에는 사다리를 갯수에 따라 순차적으로 놓는 것이 아닌 0개,1개,2개,3개,0개,1개,2개,3개, ... 이런식으로 가능한 모든 경우에 대해 갯수에 상관없이 사다리를 놓아서 실행시간이 오래걸렸다.

 

전체코드

package com.mincheolsong;
import java.io.*;
import java.util.*;


public class Main {


    static int N,M,H;
    static int[][] arr;
    static int ans;
    static final int INF = (int)1e9;

    static boolean go(int row, int col,int start){ // (1행, col열, 시작위치)

        if(arr[row][col]==9 && start==col){ // 끝 까지 내려갔는데 시작 위치 열에 도착한 경우
            return true;
        }

        if(arr[row][col]==0){ // 아래로 내려가기
            if(go(row+1,col,start)) return true;
        }else if(arr[row][col]==1){ // 오른쪽으로 가기
            if(go(row+1,col+1,start)) return true;
        }else if(arr[row][col]==2){ // 왼쪽으로 가기
            if(go(row+1,col-1,start)) return true;
        }

        return false;

    }
    static boolean check(){

        for(int i=1;i<N+1;i++){
            if(!go(1,i,i)){ // (1행, i열, 시작위치) 에서 출발 시키기
                return false;
            }
        }

        return true;
    }
    static boolean solve(int n, int row, int cnt){

        if(n==cnt){
            if(check()){
                ans = Math.min(ans,n);
                return true;
            }
            return false;
        }


        for(int i=row;i<H+1;i++){
            for(int j=1;j<N;j++){
                if(arr[i][j]==0 && arr[i][j+1]==0){
                    // 다리 놓기
                    arr[i][j]=1; // 1을 만나면 오른쪽으로 이동
                    arr[i][j+1]=2; // 2를 만나면 왼쪽으로 이동
                    if(solve(n+1,i,cnt)) return true;
                    arr[i][j]=0;
                    arr[i][j+1]=0;
                }
            }
        }
        return 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());
        arr = new int[H+2][N+1];
        ans = INF;
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int a,b;
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            arr[a][b] = 1;
            arr[a][b+1] = 2;
        }
        Arrays.fill(arr[H+1],9);

        for(int i=0;i<=3;i++){
            if(solve(0,1,i)) break;
        }


        if(ans==INF) ans = -1;

        System.out.println(ans);



    }

}