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

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

15684번: 사다리 조작

 

풀이

    문제의 입력을 보면 세로선의 개수는 최대 10개, 높이는 최대 30개이다. 즉 놓치 못하는 규칙을 고려하지 않았을 때 가로선이 있을 수 있는 위치는 총 300개이다. 또 최대 3개의 가로선을 추가할 수 있는 조건을 보았을 때 브루트 포스 알고리즘으로 백트래킹을 사용해도 풀릴 수 있는 문제라고 생각하였다. 따라서 가로선이 놓일 수 있는 부분이 겹치지 않게 놓다보면 시간초과가 발생하지 않을 것이다.

    가로선은 세로선에서 오른쪽으로만 놓는다고 생각한다. 따라서 j번 세로선에 놓는다고 했을 때 j-1, j+1의 세로선에 모두 가로선이 존재하지 않아야한다. 만약 j번에 놓을 수 있을 때 dfs를 이용하여 재귀적으로 j번 세로줄부터 놓을 수 있는 위치를 다시 계산한다. 최대한 중복을 줄이기 위해 j번 세로줄부터 확인하는 것이다.

 

소스 코드

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <deque>

using namespace std;

const int MN = 9;
int N, M, H;
int ans = 4; //최대 3까지이므로 4로 설정

void dfs(int now, int n, bool ladder[31][11]) {
    if(n >= ans) return; //이미 최소값을 넘은 경우 탐색하지 않음

    bool chk = false; //모두 j번 세로줄이 j번에서 끝나는지 확인하는 변수
    for(int j = 1; j <= N; j++) {
        int now = j;
        for(int i = 1; i <= H; i++) {
            if(ladder[i][now-1]) { //왼쪽에 길이 있다면 왼쪽 세로줄로 이동
                now--;
            }
            else if(ladder[i][now]) { //오른쪽에 길이 있다면 오른쪽 세로줄로 이동
                now++;
            }
        }
        if(now != j) { //만약 j번에서 끝나지 않은 경우
            chk = true; //끝나지 않음을 체크 후 종료
            break;
        }
    }
    if(!chk)  { //만약 모두 알맞게 끝난 경우
        ans = min(ans, n); //최소값 갱신 후 더 이상 탐색하지 않음
        return;
    }

    if(n == 3) return; //3개 가로줄 사용한 경우 리턴
    for(int j = now; j < N; j++) { //지금까지 탐색한 세로줄부터
        for(int i = 1; i <= H; i++) { //모든 높이를 탐색
            if(!ladder[i][j] && !ladder[i][j+1] && !ladder[i][j-1]) { //가로줄을 놓을 수 있는 경우
                ladder[i][j] = true; //가로줄 생성
                dfs(j, n+1, ladder); //재귀
                ladder[i][j] = false; //가로줄 제거
            }
        }
    }
}

int main() {
    cin >> N >> M >> H;
    bool ladder[31][11];
    memset(ladder, 0, sizeof(ladder)); //사다리 초기화
    for(int i = 0; i < M; i++) {
        int a, b; cin >> a >> b;
        ladder[a][b] = true; //가로줄 추가
    }
    dfs(1, 0, ladder); //재귀로 탐색
    if(ans == 4) cout << -1; //방법이 없는 경우 -1출력
    else cout << ans;
}

위 과정대로 작성한 코드이다. 방법이 없는 경우를 고려해 초기값을 4로 설정했다. 최대 3까지 정답이 될 수 있기 때문이다.

 

채점 결과