3-O 사다리 조작

안녕하세요 종현님 ㅎㅎ

오랜만에 큰거 하나 들고오셨군요.. ㅎㅎ

저 정말 오래걸렸어요 ㅠㅠ

일단은.. 종현님의 코드가 뭐가 틀린지 위주로 해봤는데 잘 안나왔습니다.

그래서 이럴 때 제가 하는 방법이 있는데요.

처음부터 다시 짜는 방법입니다.

물론.

종현님의 코드스타일이 묻어나게 짜봤습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M, H; 
int ladder[31][11];  
int answer = 1e9;  
bool check() {
    for (int i = 1; i <= N; i++) {
        int pos = i;
        for (int j = 1; j <= H; j++) {
            if (ladder[j][pos]) {
                pos = ladder[j][pos];
            }
        }
        if (pos != i) return false;
    }
    return true;
}

void go(int cnt, int index) {
    if (cnt >= answer || cnt > 3) return;

    if (check()) {
        answer = min(answer, cnt);
        return;
    } 

    int y = (index - 1) / (N - 1) + 1;
    int x = (index - 1) % (N - 1) + 1; 
    if (y > H) return; 
    if (ladder[y][x] == 0 && ladder[y][x + 1] == 0) {
        ladder[y][x] = x + 1;
        ladder[y][x + 1] = x;
        go(cnt + 1, index + 1);
        ladder[y][x] = 0;
        ladder[y][x + 1] = 0;
    }

    go(cnt, index + 1);
}

int main() { 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> M >> H;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        ladder[a][b] = b + 1;
        ladder[a][b + 1] = b;
    }

    go(0, 1);
    
    if (answer > 3) cout << -1 << '\n';
    else cout << answer << '\n';
    
    return 0;
}

이렇게 하면 시간초과가 납니다.

이게 왜 그러냐면 이 정점에서 + 1 하면서 순차적으로 탐색하는 것..

로직상은 괜찮지만 사실 이게 엄청나게 별로긴 하거든요. 정점에서 2중for문으로 바로 다른 정점을 sparse하게 뛰는게 더 빠릅니다. 그래서 시간초과가 떠요.

사실 종현님 코드가 이렇게 시간초과가 떠야 정상인데.. 왜 틀린지는... 죄송합니다 ㅠ

그래서 종현님 코드스타일을 녹인 정답코드는 다음과 같구요.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M, H; 
int ladder[31][11];  
int answer = 1e9;  
bool check() {
    for (int i = 1; i <= N; i++) {
        int pos = i;
        for (int j = 1; j <= H; j++) {
            if (ladder[j][pos]) {
                pos = ladder[j][pos];
            }
        }
        if (pos != i) return false;
    }
    return true;
}

void go(int cnt, int y, int x) {
    if (cnt >= answer || cnt > 3) return;

    if (check()) {
        answer = min(answer, cnt);
        return;
    }  

    for (int i = y; i <= H; i++) {
        for (int j = (i == y) ? x : 1; j < N; j++) {
            if (ladder[i][j] == 0 && ladder[i][j + 1] == 0) {
                ladder[i][j] = j + 1;
                ladder[i][j + 1] = j;
                go(cnt + 1, i, j + 2);
                ladder[i][j] = 0;
                ladder[i][j + 1] = 0;
            }
        }
    }
}

int main() { 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> M >> H;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        ladder[a][b] = b + 1;
        ladder[a][b + 1] = b;
    }

    go(0, 1, 1); 
    
    if (answer > 3) cout << -1 << '\n';
    else cout << answer << '\n';
    
    return 0;
}

50% 부족한 답변..

죄송합니다..

감사합니다. 🙂

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

인프런 커뮤니티 질문&답변