글 읽기 - 살려주세요... 문제 TC와 질문 게시판 반례 다 맞는데 바로 틀렸습니다.

curve4403 4년 전 0

대략적인 알고리즘은 이렇습니다.

map에서 h의 n에 사다리를 놓으면, n에서 n + 1, 혹은 n + 1에서 n으로 세로 선을 갈아탈 수 있다는 의미로,

map의 [h][n]에는 n + 1로 기록하고, [h][n +1]에는 n으로 기록했습니다.

이 후, chk_result 함수에서 각 n(열)의 처음 h가 1일 때부터 끝 부분 H일 때까지 검사하여, 처음 지점의 n과 끝 지점의 n 값이 다르면 올바르지 않은 결과(i번 사다리를 탔을 때 i번으로 나오지 않는)로 판단합니다.

문제에서 제시된 TC와 질문 게시판에 있는 반례를 모두 찾아 돌렸는데 에러가 나지 않았습니다. 하지만 백준에 제출 시,

map의 크기를 [11][31]로 했을 때 런타임 에러가 발생했습니다.
그래서 map의 크기를 [100][100]으로 늘렸을 때에는 틀렸습니다.

혹시 코드에서 제가 놓치거나 잘 못 작성한 알고리즘이 있는지 확인해주시면 정말 감사하겠습니다..!

한 달 전에도 같은 문제로 포기하고, 어제 다시 풀었는데도 같은 문제가 발생해서 매우 혼란스럽네요.. 부끄러움을 무릎쓰고 부탁드립니다..!

/*
 * 사다리 조작
 */

#include <iostream>
#include <vector>

using namespace std;

int N, M, H; //[세로 선의 개수], 가로 선의 개수, [세로 선 마다 가로 선을 놓을 수 있는 위치의 개수]
int map[11][31];
int cnt;

bool chk_result() {
    //세로 선 하나 선택
    for(int n = 1; n <= N; n++) {
        int current_n = n, start_n = n;
        //세로 선 결과 확인 위한 아래로 전진
        for(int h = 1; h <= H; h++) if(map[h][current_n] > 0) current_n = map[h][current_n];    //다른 세로 선을 타야하는 경우
        if(start_n != current_n) return false;          //시작 점 start_n과 결과 점 비교
    }
    return true;
}

int minimum = 99999;
void solution(int idx) {
    if(minimum < cnt) return;               //최소 사다리 개수보다 더 많은 사다리를 추가하려고 하는 경우 종료
    if(cnt > 3) return;                     //더 이상 사다리를 추가할 수 없는 경우 종료
    if(chk_result()) {                      //결과 값 확인 후 옳은 경우 최소 값 갱신 후 종료
        if(minimum > cnt) minimum = cnt;
        return;
    }

    //사다리 설치
    for(int h = idx; h <= H; h++) {
        for(int n = 1; n < N; n++) {
            //이미 사다리가 놓인 위치인 경우 제외
            if(map[h][n] != 0 && map[h][n - 1] != 0 && map[h][n] == n - 1) continue;
            if(map[h][n] != 0 && map[h][n - 1] != 0 && map[h][n] == n + 1) {
                n += 1;
                continue;
            }
            //놓으려고 하는 위치의 오른쪽에 사다리가 이미 놓인 경우 제외
            if(map[h][n + 1] != 0) {
                n += 2;
                continue;
            }
            //n이 2 이상인 경우, 놓으려고 하는 위치의 왼쪽에 사다리가 이미 놓인 경우 제외
            if(n != 1 && map[h][n - 1] != 0) continue;

            //사다리 설치 시작
            map[h][n] = n + 1;
            map[h][n + 1] = n;
            cnt++;

            solution(h);

            //사다리 원 상태로 복구
            cnt--;
            map[h][n] = 0;
            map[h][n + 1] = 0;
        }
    }

}

int main() {
    cin >> N >> M >> H;
    for(int i = 0; i < M; i++) {
        int tmpH, tmpN;
        cin >> tmpH >> tmpN;
        map[tmpH][tmpN] = tmpN + 1;
        map[tmpH][tmpN + 1] = tmpN;
    }

    solution(1);

    if(minimum == 99999) minimum = -1;
    cout << minimum << endl;

    return 0;
}

luniro 4년 전 1

map[h][n]이라서 map[31][11]이 돼야합니다

댓글을 작성하려면 로그인해야 합니다.