글 읽기 - 98%...에서 틀렸습니다.. 제발 한번만 도와주세요 ㅠㅠ

jwl0105 1년 전 0

0%에서 틀리나 98%에서 틀리나 별 차이 없는건 알고 있습니다... 근데 도저히 모르겠습니다.. 왜 이게 틀린건지 감도 안오고 미치겠습니다.. 고수님들 한번만 도와주십쇼..ㅠㅠ

제가 푼 방법

일단 저는 모든 0에 대해서 판단할 필요가 없다고 생각했습니다. 1의 주변에 있는 곳에서 0 -> 1 의 변화가 최댓값을 도출할 수 있다고 생각했기 때문입니다.

그래서 저는 처음 입력받은 1에 대한 위치를 enqueue()로 넘긴 뒤 해당 위치에 대한 주변(제 코드에서는 next.x, next.y)에 0을 1로 변환할 수 있다고 생각했습니다.

그리고 그 0에서 1로 바뀐 위치에 대한 주변에 연결 될 수 있는 그룹의 크기를 더해서 각 상황별로 최대값을 구할 수 있다고 생각했습니다.

제가 말을 못해서 괜히 더 어렵게 설명드린거 같습니다.. 계속 안풀려서 구글링 했는데 제 방법과 구글링해서 나오는 코드의 다른 점은

구글링은 모든 0의 좌표를 확인하고

저는 1의 주변에 있는 0의 좌표만 확인하는 점이 다른 부분입니다.

주석 달겠습니다.. 제발 한번만 도와주십쇼...

#include <stdio.h>
int map[1001][1001], section[1001][1001], visited[1001][1001], size[1000001], move_x[4]={1,0,-1,0}, move_y[4]={0,1,0,-1}, y_size=0, x_size=0, front=0, rear=0, cnt=0, sum=0, ans=0;
typedef struct _Point
{
    int x, y;
}Point;
Point queue[5000000];
void enqueue(Point n)
{
    queue[rear++]=n;
}
Point dequeue()
{
    return queue[front++];
}
void use_bfs()
{
    Point temp, next, check;
    int arr[5]; // 4방향을 확인하기 위한 배열
    while(front<rear)
    {
        temp=dequeue(); // 기존 1의 위치 가져오기
        for(int q=0; q<4; q++)
        {
            next.x=temp.x+move_x[q]; 
            next.y=temp.y+move_y[q];// next== 기존 1의 주변 == 0 -> 1로 변화하는 위치
            if(next.x>=0 && next.x<x_size && next.y>=0 && next.y<y_size && visited[next.y][next.x]==0)
            {
                sum=0; // 4방향에 대해서 연결될 수 있는 그룹의 크기 더하는 변수
                visited[next.y][next.x]=1;
                for(int w=1; w<5; w++)
                {
                    check.x=next.x+move_x[w-1];
                    check.y=next.y+move_y[w-1]; //check == 1로 변화된 곳 주변에 연결될 그룹 확인
                    int num=section[check.y][check.x]; // 그룹의 번호 num에 저장 // 0도 저장 될 수 있음
                    for(int e=0; e<w; e++) // 중복을 피하기 위한 반복문 4방향 중 같은 그룹이 2번 이상 들어가는 경우 배제
                    {
                        if(num==arr[e]) // 기존에 파악했던 그룹이라면
                        {
                            arr[w]=0; // 0으로 둬서 더하는 값에 지장이 없도록 함
                            break;
                        }
                        else
                        arr[w]=num; // 중복 없는 경우
                    }
                    sum+=size[arr[w]]; // 방향에 대해 그룹의 크기 더한 뒤 저장
                }
                arr[1]=0; 
                arr[2]=0;
                arr[3]=0;
                arr[4]=0; // 혹시 모르니깐 arr 초기화
            }
            if(ans<sum) // 더한 값이 ans보다 큰 경우 초기화
            ans=sum;
        }
    }
}
void use_dfs(int y, int x, int island)
{
    Point temp;
    ++cnt; // 크기 파악
    visited[y][x]=1;
    for(int q=0; q<4; q++)
    {
        int next_x=x+move_x[q];
        int next_y=y+move_y[q];
        if(next_x>=0 && next_x<x_size && next_y>=0 && next_y<y_size && visited[next_y][next_x]==0 && map[next_y][next_x]==1)
        {
            section[next_y][next_x]=section[y][x]; // 같은 그룹은 같은 숫자로 section에 저장
            temp.y=next_y;
            temp.x=next_x;
            enqueue(temp); // 1인 부분 enqueue
            use_dfs(next_y, next_x, island);
        }
    }
}
void make_group() // 1의 그룹화, 해당 그룹에 대한 크기 저장
{
    int island=0;
    Point start;
    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)
            {
                ++island;
                section[a][b]=island; // 그룹화 해서 나타낸 배열 : section/ island는 그룹의 번호
                start.y=a;
                start.x=b;
                enqueue(start); //1의 위치를 인큐
                use_dfs(a, b, island); // dfs를 이용해서 그룹과 크기 파악
                size[island]=cnt; // size[그룹의 번호]=그룹의 크기
                cnt=0;
            }

        }
    }
}
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]);
        }
    }
    make_group(); // 그룹 짓고, 크기 저장
    use_bfs(); // 유의미한 곳에 0을 1로 바꾸면서 그룹의 최대 크기 찾기
    printf("%d", ans+1); // ans=연결된 그룹의 크기의 합 + 0에서 1로 변화한 곳
}  

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

문제

문제

출처

ICPC

98%...에서 틀렸습니다.. 제발 한번만 도와주세요 ㅠㅠ

jwl0105 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말