글 읽기 - 1976번 이게 왜 맞았는지 모르겠습니다.

ZZangZZang 9년 전 2

자꾸 런타임 에러나서 find 함수에서 n이 바운드를 벗어나서 그런가 해서 if(x>=n) return 0; 를 집어넣었더니 정답이라고 떴어요.

근데 문제에서는 1~n 으로 입력이 주어지는데 전 버릇 때문에 0~n-1 로 가정하고 풀었단 말이죠.

근데 런타임 에러가 나던게

if(x>=n) return 0;

이거 하나 집어넣었다고 문제가 맞다니 뭔가 이상합니다 ㅋㅋㅋ... 틀려야하는거같은데.

#include <stdio.h>
class DisjointSet {
private:
    int n;
    int parent[300];
public:
    DisjointSet(int n): n(n) {
        for(int i=0; i<n; i++)
            parent[i] = i;
    }
 
    ~DisjointSet() {
    }
 
    int find(int x) {
        if(x>=n) return 0;
        return parent[x] != x ? parent[x] = find(parent[x]) : x;
    }
 
    void unify(int x, int y) {
        int xRoot = find(x),
            yRoot = find(y);
        if(xRoot == yRoot)
            return;
        if(xRoot < yRoot)
            parent[yRoot] = xRoot;
        else
            parent[xRoot] = yRoot;
    }
};
 
int main() {
    int N, M, i, j;
    scanf("%d %d", &N, &M);
    DisjointSet set(N);
    for(i=0; i<N; i++) {
        for(j=0; j<N; j++) {
            int e;
            scanf("%d", &e);
            if(e) {
                set.unify(i, j);
            }
        }
    }
     
    int boo = -1;
    for(i=0; i<M; i++) {
        int e;
        scanf("%d", &e);
        e = set.find(e);
        if(boo != -1 && boo != e)
            break;
        if(boo == -1)
            boo = e;
    }
    puts(i==M ? "YES" : "NO");
    return 0;
}

joonas 9년 전 0

말씀을 인용하자면 "1~n 으로 입력이 주어지는데" 별다른 처리 없이 바로 find(e) 로 호출하셨네요. 그럼 find 에서 x 의 범위는 1~n 이 되지 않을까요? ㅎㅎ

x >= n 으로 하시면 배열을 [0...n] 까지 사용하는데 x > n 으로 하시면 [0 ... n-1] 까지 사용해서 n번째 인덱스를 놓치게 되버리죠.

아마 find(e-1) 로 하시면 정답 나오실거같습니다.

WeissBlume 9년 전 1

잘 생각해보면 문제가 없단걸 알 수 있습니다.

1번 정점은 1을 루트로, 2번 정점은 2를 루트로, ..., n번 정점은 0을 루트로 하도록 초기화했다고 하면,

unify()의 구현에 따라 n번 정점과 합집합되는 모든 집합은 0을 루트로 하게 되기 때문에 find(n)은 항상 옳은 값을 리턴하겠죠?

따라서 한 칸씩 ROL된듯한 저 집합은 의외로 옳은 동작을 하게 됩니다!

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

문제

문제

출처

ICPC

1976번 이게 왜 맞았는지 모르겠습니다.

ZZangZZang 9년 전 2

joonas 9년 전 0

WeissBlume 9년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말