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

안녕하세요 정재님 ㅎㅎ

최대한 정재님 스타일로 코드를 다듬어봤습니다.

#include <bits/stdc++.h>
using namespace std;

int N, M, H;
int visited[30][10];
int ret = INT_MAX;

bool ladder() {
    for (int start = 0; start < N; start++) {
        int pos = start;
        for (int h = 0; h < H; h++) {
            if (pos < N-1 && visited[h][pos])
                pos++;
            else if (pos > 0 && visited[h][pos-1])
                pos--;
        }
        if (pos != start) return false;
    }
    return true;
}

void dfs(int startRow, int startCol, int cnt) {
    if (cnt >= ret) return;
    if (ladder()) {
        ret = cnt;
        return;
    }
    if (cnt == 3) return;

    for (int i = startRow; i < H; i++) {
        for (int j = (i == startRow ? startCol : 0); j < N-1; j++) {
            if (visited[i][j] ||
                (j > 0      && visited[i][j-1]) ||
                (j < N-2    && visited[i][j+1])) continue;

            visited[i][j] = 1;
            dfs(i, j + 2, cnt + 1);
            visited[i][j] = 0;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M >> H;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        visited[a-1][b-1] = 1;
    }

    dfs(0, 0, 0);
    cout << (ret <= 3 ? ret : -1) << "\n";
    return 0;
}

새행부터는 0부터 탐색, 연속해서 사다리 놓치 못하게하는 것, 가지치기 이 3개를 중점으로만 봐주시면 됩니다.

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

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

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다. 이정재님. 사다리 조작 문제 해결 관련해서 반복적으로 “틀렸습니다” 결과를 받으셨다고 하셨네요. 이 문제에서는 보통 사다리의 설정과 방향성이 중요한데, 틀린 이유는 사다리를 추가하거나 이동시키는 로직에서 발생할 수 있습니다.

다음은 사다리 조작 문제와 관련된 이전 답변들이며, 참고하실 만한 내용들로 도움을 드릴 수 있을 것 같습니다:

1. 15684 사다리조작 로직 틀린이유 질문드립니다

   • 기본적인 로직의 순환과 재귀 구조 확인에 도움이 될 수 있는 내용입니다.
     

2. 3-O 질문있습니다

   • 적절한 사다리 추가 로직과 확인 조건 설정에 대한 팁을 얻을 수 있습니다.
     

3. 15684 사다리 조작 추가 질문입니다

   • 시간 초과를 해결하기 위한 최적화 방법에 대한 논의가 포함되어 있습니다.
     

주요 포인트로 살펴보아야 할 부분은 다음과 같습니다:
- 사다리가 추가될 수 있는 위치가 올바른지, 즉 양 옆이나 위/아래 제한에 걸리지 않는지 확인해야 합니다.
- 재귀 함수나 DFS를 사용할 때, 사다리를 놓는 경우와 놓지 않는 경우 모두 탐색해야 하지만 중복되지 않도록 해야 합니다.
- 최적의 경로를 찾기 위해 가능한 모든 경우의 수를 탐색하지만, 제한 사항으로 인해 만약 3보다 많은 사다리를 놓아야 할 경우에는 -1을 반환해야 합니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.