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

문제

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

15684번: 사다리 조작

 

풀이

처음에 사다리를 어떻게 세팅해야 될 지 몰라서 헤맸다.

초반에 감을 못잡으니까 시작을 할 수 없어서 구글링을 통해 역시나 얍문님 풀이를 참조했다.

 

나는 visited[x][y] 배열을 사다리 연결 상태를 표시하기 위해 사용했는데,

visited[x][y] = true는, x번째 라인에 세로선 y와 y+1 을 연결하는 선이 존재한다는 뜻이다.

 

크게는 selectLine 함수로 사다리 놓기 시도를 한 후,

사다리를 놓은 각 경우의 수마다 doLadder 함수를 통해 문제 조건을 만족하는 지 검사한다.

 

selectLine 함수

selectLine 함수는 재귀함수로써 인자로 idx, cnt가 들어가는데,

idx는 현재 시점부터 처음 사다리를 놓는 시도를 할 x축 (가로선),

=> 여기서 왜 현재 시점이라고 표현했냐면, 이전에 이미 사다리를 놓았을 수도 있기 때문이다.

재귀함수라서 나에게는 시점에 대한 이해가 중요했는데, 이전에 한 사다리 놓기 작업에 이어서 '현재'부터 사다리 놓기 작업을 어느 라인부터 수행할 것이냐를 idx가 정해준다.

그리고 이 idx는 이전에 호출했던 재귀함수에서 for loop으로 증가하는 수이다.

(예: 만약 이전 idx 값이 1일 경우 => 다음 idx는 1~H까지이다. 왜냐하면 1번째 라인에 사다리를 놓은 후, 다음에 놓을 사다리는 1번째 라인이 될 수도 있고, 2번째 라인이 될 수도, ... H번째 라인이 될 수도 있기 때문이다.)

cnt는 현재까지 놓은 사다리의 총 개수이다.

종료조건은 cnt가 3보다 큰 지 확인하는 것이다. 문제에서 cnt 값은 3보다 크면 의미가 없다고 했으므로, cnt가 3보다 클 경우 return한다.

추가로 각 경우마다 doLadder를 통해 조건을 만족하는지를 검사한다.

 

doLadder 함수

doLadder 함수는 조건을 만족하는지 검사하는 함수로, 로직은 다음과 같다.

1. 각 세로축마다 다음을 반복한다.
   1. 현재의 세로축을 curNum에 담아주고,
   2. 각 가로축 (1부터 H까지의 라인) 을 확인하면서, 사다리가 연결되어 있으면 왼쪽/오른쪽 연결되어 있는 쪽으로 curNum을 이동한다.
   3. 가로축을 다 탐색한 결과 curNum과 해당 세로축의 값이 같지 않다면 즉시 false를 리턴시켜 종료한다.
2. 여기까지 왔을 때 한번도 false를 리턴하지 않았으면 모든 세로축 라인이 문제 없이 통과된 것이므로, true를 리턴한다.

 

코드

//
// Created by ღ 𝚂𝚑𝚒𝚗𝚎 𝚈𝚎𝚘𝚗 ღ on 2022/10/14.
//

#include <iostream>
#include <algorithm>
using namespace std;

int N, M, H; //세로선개수, 가로선개수, 각 세로선마다 놓을 수 있는 가로선의 개수
bool visited[400][20];
int answer = 98765432;

bool doLadder() {
    for(int i=1; i<=N; i++) {
        int curNum = i;
        for(int j=1; j<=H; j++) {
            if(visited[j][curNum]) curNum += 1;
            else if(visited[j][curNum-1]) curNum-=1;
        }
        if(curNum!=i) return false;
    }
    return true;
}

void selectLine(int idx, int cnt ) { //현재 고른 가로 (idx), 지금까지 놓은 사다리 (cnt)
    if(cnt > 3) return;
    if(doLadder() ) { //사다리 놓기 성공했을 경우
        answer = min(answer, cnt); //최소 cnt값 갱신해야 함
        return;
    }

    for(int i=idx; i<=H; i++) {
        for(int j=1; j<N; j++) {
            if(visited[i][j] == true) continue;
            if(visited[i][j-1] == true) continue;
            if(visited[i][j+1] == true) continue;

            visited[i][j] = true;
            selectLine(i, cnt+1);
            visited[i][j] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cin>>N>>M>>H;
    for(int i=0; i<M; i++) {
        int a, b;
        cin>>a>>b;
        visited[a][b] = true; //a번째 라인에 세로선 b, b+1을 연결하는 선이 존재한다.
    }
    selectLine(1, 0);
    if(answer>3) answer = -1;
    cout<<answer<<"\n";

}

 

결과