글 읽기 - [캠프문제] 질문있어요. - biconnected component로 풀었습니다.

plzrun 6년 전 0

아 제 생각이 틀린것 같군요..

같은 bcc안에 있어도 차이가 d만 있는게 아니라 2d일때도 있다는걸 알았습니다. 다른 방법으로 접근해야겠군요 ㅠ

~~다른 분들 소스코드 길이로 보아~~

~~심히 다른 방법으로 풀지 않았나 생각이 드는데요, ㅋ~~

~~biconnected component끼리 묶어주구요 (앞으로 bcc라고 할게요.)~~

여기서 묶을때 만약 그래프가 2개 이상의 컴포넌트로 분리되는 경우가 생기면 바로 -1을 출력하고 종료하도록 했습니다. 또 처음 입력받고 나서 전부 N인경우에는 바로 -1을 출력하도록 했어요.

~~bcc끼리 묶고나면,~~

~~그건 이제 그래프가 아니라 트리니까... dfs돌려서 (제 코드에선 dfs2()라는 함수)트리의 지름을 구했습니다.~~

~~제 접근방식이 맞는걸까요? (맞는것 같은데... ㅋㅋㅋ)~~

~~맞다면, 어떤케이스를 놓친걸까요?~~

~~답변주시면 감사하겠습니다~!~~

#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
char v[51][51], g[51][51];
int discov[51], bcc[51];
int n,d,dscnt=0,no=0;
stack<int> s;
int dfs(int x, int p) {
    s.push(x);
    int ret=discov[x]=++dscnt;
    for(int i=0; i<n; i++) {
        if(v[x][i]=='Y') {
            if(!discov[i]) ret = min(ret,dfs(i,x));
            else if(i!=p&&!bcc[i]) ret = min(ret,discov[i]);
        }
    }
    if(ret==discov[x]) {
        //printf("ret:%d, discov[%d]:%d\n",ret,x,discov[x]);
        no++;
        while(true) {
            int z = s.top(); s.pop();
            //printf("z: %d\n",z);
            bcc[z]=no;
            if(discov[z]==discov[x]) break;
        }
    }
    return ret;
}
bool chk[51];
int start,mx;
void dfs2(int x, int len) {
    if(mx<len) {
        mx=len;
        start=x;
    }
    chk[x]=true;
    for(int i=1; i<=no; i++) {
        if(g[x][i]&&!chk[i]) {
            dfs2(i,len+1);
        }
    }
}
int main() {
    bool hasAns=false;
    scanf("%d%d", &n,&d);
    
    //그래프 입력받습니다.
    for(int i=0; i<n; i++) {
        scanf("%s",v[i]);
        int lim = strlen(v[i]);
        for(int j=0; j<lim; j++) {
            if(v[i][j]=='Y') hasAns=true;
        }
    }
    //처음 안되는 부분 처리 (n==1일때는 안들어오지만, 혹시나 해서 넣어봤습니다.)
    if(n==1) return 0&puts("0");
    else if(!hasAns) return 0&puts("-1");

    //bcc[노드번호] = bcc 그룹 번호 (이런 형태로 assign됩니다.)
    bool light=false;
    for(int i=0; i<n; i++) {
        if(!discov[i]&&!light) {
            dfs(i,-1);
            light=true;
        } else if(!discov[i]&&light) {
            return 0&puts("-1");
        }
    }

    //만들어진 bcc를 바탕으로 새로운 그래프를 만들어줍니다. (이 그래프는 g라는 인접행렬로 표현)
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(v[i][j]=='Y') {
                if(bcc[i]!=bcc[j]) g[bcc[i]][bcc[j]]=true;
            }
        }
    }
    //트리 지름 구하는 부분
    dfs2(1,0);
    memset(chk,false,sizeof(chk));
    dfs2(start,0);
    printf("%d", mx*d);
    return 0;
}

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