[BOJ] 15684:사다리조작

0. 문제

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

15684번: 사다리 조작

 

1. 문제분석

- 주어진 사다리에서 추가로 가로줄을 그려서 사다리 타기의 시작점과 끝점이 모든 경우에 같도록 하는 경우를 찾는 문제이다. 최대 3개의 가로줄을 넣어보고, 그 때의 사다리 타기 결과가 조건을 만족하는 가로줄 개수의 최솟값을 구해야 하므로, 각각의 가로줄을 넣어보고 각 경우에 대해서 사다리 타기의 결과를 체크해 보아야 한다. 즉, 추가할 가로줄을 순차적으로 대입시켜보고, 다시 원래 상태로 복구한 뒤에 새로운 경우의 수를 대입시키는 방식으로 코드를 작성해야 하므로 n-queen 문제를 푸는 것과 마찬가지로  백트래킹(backtracking)을 사용해 문제를 풀어야 한다. 

 

2. 주의할 점

- 시간 초과에 유의하며 풀어야 한다. 추가할 수 있는 최대의 가로줄 개수가 3개라는 비교적 작은 크기의 limit 값이 있지만, 사다리 줄을 추가해줄 때마다 매번 조건을 만족하는지 체크해주어야 하기 때문이다.

- 어느 방식으로 사다리 개수 체크를 해줄 지를 결정하느냐에 따라 테스트케이스 시간도 달라진다.

1 . 가로줄을 하나씩 추가해 가면서, 추가할 때마다 조건 만족하는지 체크 

2. 추가할 가로줄의 개수를 정해놓고 해당 개수를 만족하는 경우에 도달하면 조건 만족하는지 체크

최종적으로 제출한 코드에서는 2번 방법을 택했다. 2번으로 코드를 짜는 편이, 최솟값에 도달한 경우 바로 코드를 종료시킬 수 있다.

 

 

3. 소스코드(Java)

// boj 15684 사다리조작
// backtracking

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

public class boj_15684 {
    static int n, m, h;
    static int ans = 4;
    static boolean found = false;
    static boolean[][] isConnected;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = stoi(st.nextToken());
        m = stoi(st.nextToken());
        h = stoi(st.nextToken());
        isConnected = new boolean[n+1][h+1];
        for (int i = 0; i < m; ++i) {
            st = new StringTokenizer(br.readLine());
            int a = stoi(st.nextToken());
            int b = stoi(st.nextToken());
            isConnected[b][a] = true;
        }
        for (int i = 0; i <= 3; ++i) {
            go(0, 1, 1, i);
            if (found) break;
        }
        if (ans > 3) System.out.print(-1);
        else System.out.print(ans);
    }
    public static int stoi(String s) {return Integer.parseInt(s);}
    public static void go (int cnt, int si, int sj, int size){
        if (cnt > 3) return;
        if (cnt == size) {
            if (check() && cnt < ans) {
                found = true;
                ans = cnt;
            }
            return;
        }
        for (int i = si; i < n; ++i) {
            if (i != si) sj = 1;
            for (int j = sj; j <= h; ++j) {
                if (isConnected[i][j] || isConnected[i - 1][j] || isConnected[i + 1][j])
                    continue;
                isConnected[i][j] = true;
                go(cnt + 1, i, j, size);
                isConnected[i][j] = false;
            }
        }
    }
    public static boolean check() {
        for (int start = 1; start <= n; ++start) {
            int now = start;
            for (int i = 1; i <= h; ++i) {
                if (isConnected[now][i]) now = now + 1;
                else if (isConnected[now - 1][i]) now = now - 1;
            }
            if (now != start) return false;
        }
        return true;
    }
}

 

4. 여담

- 삼성 SW테스트 기출문제에서 연속으로 백트래킹 문제가 나왔다. 삼성은 백트래킹을 좋아하는걸까

- 최대한 시간을 줄일 수 있는 방향으로 코드를 짜는 연습을 해야겠다. 너무 문제를 "풀 수만 있게" 코드를 짜다보니 이런 시간초과 되기 쉬운 문제를 만났을 때 무너지는 것 같다.