글 읽기 - visted의 초기화 이유?

jwl0105 2년 전 0

오늘도 어김없이 여러 삽질을 하며 고통 받는 학생입니다..ㅠㅠ

반례도 잘 통과하고 문제없이 맞겠거니 싶던 문제가 저를 비웃기나 하듯이 틀렸습니다가 나와서

수많은 질문들을 찾아보며 답을 찾고 있었습니다.

그 중 어떤 댓글에

테스트케이스 마다 visited를 초기화해야한다고 알려주셨습니다. 그래서 visited를 초기화하는 clean이라는 함수를 만들어 실행하니 맞았습니다.

근데 여기서 궁금한 것이 생겼습니다. visited를 초기화해주는 이유는

두번째, 세번째 혹은 그 이후의 경우에서 전의 visited 배열을 참조해서 확인하지 않는 배열이 나올 수도 있기 때문이라고 했습니다.

근데 왜 제가 여러 예제들을 돌려볼때는 그런 경우가 나타나지 않은걸까요?

예를 들어

2

2 2 2

0 1

1 0

2 2 2

0 1

1 0

처럼 아예 똑같은 예제를 돌렸을 때도, 답이 2/ 2로 잘 나왔어서

visited를 초기화 하지 않아도 답이 똑바로 나오는 경우는 무엇인지 궁금합니다.

#include <stdio.h>
int map[50][50], visited[50][50], ans[50][50], hor=0, ver=0, cnt=0; //hor=가로, ver=세로
int move_v[4]={0,1,0,-1}, move_h[4]={1,0,-1,0};
void clear()
{
    for(int c=0; c<50; c++)
    {
        for(int d=0; d<50; d++)
        {
            visited[c][d]=0;
            map[c][d]=0;
            ans[c][d]=0;
        }
    }
    cnt=0;
}
void use_dfs(int n, int m)
{
    int garo=0, sero=0;
    visited[n][m]=1;
    ans[n][m]=cnt;
    for(int q=0; q<4; q++)
    {
        sero=n+move_v[q];
        garo=m+move_h[q];
        if(garo<0 || sero<0 || garo>=hor || sero>=ver)
        continue;
        else
        {
            if(visited[sero][garo]==0 && map[sero][garo]==1)
            {
                ans[sero][garo]=cnt;
                use_dfs(sero, garo);
            }
        }
    }
}
void find_earthworm()
{
    for(int a=0; a<ver; a++)
    {
        for(int b=0; b<hor; b++)
        {
            if(visited[a][b]==0 && map[a][b]==1)
            {
                cnt++;
                use_dfs(a,b);
            }
        }
    }
}
int main()
{
    int test=0, cabbage=0, temp1=0, temp2=0;
    scanf("%d", &test);
    for(int i=0; i<test; i++)
    {
        scanf("%d %d %d", &hor, &ver, &cabbage);
        for(int j=0; j<cabbage; j++)
        {
            scanf("%d %d", &temp1, &temp2);
            map[temp2][temp1]=1;
        }
        find_earthworm();
        printf("%d\n", cnt);
        clear();
    }
}

zenith82114 2년 전 0

테스트 케이스를 tc라고 쓰겠습니다.

tc 하나가 끝났을 때 visited가 어떤 상태일지 생각해 보면

map이 0이었던 곳은 visited도 0일 것이고,

map이 1이었던 곳은 0보다 큰 값 (그곳을 방문할 당시 cnt의 값)일 겁니다.

따라서

"(k+1)번째 tc에서 map이 1인 곳 중에

k번째 tc에서 범위 밖이었거나 map이 0이었던 곳들을 0으로 바꿔도

(k+1)번째 tc의 정답이 변하지 않는다."

이것이 모든 k에 대해 참이면

visited는 초기화하지 않고 cnt만 초기화해도 정답이 되겠네요.

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