gaelim   2년 전

무엇이 문제인지 모르겠습니다. 게시판에 있는 반례는 전부해본거같습니다. 어떤 반례가 있을까요? 16%에서 틀렸다고 나옵니다.


#include <stdio.h>

int main(){
  int comp[101];
  int chk[101][101];
  int n, i, j, link;
  scanf("%d", &n);
  scanf("%d", &link);
  comp[1]=1;
  for(i=0; i<link; i++){
    int pc1, pc2;
    scanf("%d %d", &pc1, &pc2);
    chk[pc1][pc2]=1;
    chk[pc2][pc1]=1;
  }
  for (i=1; i<=n;i++){
    for (j=1; j<=n; j++){
      if (chk[i][j]) {
        comp[i] |=comp[j];
        comp[j] |=comp[i];
      }
    }
  }
  int ans=0;
  for(i=2;i<=n;i++)
    ans+=comp[i];
  printf("%d\n", ans);
  return 0;
}

djm03178   2년 전

comp랑 chk랑 초기화가 전혀 되어 있지 않으니 문제가 발생합니다. 어떤 컴파일러들에서는 알아서 초기화를 해주는지 모르겠지만, 원래는 지역 변수의 경우 명시적 초기화를 하지 않으면 쓰레기값이 들어있는 게 맞습니다.

gaelim   2년 전

@djm03178 제가 가능한 초기화라던가 이런거 해보았지만 여전히 틀렸습니다... 아무래도 알고리즘상에서 문제가 있는것같습니다.

djm03178   2년 전

일단 반례는 여기 드립니다.

4 3

1 4

4 3

3 2

답은 3이지만, 2를 출력합니다.

살짝 수정해서 정답을 띄울 수 있는지 시도해봤는데, 한문장 추가하는 걸로는 40%대에서 틀리는 정도밖에 못 만들겠네요. 좀 더 검증 가능한 알고리즘을 생각해보세요.

djm03178   2년 전

현재 코드를 가장 조금 수정하고 맞게 나오는 방법은 이 전체 과정을 n라운드 반복해서 진행하는 거지만, Θ(N^3)이 걸리는 알고리즘이라 매우 비효율적입니다. 이 코드는 N이 워낙 작아서 0MS AC가 떴기는 하지만요.

gaelim   2년 전

@djm03178 님 감사합니다 좀더 분발해보겠습니다

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