글 읽기 - 2668 숫자고르기 질문입니다.

ljy8947 8년 전 0

chk에 경로 표시하면서 dfs로 따라 들어가는 식으로 짰는데, 오답이 나옵니다.

몇 가지 테스트 케이스를 넣어봐도 왜 틀렸는지를 모르겠습니다.

#include <stdio.h>
#include <algorithm>

int n, arr[105], chk[105], path[200];
int cnt, max, add, idx, k;

void f(int m)
{
    if(arr[m]==m) // 함정 사이클에 빠짐. 5 5 같은.
    {
        cnt=0;
        return;
    }
    else if(chk[arr[m]]==1)// 다음 갈 노드가 사이클 내부. 실패.
    {
        cnt=0;
        return;
    }
    else if(chk[arr[m]]==2) // 다음 노드가 사이클 초입. 성공.
    {
        cnt++;
        chk[m]=1;
        return;
    }
    else
    {
        cnt++;

        if(cnt==1)
            chk[m]=2;
        else
            chk[m]=1;

        f(arr[m]);
    }
}
int main()
{
    int max_k=0;
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        scanf("%d", &arr[i]);

    for(int i=1; i<=n; i++)
    {
        if(arr[i]==i)
        {
            add++;
            path[k++]=i;
        }
    }
    idx=k; // k-1 까지는 고정. k부터 초기화 시켜라.
    for(int i=1; i<=n; i++)
    {
        f(i);

        if(cnt>max)
        {
            max=cnt;
            for(int j=1; j<=n; j++)
            {
                if(chk[j])
                    path[k++]= j;
            }
            max_k=k;
        }

        cnt=0;
        for(int j=1; j<=n; j++)
            chk[j]=0;

        k=idx; // 반복 할 때마다 k를 다시 시작 값으로.
    }

    printf("%d\n",max+add);
    std::sort(path, path+max_k);
    for(int i=0; i<max_k; i++)
        printf("%d\n", path[i]);

    return 0;
}

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

문제

문제

출처

ICPC

2668 숫자고르기 질문입니다.

ljy8947 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말