글 읽기 - 이유를 모르겠습니다.

jwl0105 2년 전 0

변수 초기화도 잘하고 있고, 그림의 개수 파악이나 넓이 파악도 잘하고 있고, 반례도 잘 나오고 있습니다.. ㅠㅠ

반례 한번 부탁드리겠습니다.

#include <stdio.h>
int map[501][501], ans[501][501], visited[501][501], x_size=0, y_size=0, cnt=0, picture=0, temp=0;
int move_x[4]={1,0,-1, 0}, move_y[4]={0,1,0,-1};
void use_dfs(int y, int x)
{
    
    for(int q=0; q<4; q++)
    {
        int next_x=x+move_x[q];
        int next_y=y+move_y[q];
        if(next_y>=0 && next_y<y_size && next_x>=0 && next_x<x_size && visited[next_y][next_x]==0 && map[next_y][next_x]==1)
        {
            ans[next_y][next_x]=ans[y][x]; // 같은 그림일 경우, 같은 숫자
            temp++; // 넓이 증가
            if(temp>picture) // 각 넓이가 가장 넓은 경우 picture에 저장
            picture=temp;
            visited[next_y][next_x]=1;
            use_dfs(next_y, next_x);
        }
    }
    
}
void check() // 방문 안한 곳과, 그림이 존재하는 곳을 찾으면 dfs 함수 호출
{
    for(int a=0; a<y_size; a++)
    {
        for(int b=0; b<x_size; b++)
        {
            if(map[a][b]==1 && visited[a][b]==0)
            {
                ans[a][b]=++cnt;
                visited[a][b]=1;
                temp=1; // 각 그림의 넓이 파악을 위해 매번 1로 초기화
                use_dfs(a,b);
            }
        }
    }
}
int main()
{
    scanf("%d %d", &y_size, &x_size);
    for(int i=0; i<y_size; i++)
    {
        for(int j=0; j<x_size; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
    check();
    printf("%d\n%d", cnt, picture);
}

jwl0105 2년 전 2

자문자답..

ex)

input

4 4

0 0 1 0

1 0 0 0

0 0 0 0

0 0 0 1

output

이런 경우에서 제 코드는 (3 / 0) 이 나왔습니다.

이유는 dfs 함수를 들어가서 이동할 곳이 있는 경우에만 최대 넓이를 초기화하고

만약 이동할 경우가 없다면 1이 하나만 존재해서 최대넓이가 1이 되는 경우에는 최대넓이가 초기화가 되지 않는 경우가 있었습니다. 그 부분을 수정했더니 맞았습니다..ㅠㅠ

좀 더 정확하게 알아보도록 하겠습니다..!

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

문제

문제

출처

ICPC

이유를 모르겠습니다.

jwl0105 2년 전 0

jwl0105 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말