글 읽기 - 배열의 초기화 여부가 왜 정답/오답을 가리는지 모르겠습니다 ㅠ

noname_0x16 3년 전 0

47번의 memset을 이용한 table을 초기화 하는 부분이 왜 정답.오답을 가리는지 모르겠습니다 ㅠ

원래는 47번라인 없이 제출해서 틀렸다고 뜬 후, 질문을 검색해보았는데요..

w, h가 큰 값이 입력되고 나서 w, h가 작은 값이 입력되었을 때 문제가 될 수 있다고 적혀있어서 수정했습니다.

근데 왜 문제가 되는지 이해가 안되서 이렇게 질문을 올립니다.

제 코드에서 dfs를 나오고나면 섬이었던 (1이었던) 값들은 전부 0이 될텐데, 굳이 다음 타임에 초기화를 해야되나? 라고 생각해서..

어떤 문제가 생기는지 알려주세요

#include <iostream>
#include <cstring>

using namespace std;

bool table[51][51];
int w = 1, h = 1;

int dfs(int ny, int nx)
{
    table[ny][nx] = false;
    if (ny > 0) {
        if(table[ny - 1][nx] == 1)
            dfs(ny - 1, nx);
        if (nx > 0 && table[ny - 1][nx - 1] == 1)
            dfs(ny - 1, nx - 1);
        if (nx < w - 1 && table[ny - 1][nx + 1] == 1)
            dfs(ny - 1, nx + 1);
    }
    if (ny < h - 1) {
        if (table[ny + 1][nx] == 1)
            dfs(ny + 1, nx);
        if (nx < w - 1 && table[ny + 1][nx + 1] == 1)
            dfs(ny + 1, nx + 1);
        if (nx > 0 && table[ny + 1][nx - 1] == 1)
            dfs(ny + 1, nx - 1);
    }
    if (nx > 0 && table[ny][nx - 1] == 1)
        dfs(ny, nx - 1);
    if (nx < w - 1 && table[ny][nx + 1] == 1)
        dfs(ny, nx + 1);
    
    return 0;
}

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

    while (1)
    {
        cin >> w >> h;
        if (w == 0 || h == 0)
            break;
        memset(table, 0, sizeof(table));
        for (int i = 0; i < h; i++)
            for (int k = 0; k < w; k++)
                cin >> table[i][k];

        int cnt = 0;
        for (int i = 0; i < h; i++) {
            for (int k = 0; k < w; k++) {
                if (table[i][k] == 1) {
                    dfs(i, k);
                    cnt++;
                }
            }
        }
        cout << cnt << '\n';
    }

    return 0;
}

ghghgh777 3년 전 0

해당 라인 지우고 제출해도 맞았습니다 가 나옵니다.

이전 제출이 틀렸던 이유는 while문 조건이 w != 0 && h != 0 이라서 마지막으로 들어오는 0 0 입력을 처리하여 0을 출력한 뒤 while문을 빠져나왔기 때문입니다.

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

문제

문제

출처

ICPC

배열의 초기화 여부가 왜 정답/오답을 가리는지 모르겠습니다 ㅠ

noname_0x16 3년 전 0

ghghgh777 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말