[BOJ 15684] 사다리 조작 - JAVA, Gold3

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

15684번: 사다리 조작

 

📌구현할 기능 목록

1. 기존 세로선, 가로선 수와 앞으로 세로선에 추가할 수 있는 가로선의 개수를 입력받는다.

 

2. 기존의 가로선들을 입력받는다.

 

3. 백트래킹을 사용해 사다리를 놓을 수 있는 가로선들 중 0~3개의 사다리를 추가하여

    조건(i번째 사다리에서 사다리 타기로 내려갈 때, 결과가 i)에 성립하는 최소 추가 사다리 개수를 구하는 함수 작성

 

4. 조건 만족을 위한 최소 추가 사다리 개수 결과를 출력한다.

 

🛠주요 로직

이차원 배열을 사용해 특정 위치에 가로선이 있음을 나타낸다.

 

예로 boolean ladder[][] = new boolean[31][11]; 라는 이차원 배열을 사용해 이를 표현하면

 

ladder[a][b] 는 b, b+1 번째 두 세로선의 a번째 가로줄에 가로선이 그어져 있다는 것을 의미한다.

위와 같은 사다리 그래프의 경우

 

ladder[1][1], ladder[5][1], ladder[3][2], ladder[2][3], ladder[5][4]가 모두 true 상태이며

 

이를 통해 가로선의 위치를 표현할 수 있다.

 

💻코드 적용

1. 기존 세로선, 가로선 수와 앞으로 세로선에 추가할 수 있는 가로선의 개수를 입력받는다.

2. 기존의 가로선들을 입력받는다.

StringTokenizer st = new StringTokenizer(br.readLine());

N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());

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[a-1][b]=true;
}

 

3. 백트래킹을 사용해 사다리를 놓을 수 있는 가로선들 중 0~3개의 사다리를 추가하여

    조건(i번째 사다리에서 사다리 타기로 내려갈 때, 결과가 i)에 성립하는 최소 추가 사다리 개수를 구하는 함수 작성

static boolean ladder[][] = new boolean[31][11];
static int ladder_cnt=0;
static boolean isSucess=false;

static void dfs(int index,int cnt){
    if(ladder_cnt==cnt){
        boolean isColSuccess = true; // 각 세로선의 검사 결과를 도출해내는 변수
        for(int i=1;i<=N;++i){
            int currentLadder=i;
            isColSuccess = true;
            
            // 하나의 세로선이 모든 가로선을 통과하고 난 후의 위치를 도출함
            for(int j=0;j<H;++j){
                if(currentLadder>1 && ladder[j][currentLadder-1]){
                    currentLadder--;
                }
                else if(ladder[j][currentLadder]){
                    currentLadder++;
                }
            }

            // 모든 가로선을 통과하고 난 후, 처음 세로선의 위치와 동일하지 않으면 조건실패로 반복문 탈출
            if(currentLadder!=i){
                isColSuccess=false;
                break;
            }
        }
        
        // 모든 세로선이 조건에 부합하는 경우
        if(isColSuccess){
            isSucess=true;
        }
        return;
    }

    // 놓을 수 있는 모든 가로선들 중 ladder_cnt 개수만큼을 선택하도록 함
    for(int i=index;i<H;++i){
        for(int j=1;j<N;++j){
            // 새로 놓을 가로선의 좌우와 해당 위치에 가로선이 없어야만 추가할 수 있도록 함
            if(!ladder[i][j-1] && !ladder[i][j] && !ladder[i][j+1]){
                ladder[i][j]=true;
                dfs(i,cnt+1);
                ladder[i][j]=false;
            }
        }
    }
}

 

4. 조건 만족을 위한 최소 추가 사다리 개수 결과를 출력한다.

// i는 추가할 사다라의 개수를 의미한다.(최대 3개까지 추가가 가능하므로)
for(int i=0;i<=3;++i){
    ladder_cnt=i;
    dfs(0,0);
    
    // 조건에 부합하는 결과가 나오는 경우, 최소의 추가 사다리를 의미하는 ladder_cnt를 출력하고 프로그램을 종료
    if(isSucess){
        bw.write(ladder_cnt+"\n");
        bw.flush();
        bw.close();
        return;
    }
}
// 조건에 부합하는 결과가 나오지 않는 경우
bw.write("-1\n");
bw.flush();
bw.close();

 

⌨제출 코드

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

public class Main {
    static int N,M,H;
    static boolean ladder[][] = new boolean[31][11];
    static int ladder_cnt=0;
    static boolean isSucess=false;

    static void dfs(int index,int cnt){
        if(ladder_cnt==cnt){
            boolean isColSuccess = true;
            for(int i=1;i<=N;++i){
                int currentLadder=i;
                isColSuccess = true;
                for(int j=0;j<H;++j){
                    if(currentLadder>1 && ladder[j][currentLadder-1]){
                        currentLadder--;
                    }
                    else if(ladder[j][currentLadder]){
                        currentLadder++;
                    }
                }

                if(currentLadder!=i){
                    isColSuccess=false;
                    break;
                }
            }
            if(isColSuccess){
                isSucess=true;
            }
            return;
        }

        for(int i=index;i<H;++i){
            for(int j=1;j<N;++j){
                if(!ladder[i][j-1] && !ladder[i][j] && !ladder[i][j+1]){
                    ladder[i][j]=true;
                    dfs(i,cnt+1);
                    ladder[i][j]=false;
                }
            }
        }
    }

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());

        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[a-1][b]=true;
        }

        for(int i=0;i<=3;++i){
            ladder_cnt=i;
            dfs(0,0);
            if(isSucess){
                bw.write(ladder_cnt+"\n");
                bw.flush();
                bw.close();
                return;
            }
        }
        bw.write("-1\n");
        bw.flush();
        bw.close();
    }
}