[BaekJoon] 7511번 - 소셜 네트워킹 어플리케이션 [Java][C++]

문제 링크

---

1. 아이디어

소셜 네트워킹 어플리케이션에서는 두 사람이 친구 관계일 경우 친구 관계 그래프에서 경로가 존재한다. 사람을 노드, 관계를 간선으로 생각한 그래프에서 두 노드가 같은 그래프에 속했는지 판단하는 문제로 생각할 수 있고 유니온 파인드 알고리즘을 활용해서 두 사람이 같은 노드에 있는지 판단해줬다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {

    static int[] p;

    static void make(int n) {
        p = new int[n];
        for (int i = 1; i < n; i++) {
            p[i] = i;
        }
    }

    static int find(int x) {
        if (p[x] == x) return x;
        return p[x] = find(p[x]);
    }

    static void union(int x, int y) {
        p[find(y)] = find(x);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= t; tc++) {
            int n = Integer.parseInt(br.readLine());
            make(n);

            int k = Integer.parseInt(br.readLine());
            while (k-- > 0) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                union(a, b);
            }

            sb.append("Scenario ").append(tc).append(":\n");
            int m = Integer.parseInt(br.readLine());
            while (m-- > 0) {
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                if (find(u) == find(v)) {
                    sb.append("1\n");
                } else {
                    sb.append("0\n");
                }
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

vector<int> p(1000000);

int find(int x) {
    if (p[x] < 0) return x;
    return p[x] = find(p[x]);
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) p[y] = x;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;

    for (int tc = 1; tc <= t; tc++) {
        int n, k;
        cin >> n >> k;

        fill(p.begin(), p.begin() + n, -1);
        while (k--) {
            int a, b;
            cin >> a >> b;
            unite(a, b);
        }

        int m;
        cin >> m;

        cout << "Scenario " << tc << ":\n";
        while (m--) {
            int u, v;
            cin >> u >> v;
            cout << (find(u) == find(v)) << '\n';
        }
        cout << '\n';
    }
}

---

3. 디버깅

입력이 뭔 소리인지 이해하기 어려웠는데 초기 테스트 케이스의 수를 먼저 입력으로 준다.

---

4. 참고

없음.

---