[BOJ - JAVA] (삼성전자 기출) 사다리 조작 (백트래킹, 조합, 완전탐색)

# 주소

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

15684번: 사다리 조작

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
class Main{
    static int n, m, k;
    static boolean[][] visit;
    static int answer;
    public static void main(String[] args) {
        answer = 0;
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        k = scan.nextInt();
        visit = new boolean[k + 1][n + 1];
        for(int i = 0; i < m; i++){
            int a = scan.nextInt();
            int b = scan.nextInt();
            visit[a][b] = true;
        }
        //입력 끝. visit배열로 a와 b사이에 사다리가 설치되었음
        boolean isOk = true;
        for(int i = 1; i <= n; i++){
            if(!check(i)){
                isOk = false;
                break;
            }
        }
        //최초의 사다리 배열도 정답이 될 수 있으므로 확인해보기
        if(isOk){
            System.out.println(0);
            System.exit(0);
        }
        //그럴 경우 0 출력
        for(int i = 1; i <= 3; i++){
            dfs(1, 0, i);
        }
        //1부터 3까지의 추가 개수를 주고 dfs탐색 시작
        System.out.println(-1);
    }
    static void dfs(int x, int start, int end){
        if(start > end)
            return;
        //start가 end보다 많으면 종료
        if(start == end){
            boolean isOk = true;
            for(int i = 1; i <= n; i++){
                if(!check(i)){
                    isOk = false;
                    break;
                }
            }
            //start가 end개수일 때 check함수를 이용하여 시작점과 끝점 같은지 비교
            if(isOk) {
                answer = end;
                System.out.println(answer);
                System.exit(0);
            }
            //만약 isOk가 무사히 false로 안바뀌고 true로 남았다면 answer출력
            return;
        }
        for(int i = x; i <= k; i++){
            for(int j = 1; j <= n - 1; j++){
                if(!visit[i][j]) {
                    visit[i][j] = true;
                    dfs(i, start + 1, end);
                    visit[i][j] = false;
                }
            }
        }
        //조합을 이용하여 visit을 2중 for문으로 백트래킹.
        //j는 n - 1까지 탐색하여야 n-1과 n까지의 연결을 확인할 수 있음
        //i가 x부터 시작하는 이유는 157사다리나 571사다리나 같은 경우이므로 앞선 경우의 수를 재탐색 방지
    }
    static boolean check(int start){
        int temp = start;
        for(int j = 1; j <= k; j++){
            if(temp - 1 != 0 && visit[j][temp - 1])
                temp--;
            else if(temp != n && visit[j][temp])
                temp++;
        }
        if(temp != start)
            return false;
        return true;
        //시작지점과 끝지점이 같으면 true 틀리면 false리턴
    }
}

시간 초과 나서 결국 코드 수정이 불가피 했던 문제... 삼성 기출이라는 명성 답게 겉보기에는 쉽지만 백트래킹에 대한 연습이 부족했던 터라 완벽하게 풀지는 못하였습니다.

문제를 간단히 요약해봅시다.

# 문제 요약

1. 3가지 이상의 사다리 추가 설치가 필요하면 바로 break하고 -1을 출력하여 불필요한 탐색 줄이기

2. 조합을 이용하여 풀어야 하며 순열로 풀 경우 시간 낭비가 심해짐

3. 노드와 노드 사이의 값을 저장하기 위해 boolean타입의 2차원 배열만으로 표현이 가능함

이렇게 요약할 수 있는데요.

딱히 어려운 자료구조를 사용하는 것도, 그렇다고 어려운 알고리즘 기법이 들어가는 것은 아니지만 이상하게도 시간과의 싸움이 저의 발목을 잡았던 것 같습니다.

코드를 보며 해결해봅시다.

answer = 0;
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
k = scan.nextInt();
visit = new boolean[k + 1][n + 1];
for(int i = 0; i < m; i++){
    int a = scan.nextInt();
    int b = scan.nextInt();
    visit[a][b] = true;
}

전 대기업 문제들이 참 좋은게, 입력 값이 쓸데없이 많지 않아서 Scanner를 이용하여 적은 코드로 풀 수 있어 좋습니다.

성능의 차이가 크게 나서 문제의 정답 유무를 가리지 않는한 웬만하면 Scanenr를 쓰지만 100에 2~3정도의 확률로 Buffer를 쓰셔야 정답 되는 경우가 종종 있으니 주의하셔야합니다.

n과 m, k를 입력 받습니다.

이 때 입력 조건을 잘 보셔야 하는데,,, 전 사실 이거 때문에 못 풀었습니다. 

머냐면 visit의 크기가 n by m이 아니라 k by n이기 때문이에요.

저렇게 해도 예제는 다 맞던데 이상하게 제출하면 틀림 + 시간 초과가 더블로 뜨더라고요. 

알고봤더니 저런 모종의 이유가 있었습니다 하핫.

보통이면 그냥 n by m으로 풀게 해주는데 이 문제는 조금 특이하네요 ㅠㅠ....

어쨌든 for문을 이용하여, visit[a][b] = true로 모든 입력값의 사다리의 값을 나타냅니다.

boolean isOk = true;
for(int i = 1; i <= n; i++){
    if(!check(i)){
        isOk = false;
        break;
    }
}
//최초의 사다리 배열도 정답이 될 수 있으므로 확인해보기
if(isOk){
    System.out.println(0);
    System.exit(0);
}

이후 최초의 사다리 배열에 대해서도 정답이 될 수 있으니 check함수로 확인하여 0을 출력합니다.

