15684번-사다리조작

문제

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

15684번: 사다리 조작

---

접근방법

1) 접근 사고

https://jaimemin.tistory.com/1078

백준 15684번 사다리 조작

를 참고하여 문제를 풀었습니다.. 아직 구현력이 많이 부족한거 같습니다.

모든 세로 열에 사다리를 놓는 방법을 사용해야하기 때문에 Backtracking으로 문제를 접근하셔야 합니다.

그런뒤에 배열에 사다리를 놓은 경우와 놓지 않을 경우를 체크한뒤 시작점이 종료지점과 같은지를 확인해야 합니다.

코드에 주석을 자세하게 적어두었습니다.

 

2) 시간 복잡도

O(N^2)

 

3) 배운 점

문제에서 주어지는 M값에 초점을 너무 두었던거 같습니다. 문제를 좀 자세히 읽는 습관이 필요해 보이네요..

 

4) PS

---

정답 코드

#include<bits/stdc++.h>
 
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X, Y) make_pair(X,Y)
#define mt(X, Y) make_tuple(X,Y)
#define mtt(X, Y, Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int MAXN = 11;
const int MAXH = 31;
int board[MAXH][MAXN];
int n, m, h;
int boardCnt;
bool flag;
 
int main(void) {
    fastio;
    cin >> n >> m >> h;
 
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        board[a - 1][b] = true;
    }
 
    auto DFS = [&](int y, int cnt, auto&& DFS) -> void{
        if (flag)
            return;
 
        if (boardCnt == cnt) {
            bool possibleFlag = true;
            //맨 좌측 col부터 시작해서 맨 우측 col까지 사다리를 타면서 내려간다.
            for (int i = 0; i < n; i++) {
                int row = i;
                for (int j = 0; j < h; j++)
                    //오른쪽으로 사다리를 놓은 경우라면
                    if (board[j][row])
                        row++;//출구 위치 증가
                        //좌측으로 사다리가 놓여져 있는 경우라면
                    else if (1 < row && board[j][row - 1])
                        row--;//출구 위치 감소
 
                //출구 위치와 사다리를 타기 시작한 i위치가 다르다면 멈춤
                if (i != row) {
                    possibleFlag = false;
                    break;
                }
            }
            //출구 위치와 사다리를 타기 시작한 위치가 true라면 참
            if (possibleFlag)
                flag = true;
            return;
        }
        for(int i = y; i < h; i++){
            for(int j = 1; j <n; j++){
                //2개의 가로선이 연속하거나 서로 접하면 안된다.
                if(!board[i][j -1] && !board[i][j] && !board[i][j + 1]){
                    board[i][j] = true;
                    DFS(i, cnt + 1, DFS);
                    board[i][j] = false;
                }
            }
        }
        return;
    };
 
    for (int i = 0; i <= 3; i++) {
        boardCnt = i;
        DFS(0, 0, DFS);
        if (flag) {
            cout << boardCnt << "\n";
            return 0;
        }
    }
    cout << -1 << "\n";
}