[백준] 15684. 사다리 조작

문제

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






풀이

역대급 삽질을 시전했다! 문제를 완전 잘못 이해한 것과 동시에 완전탐색을 대충 쓰면 처참한 결과를 받게 될 것이라는 교훈을 뼈 저리게 느끼게 되었다.

• '가로선의 수'라는 것이 행의 개수가 아니라 그을 수 있는 가로선의 개수를 말하는 것이었다... 따라서 M이 긋는 가로선의 개수, H가 행의 수를 의미하는 것이며, 즉 행은 30개 이하가 된다.
• 조합이 300C3이므로 간당 간당하게 시간 안에 돌 수 있다. 따라서 완전 탐색이 가능하다. 다만 이번에도 중복되는 경우를 제거해줘야 하는데, 가령 1번과 2번 세로선을 통과하는 위치 1 가로선을 긋고 3번과 4번세로선을 통과하는 위치 3 가로선을 긋는 순서를 뒤바꿔도 결과는 똑같이 나오므로 둘 다 탐색을 해줄 필요가 없다. 따라서 다음에 그릴 가로선은 이전에 그릴 가로선보다 상대적으로 다음의 위치에 나오게끔 만들어줘야 한다.
• 사다리를 확인하는 과정에서 시작 위치 != 끝 위치일 때 바로 return false로 나오게끔 짜지 않으면 시간초과가 난다고 한다. 진작에 위와 같이 만들어서 정말 시간초과가 나는지는 확인해보지 않았다.

//
//  15684.cpp
//  BJ
//
//  Created by 신기열 on 28/10/2019.
//  Copyright © 2019 신기열. All rights reserved.
//

#include <stdio.h>
#include <iostream>

using namespace std;

int N, M, H;
int map[31][11];
int answer = 4;

// 사다리의 시작점 = 끝점이 제대로 되는지 체크
bool PathFind(int m[][11]){
    // 세로선 번호 1 ~ 끝번호까지 전부 체크
    for(int i = 1; i <= N; i++){
        // 열의 위치는 세로선의 번호부터 시작하게 된다.
        int x = i; int y = 1;
        // 행의 끝에 다다를때까지 계속한다.
        while(y <= H){
            if(m[y][x] != 0){
                // 사다리 상에서 현재 위치에서 우측으로 가로선이 놓여있다면
                if(x + 1 <= N && m[y][x + 1] == m[y][x]){
                    // 우측으로 이동한다.
                    x++;
                }
                // 사다리 상에서 현재 위치에서 좌측으로 가로선이 놓여있다면
                else if(x - 1 >= 1 && m[y][x - 1] == m[y][x]){
                    // 좌측으로 이동한다.
                    x--;
                }
            }
            // 가로선이 놓여있든, 놓여있지 않든 과정이 끝나면 한칸 내려가줘야한다.
            y++;
        }
        // 현재 세로선에서 시작일 때 번호 != 끝일 때 번호라면 올바르게 조작된 사다리가 아니다.
        if(x != i) return false;
    }
    return true;
}

void DFS(int m[][11], int cnt, int x, int y){
    
//    cout << cnt << '\n';
//    for(int i = 1; i <= H; i++){
//        for(int j = 1; j <= N; j++){
//            cout << m[i][j];
//        }
//        cout << '\n';
//    }
//    cout << '\n';
//
    // cnt가 현재까지 구한 최소보다 작거나, 3을 넘어버리면 종료한다.
    if(cnt > answer || cnt > 3) return;
    // 올바르게 조작된 사다리라면 최솟값을 업데이트한다.
    if(PathFind(m)){
        answer = min(answer, cnt);
        return;
    }
    // 0보다 더 작을 순 없으므로 최솟값이 0이 나온다면 그냥 종료한다.
    if(answer == 0) return;

    // x와 y는 각각 이전 가로선의 시작점의 x, y좌표이다. 다음에 놓을 가로선은 같은 행에 있으며 x가 더 큰쪽에 있거나, 다음에 놓을 가로선이
    // 이전 가로선보다 더 밑에 있어야한다.(행 번호가 더 커야한다.)
    for(int i = y; i <= H; i++){
        // 다음 가로선의 x좌표는 이전 가로선의 x좌표보다 최소 1 커야한다.
        for(int j = x; j <= N; j++){
            // 이 때, 행이 바뀌고나면 x좌표는 다시 1부터 체크해줘야하므로 x = 0으로 만들어줌으로써 j가 다시 1부터 N까지 탐색할 수 있게 해준다.
            x = 0;
            // 가로선이 놓여있는 시작점에 아무것도 놓여있지 않으며 && 가로선의 끝점이 사다리를 벗어나지 않으며 && 가로선의 끝점에 아무것도 놓여
            // 있지 않다면
            if(m[i][j] == 0 && j + 1 <= N && m[i][j + 1] == 0){
                // 탐색 지점과 끝 지점에 가로선을 놓아준다. 이 때 cnt + 1로 값을 바꿔준 이유는 가령 전부 1로 업데이트를 해주게 되면
                // 00110000         00111100
                // 00000000  ---->  00000000
                // 00001100         00001100
                // 00000000         00000000
                // 같은 사다리가 된다면 마치 사다리가 연속되는 것처럼 보이게 된다. 따라서 cnt + 1로 값을 다르게 설정해준다면
                // 00110000         00112200
                // 00000000  ---->  00000000
                // 00001100         00001100
                // 00000000         00000000
                // 와 같이 사다리의 시작점과 끝지점을 제대로 구분할 수 있게 된다.
                m[i][j] = cnt + 1;  m[i][j + 1] = cnt + 1;
                DFS(m, cnt + 1, j, i);
                // DFS를 돌리고 나면 다시 가로선을 없애준다.
                m[i][j] = 0; m[i][j + 1] = 0;
            }
        }
    }
}


int main(){
    
    cin >> N >> M >> H;
    for(int i = 0; i < M; i++){
        int a, b;
        cin >> a >> b;
        map[a][b] = i + 5; map[a][b + 1] = i + 5;
    }
    
    DFS(map, 0, 1, 1);
    
    if(answer > 3) cout << -1;
    else cout << answer;
    
    return 0;
}