백준 15684 사다리 조작 C++

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

15684번: 사다리 조작

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ15684.cpp

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

//
//  main.cpp
//  BJ15684
//
//  Created by 최화연 on 2022/04/23.
//

#include <iostream>
using namespace std;

int N, M, H;
int ladder[31][20] = {0, };

int answer = -1;

bool check_ladder() {
    bool check = true;
    for (int c=1; c<=N; c++) {
        int col = 2*(c-1)+1;
        int row = 1;
        while (row <= H) {
            //오른쪽 체크
            if (col < 2*(N-1)+1 && ladder[row][col+1]) {
                col += 2;
            }
            //왼쪽 체크
            else if (col > 1 && ladder[row][col-1]) {
                col -= 2;
            }
            row ++;
        }
        if (col == 2*(c-1)+1) continue;
        check = false;
        break;
    }
    return check;
}

void add_lines(int cnt, int col, int row, int num) {
    if (answer == num) return;
    if (cnt == num) {
        if (check_ladder()) {
            answer = num;
        }
        return;
    }
    
    for (int c=1; c<N; c++) {
        int nc = 2*(c-1)+1;
        int rr = row;
        if (c < col) rr = row+1;
        for (int r=rr; r<=H; r++) {
            if (ladder[r][nc+1]) continue;
            ladder[r][nc+1] = 1;
            if (c == N-1) add_lines(cnt+1, 1, r+1, num);
            else add_lines(cnt+1, c+1, r, num);
            ladder[r][nc+1] = 0;
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> M >> H;
    for (int i=0; i<M; i++) {
        int a, b;
        cin >> a >> b;
        ladder[a][2*(b-1)+2] = 1;
    }
    
    for (int c=1; c<=N; c++) {
        int col = 2*(c-1)+1;
        for (int r=1; r<=H; r++) {
            ladder[r][col] = 1;
        }
    }
    
    if (M == 0 || check_ladder()) cout << 0 << endl;
    else {
        for (int i=1; i<=3; i++) {
            if (answer != -1) break;
            add_lines(0, 1, 1, i);
        }
        
        cout << answer << endl;
    }
    
    return 0;
}

---

풀이 과정

풀이 시간 1시간 8분

#include <iostream>
using namespace std;

int N, M, H;
int ladder[31][20] = {0, };

int answer = -1;

bool check_ladder() {
    bool check = true;
    for (int c=1; c<=N; c++) {
        int col = 2*(c-1)+1;
        int row = 1;
        while (row <= H) {
            //오른쪽 체크
            if (col < 2*(N-1)+1 && ladder[row][col+1]) {
                col += 2;
            }
            //왼쪽 체크
            else if (col > 1 && ladder[row][col-1]) {
                col -= 2;
            }
            row ++;
        }
        if (col == 2*(c-1)+1) continue;
        check = false;
        break;
    }
    return check;
}

void add_lines(int cnt, int col, int row, int num) {
    if (answer == num) return;
    if (cnt == num) {
        if (check_ladder()) {
            answer = num;
        }
        return;
    }
    
    for (int c=1; c<N; c++) {
        int nc = 2*(c-1)+1;
        int rr = row;
        if (c < col) rr = row+1;
        for (int r=rr; r<=H; r++) {
            if (ladder[r][nc+1]) continue;
            ladder[r][nc+1] = 1;
            if (c == N-1) add_lines(cnt+1, 1, r+1, num);
            else add_lines(cnt+1, c+1, r, num);
            ladder[r][nc+1] = 0;
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> M >> H;
    for (int i=0; i<M; i++) {
        int a, b;
        cin >> a >> b;
        ladder[a][2*(b-1)+2] = 1;
    }
    
    for (int c=1; c<=N; c++) {
        int col = 2*(c-1)+1;
        for (int r=1; r<=H; r++) {
            ladder[r][col] = 1;
        }
    }
    
    if (M == 0 || check_ladder()) cout << 0 << endl;
    else {
        for (int i=1; i<=3; i++) {
            if (answer != -1) break;
            add_lines(0, 1, 1, i);
        }
        
        cout << answer << endl;
    }
    
    return 0;
}

---

이전 풀이

//
//  main.cpp
//  BJ15684
//
//  Created by Hwayeon on 2021/08/11.
//

#include <iostream>
using namespace std;

int N, M, H;

//사다리의 정보를 담는 배열
//사다리의 왼쪽과 오른쪽을 탐색해야 하므로 N+1, H+1 크기로 할당
//ladder[r][c] = c번째 세로줄에 r번째 가로줄의 상태
//1. ladder[r][c] = 1 -> c와 c+1을 이어주는 가로줄, c기준으로 오른쪽에 사다리가 설치되어 있는 상태
//2. ladder[r][c] = 0 && ladder[r][c-1] = 1 -> c와 c-1을 이어주는 가로줄, c기준으로 왼쪽에 사다리가 설치되어 있는 상태
//3.ladder[r][c] = 0 && ladder[r][c-1] = 0 -> c번째 세로줄에 r번째 가로줄이 없는 상태
int ladder[32][12] = {0, };
int min_line = -1;

//T(n) = N*H
bool check_ladder(){
    for(int c=1; c<=N; c++){
        int now_c = c;
        for(int r=1; r<=H; r++){
            //왼쪽으로 가야하는 경우
            if(ladder[r][now_c] == 0 && ladder[r][now_c-1] == 1){
                now_c--;
            }
            //오른쪽으로 가야하는 경우
            else if(ladder[r][now_c] == 1){
                now_c++;
            }
        }
        //i번 세로선의 i번 결과가 아닌 경우 실패
        if(c != now_c) return false;
    }
    return true;
}

//T(n) = V+E = N*H + (N+1)*H
void install_line(int cnt, int n, int row, int col){
	//n개의 가로줄을 모두 설치한 경우
    if(cnt == n){
        //사다리 조작이 성공적인 경우
        if(check_ladder()){
            min_line = n;
        }
        return;
    }
    //가로줄 설치
    for(int r=row; r<=H; r++){
    	//r이 이전에 설치한 가로줄 번호인 row와 같다면, 세로줄을 col부터 탐색한다
    	//r이 row보다 큰 경우, 세로줄을 1부터 탐색한다
    	if(r > row+1) col = 1;
        for(int c=1; c<=N; c++){
        	//가로줄은 연속되거나 겹치면 안되기 때문에, 현재 위치와 양 옆에 가로줄이 있는지 확인
            if(ladder[r][c]==0 && ladder[r][c-1] == 0 && ladder[r][c+1] == 0){
                ladder[r][c] = 1;
                //현재 설치한 세로줄의 다음번 세로줄에는 사다리를 설치할 수 없으므로 col을 c+2로 한다
                install_line(cnt+1, n, r, c+2);
                ladder[r][c] = 0;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> M >> H;
    for(int i=0; i<M; i++){
        int col, row;
        cin >> row >> col;
        //col과 col+1이 연결되어 있는 가로줄
        ladder[row][col] = 1;
    }
    for(int i=0; i<=3; i++){
    	//더 적은 가로줄을 설치하여 조작 가능하므로 break
        if(min_line != -1) break;
        install_line(0, i, 1, 1);
    }
    cout << min_line << endl;
    
    return 0;
}
#시간복잡도 = T((N*H+(N+1)*H)*N*H) -> O(n^4), 공간복잡도 = O(n^2)