check함수는 처음 들어가는 인풋값과 끝지점이 같은지 물어보는 함수입니다. 나중에 확인합시다.

for(int i = 1; i <= 3; i++){
    dfs(1, 0, i);
}
//1부터 3까지의 추가 개수를 주고 dfs탐색 시작
System.out.println(-1);

중요한건 check가 아니라 dfs함수이지요.

백트래킹의 기본 중에 기본인 순열, 조합. 어떤 차이가 있는지 코드로 봅시다.

i가 3넘어가면 -1이 출력되게 하는 것은 덤입니다.

 

for(int i = x; i <= k; i++){
    for(int j = 1; j <= n - 1; j++){
        if(!visit[i][j]) {
            visit[i][j] = true;
            dfs(i, start + 1, end);
            visit[i][j] = false;
        }
    }
}

최초의 dfs가 실행된다면 이 구문이 가장 먼저 실행됩니다.

이중 for문을 이용하여 사다리를 선택할 것입니다.

예를 들어 봅시다.

6 x 6의 크기의 공간이 있습니다.

이 때 저희는 사다리를 2개를 선택하려면 어떻게 하나요?

가로의 길이는 5개, 세로의 길이는 6개 이므로 30 x 29 x 1/2지요?

즉 30C2라는 조합의 결과가 연산이 됩니다.

여기에서 저희는 1, 29라는 번호의 사다리를 선택하거나 29, 1의 사다리를 선택하거나 모두 같은 경우로 칩니다.

어쨌든 사다리를 내려오는 당사자 입장이 되었을 때 두 개의 경우의 사다리 조합은 어딜봐도 같기 때문이지요.

따라서 저희는 순열 대신 조합을 이용하여 이 문제를 풀어갈 것인데요.

순열의 경우 1, 29와 29, 1의 경우가 서로 다를 때 쓸 수 있답니다.

코드로 보게 되면 

for(int i = 0; i <= k; i++){
    for(int j = 1; j <= n - 1; j++){
        if(!visit[i][j]) {
            visit[i][j] = true;
            dfs(start + 1, end);
            visit[i][j] = false;
        }
    }
}

이렇게 짜여진 코드가 순열이라고 할 수 있습니다.

1 5 9, 5 1 9, 1 9 5, 5 9 1 등 숫자 세 개만 가지고 만들어지는 조합이 엄~청나게 많아지거든요. 따라서 이 문제는 조합으로 푸셔야 하는데, 순열에서 조합으로 나타내는법은 굉장히 쉽습니다.

그냥 dfs함수에 파라미터를 한 개 추가해주어 시작하는 for문의 위치에서 전에 탐색했던 그 위치에서 재탐색을 하면 간단하거든요.

시간이 왜 이렇게 차이가 나냐면, 단순히 경우의 수에 국한된다면 또 모를까, 이 뒤에 있을 check함수 까지 생각하면 시간 복잡도는 자그마치 O(N^2)였던 것이 O(6 x N^2)까지 늘어날 수 있게 됩니다.

물론 N값이 크지 않다고는 하지만 이러한 작은 개수 차이가 나중엔 실로 엄청난 복잡도를 가지게 되니 재귀를 이용하는 문제에서 특히 시간 복잡도를 유념하셔야 겠습니다.

어쨌든 다음으로 넘어갑시다.

if(start == end){
    boolean isOk = true;
    for(int i = 1; i <= n; i++){
        if(!check(i)){
            isOk = false;
            break;
        }
    }
    //start가 end개수일 때 check함수를 이용하여 시작점과 끝점 같은지 비교
    if(isOk) {
        answer = end;
        System.out.println(answer);
        System.exit(0);
    }
    //만약 isOk가 무사히 false로 안바뀌고 true로 남았다면 answer출력
    return;
}

저희는 이렇게 구한 경우의 수를 가지고 check함수에 제출하여 

"우리 이렇게 사다리 짰는데 이렇게 1번부터 n번까지 사람들이 내려가면 다 각자 위치대로 내려오는지 확인해줄래?"같은 함수를 실행합니다.

그 check함수는 생각보다 너무나 간단하게 생겼습니다.

static boolean check(int start){
    int temp = start;
    for(int j = 1; j <= k; j++){
        if(temp - 1 != 0 && visit[j][temp - 1])
            temp--;
        else if(temp != n && visit[j][temp])
            temp++;
    }
    if(temp != start)
        return false;
    return true;
    //시작지점과 끝지점이 같으면 true 틀리면 false리턴
}

시작지점인 start를 파라미터로 가져와, temp에 담은 뒤 하나의 for문으로 탐색을 할 수 있습니다.

이 때 temp가 1이 아니고 왼쪽에 visit이 true라면 temp값을 깎아주고, 반대로 n이 아닐 때 오른쪽에 true라면 temp 증가시킵니다.

직접 temp가 내려가는 방식이 아니라 temp를 위에서 내려다본 방식으로 접근하여 visit의 유무에 따라 짤 수 있었습니다.

최종적으로 temp가 start에 도달하면 true를, 아니면 false를 리턴하여 answer를 정상적으로 출력하심 됩니다.

 

 

이 문제가 최근에 풀었던 문제 중 제일 전 어려웠습니다.

구현이나 BFS, DFS, 시뮬레이션보다 이 문제는 시간 초과와의 싸움이 저에게 너무나도 힘들었습니다...

내일 쯤엔 다시 구현 문제로 달려야겠네용.

내일 뵙겠습니다~