글 읽기 - 테스트케이스, 예외 다 맞는데 왜...

sch0115 5년 전 0

알고리즘은 이렇습니다. 처음 입력을 box에 받고, 입력과 동시에 가장 높이가 높은 녀석을 저장합니다.

이후 높이에 따라 침수되는 녀석들을 0으로 마킹하면서 cbox에 복사합니다. 0보다 큰 녀석에 대해 dfs를 실행하여 안전구역을 구한 후 방문된 안전구역은 k로 마킹합니다. (k는 음수) , 하나의 높이에서 dfs가 모두 끝나면 -k에서 1을 뺀 값이 해당 높이에 대한 안전구역 개수가 됩니다... 테스트 케이스에서도 잘 동작하고, 비가 오지 않을 때 역시 잘 동작하는데 제출만하면 바로 틀렸습니다 가 나오네요... 도와주세요 ㅠ

#include <iostream>
#include <algorithm>
#include <queue>

/*
 * h를 2부터 n-1까지 선형적으로 올려가면서, 해당 이하의 높이를 cbox에 0로 마킹
 * cbox에서 0이 아닌 좌표에 대해 dfs 탐색, 탐색완료공간은 -k으로 마킹, k는 몇 번째 안전한 구역인지 나타냄
 * h for문이 한번 종료될때마다 k를 확인하고 ans값을 갱신, 다시 k을 초기화, cbox 초기화
 * */

using namespace std;

int box[101][101];
int cbox[101][101]; // clone box
int d_row[] = {-1,1,0,0};
int d_col[] = {0,0,-1,1};
int N;
int max_h = 0;
int k = 0;
int ans ;

bool isBoundary(int row, int col)
{
    bool isRow = row >=0 && row < N;
    bool isCol = col >=0 && col < N;

    return isRow && isCol;
}

void dfs(int row, int col)
{
    cbox[row][col] = k; // 방문 마킹
    int nrow, ncol;

    for (int i = 0; i < 4; ++i) {
        nrow = row + d_row[i];
        ncol = col + d_col[i];

        if(!isBoundary(nrow,ncol)) continue;
        if(cbox[nrow][ncol] > 0)
                dfs(nrow,ncol);
    }

}

void Solution()
{
    for (int h = 1; h < max_h -1; ++h) { // 물 높이
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if(box[i][j] <= h)
                    cbox[i][j] = 0; // 높이보다 낮다면 침수
                else
                    cbox[i][j] = box[i][j];
            }
        }
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if(cbox[i][j] > 0) { // 침수되지 않고, 방문하지 않은 노드
                    k--;
                    dfs(i, j);
                }
            }
        }
//        ---------------Print----------------
//        for (int i = 0; i < N; ++i) {
//            for (int j = 0; j < N; ++j) {
//                cout << cbox[i][j] << " ";
//            }
//            cout << endl;
//        }
//        cout << "K : " << k <<endl;
//        cout << "--------------------------" <<endl;
        if(ans < -k)
            ans = -k;
//        ans = max(ans,-k);
        k = -1;

    }
}



int main()
{
    cin >> N;

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> box[i][j];
            if(max_h < box[i][j])
                max_h = box[i][j];
        }
    }

    Solution();

    if(ans == 0)
        ans = 2;
    cout << ans-1 << endl;

    return 0;

}

park780172 5년 전 1

1. 읽어보세요! 클릭

2. 올려주신 코드 기준으로 48번 째 줄 h의 범위가 잘못됐습니다.

3. 또한, k = 0으로 시작하는데, 그 다음부터는 77번 째 줄에 의하여 k = -1로 시작해버립니다.

4. 3에 의하여, 98 ~ 100번 째 줄 코드도 수정하시면 됩니다.

park780172 5년 전 0

2468번 안전 영역

sch0115 5년 전 0

감사합니다!

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

문제

문제

출처

ICPC

테스트케이스, 예외 다 맞는데 왜...

sch0115 5년 전 0

park780172 5년 전 1

park780172 5년 전 0

sch0115 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말