친구 찾기문제

#include <stdio.h>

int parent[1001];

// Find 부모 찾기
int find(int x) {
    if (x == parent[x]) 
        return x;
    else
        return parent[x] = find(parent[x]);  // 경로 압축
}

// Union 
void union(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);
    
    if (rootA != rootB) {
        parent[rootA] = rootB; 
    }
}

int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    
    for (int i = 1; i <= N; i++) {
        parent[i] = i;
    }
    
    // 친구 관계 입력
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        union_students(a, b);
    }
    
    // 마지막 두 학생이 친구인지 확인
    int student1, student2;
    scanf("%d %d", &student1, &student2);
    
    // 두 학생이 같은 그룹에 속하는지 확인
    if (find(student1) == find(student2)) {
        printf("YES\n");
    } else {
        printf("NO\n");
    }
    
    return 0;
}

이 코드는 "Union-Find(합집합-찾기)" 알고리즘을 사용하여 학생들의 친구 관계를 처리하고, 두 학생이 같은 친구 집단에 속하는지를 판별합니다. 주어진 문제에서는 학생들의 친구 관계를 여러 쌍으로 제공하고, 마지막으로 두 학생이 같은 친구 집단에 속하는지 확인해야 합니다.

코드 구성 및 각 부분의 역할

1. parent 배열


int parent[1001];

parent 배열은 각 학생이 속한 그룹의 부모(연결 된 친구)를 저장하는 배열입니다. 각 인덱스는 학생의 번호를 나타내고, 그 값은 해당 학생이 속한 그룹의 부모를 나타냅니다. 예를 들어, parent[1] = 3이라면 1번 학생의 부모는 3번 학생입니다.

초기에는 모든 학생이 자기 자신을 대표자로 가집니다. 이를 통해 모든 학생이 각각 독립된 집합으로 시작할 수 있습니다.

2. find 함수

int find(int x) {
    if (x == parent[x])
        return x;
    else
        return parent[x] = find(parent[x]);
}

find 함수는 재귀적으로 해당 학생이 속한 그룹의 부모(루트)를 찾는 함수입니다.

3. union 함수

void union(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);

    if (rootA != rootB) {
        parent[rootA] = rootB;
    }
}

union 함수는 두 학생이 속한 집합을 하나로 합치는 함수입니다. 이를 위해 먼저 두 학생의 그룹 부모(루트)를 각각 찾고, 그 부모들이 다르다면 한쪽의 부모를 다른 쪽 부모로 설정합니다.

4. main 함수

c
코드 복사
int main() {
    int N, M;
    scanf("%d %d", &N, &M);

    // 초기화: 각 학생은 자기 자신이 부모입니다.
    for (int i = 1; i <= N; i++) {
        parent[i] = i;
    }

    // 친구 관계 입력
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        union(a, b);
    }

    // 마지막 두 학생이 친구인지 확인
    int student1, student2;
    scanf("%d %d", &student1, &student2);

    // 두 학생이 같은 그룹에 속하는지 확인
    if (find(student1) == find(student2)) {
        printf("YES");
    } else {
        printf("NO");
    }

    return 0;
}