[백준/C++] 15684번 사다리 조작

문제 링크

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

15684번: 사다리 조작

 

접근 방법

추가해야하는 가로선이 3개 보다 많거나 불가능할 경우 모두 -1을 출력하라는 요구사항이 있기 때문에 3가지를 넘어가는 경우에 대해선 생각하지 않아도 되고, N과 H 또한 각각 최대 10, 30으로 크지 않아서 최악의 경우에 대해 

((N-1) * H) C  3 = 3,244,140 개의 조합만을 구하면 되기때문에 백트래킹을 이용하여 완전 탐색하는 방법을 생각했습니다.

개인적으로는 사다리 표현 방법과 사다리 타는 것을 구현하는 것에 많은 시간을 썼기 때문에 백트래킹보다 구현 문제에 좀 더 가깝다고 느꼈습니다.

코드

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int N, M, H, h, n, graph[31][11][11], answer = 4;
vector<pair<int, int>> candidate, list;

int dfs(int s, int h){
    if(h == H + 1) return s; // 마지막 높이에 도착했다면 해당 세로선 번호 반환
    if(graph[h][s][s + 1]) return dfs(s + 1, h + 1); // 내 다음 세로선과 연결된 경우 ex) 1 -> 2
    else if(graph[h][s][s - 1]) return dfs(s - 1, h + 1); // 내 이전 세로선과 연결된 경우 ex) 2 -> 1
    else return dfs(s, h + 1); // 현재 높이(h)에서 연결된 세로선이 없는 경우 동일한 세로선의 다음 높이로 이동
}

bool validate(){
    bool flag = true;

    // 뽑은 가로선 후보를 graph에 적용
    for(int i = 0; i < candidate.size(); i++){
        int h = candidate[i].first, n = candidate[i].second;
        graph[h][n][n + 1] = graph[h][n + 1][n] = 1;
    }

    // 1~N번 가로선까지 사다리타기를 진행
    for(int i = 1; i <= N; i++){
        if(i != dfs(i, 1)) { // 사다리타기 결과가 i와 다른 경우 즉시 break
            flag = false; 
            break;
        }
    }

    // graph에 적용된 가로선 원상복구
    for(int i = 0; i < candidate.size(); i++){
        int h = candidate[i].first, n = candidate[i].second;
        graph[h][n][n + 1] = graph[h][n + 1][n] = 0;
    }
    return flag;
}

void backtrack(int s){
    // 후보 가로선 개수와 상관없이 검증 진행, 최소값인 경우 최신화
    if(validate()) answer = min(answer, (int)candidate.size());
    if(candidate.size() == 3) return; // 3개를 초과하여 뽑을 필요없으므로 백트래킹 중지

    // 백트래킹 중복 제거를 위해 s 인덱스부터 시작
    for(int i = s; i < list.size(); i++){
        candidate.push_back(list[i]);
        backtrack(i + 1);
        candidate.pop_back();
    }
}

int main() {
    cin >> N >> M >> H;
    for (int i = 0; i < M; i++) {
        cin >> h >> n;
        graph[h][n][n + 1] = graph[h][n + 1][n] = 1;
    }

    // 구성된 graph를 후보가 될 수 있는 가로선 추가
    for(int i = 1; i <= H; i++){
        for(int j = 1; j < N; j++){
            if(!graph[i][j][j + 1]) list.push_back(make_pair(i, j));
        }
    }

    backtrack(0);
    if(answer == 4) answer = -1;
    cout << answer;
}

코드 설명

graph[i][j][k]는 i번째 높이에서 j번째 세로줄과 k번째 세로줄이 연결되어있다면 1, 아니라면 0으로 저장하는 방식으로.        3차원 배열을 통해 사다리를 표현하였습니다. 사다리타기는 현재 위치의 세로줄에서 연결된 다음 세로줄로 이동하는 방식으로 dfs와 유사하게 구현하였습니다.

형성된 graph를 이용하여 놓을 수 있는 가로줄의 위치를 구하여 모두 list에 저장하고 후보 가로줄이 3개가 될때까지 백트래킹을 이용하여 모든 경우의 수를 구합니다. 문제에서 최소로 가로줄을 놓아 정답을 만족하도록 요구하기 때문에 1, 2 가지의 가로줄을 골랐을 때에도 사다리타기(dfs)를 진행하여 답을 최신화하였습니다.

어려웠던 점

앞서 계산한 것과 같이 최악의 경우에 대해 경우의 수를 뽑는 데 걸리는 시간은 오래걸리지 않았지만 모든 경우에 대해 사다리타기를 진행해야하기 때문에 이 부분 때문에 시간초과가 걸렸습니다. 사다리타기를 진행하며 정답에 맞지 않는 경우가 나오는 즉시(i번 세로선의 사다리타기 결과가 i번이 나오지 않는 경우)  사다리타기를 종료하는 방식으로 최적화하여   시간초과를 피할 수 있었습니다.