4195번 - 친구 네트워크

2024-07-09

#JAVA#백준

문제 링크

문제 풀이 시간 : 1시간

문제 요약

•
어떤 사이트의 친구 관계가 생긴 순서대로 주어진다.

•
두 사람의 친구 네트워크에 몇 명이 있는지 구하라.

•
첫째 줄에 테스트 케이스의 개수가 주어진다.

•
각 테스트 케이스의 첫째 줄에 친구 관계의 수 F ( ≤ 100,000) 가 주어진다.

•
다음 F 개의 줄에는 친구 관계가 생긴 순서대로 주어진다.

문제 풀이

이 문제는 그냥 골드2에 비해 쉬워보여서 선택했다.

처음에는 무지성으로 해시맵에 그냥 이름, 친구 수 를 넣어서 친구가 추가될 때마다 두 명의 친구 수를 합해서 업데이트 해주면 되는거 아닌가?

라는 생각으로 코드를 짰다.

아래와 같은 코드를 이용해서

network 라는 해시맵에 해당 이름이 있다면 해당 이름의 친구 수를 가져오고,

없다면 1을 가져와 두 사람의 친구수의 합을 구했다.

그렇게 구한 새로운 친구 수를 network에 업데이트 하고, 출력하여 아주 쉽게 풀었다고 생각했는데..

Java

num = network.getOrDefault(n1, 1) + network.getOrDefault(n2, 1);

초기 코드

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.security.Provider;
import java.util.*;

public class Main {
    public static int N, F;
    public static HashMap<String, Integer> network;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        network = new HashMap<>();
        for (int i = 0; i < N; i++) {
            F = Integer.parseInt(br.readLine());
            network.clear();
            for (int j = 0; j < F; j++) {
                String n1, n2;
                int num;
                st = new StringTokenizer(br.readLine());
                n1 = st.nextToken();
                n2 = st.nextToken();
                num = network.getOrDefault(n1, 1) + network.getOrDefault(n2, 1);
                network.put(n1, num);
                network.put(n2, num);
                System.out.println(num);
            }
        }
    }
}

하지만 38%에서 틀렸다 가 떴다.

이유를 알아봤더니

만약 입력이 아래와 같이 주어졌다면

Java

a b
b c
a c

위의 코드에서는 2, 3, 5 를 출력하게 된다.

실제 결과는 2, 3, 3 이 나와야 한다.

위 코드에서는 실제로 친구 관계에 속해있는 것을 구분하지 못하는 것이다.

이걸 해결하기 위해 나는 다시 Union - Find 를 꺼내게 되었다.

하지만 이번에는 일반 Union - Find 와 달리 배열로 구현을 할 수가 없어서 위의 코드와 같이 해시맵을 사용했는데, 그렇게 하면 친구 수를 저장할 방법이 없어서 아래와 같이 새로운 해시맵을 또 만들었다.

Java

public static HashMap<String, String> network; //Union-find를 위한 해시맵
public static HashMap<String, Integer> friendNum; //친구 수 검색을 위한 해시맵

결과 코드

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int N, F;
    public static HashMap<String, String> network;
    public static HashMap<String, Integer> friendNum;

    public static String find(String name) {
        if (!network.get(name).equals(name)) { //부모 이름과 자신의 이름이 같지 않으면
            network.put(name, find(network.get(name))); //부모 찾아서 업데이트
        }
        return network.get(name); //부모 리턴하기
    }

    public static void union(String n1, String n2) { //새로운 친구 관계 맺기
        String p1 = find(n1); //두 부모 찾기
        String p2 = find(n2);
        int num1 = friendNum.get(p1);
        int num2 = friendNum.get(p2);
        if (!p1.equals(p2)) {
            network.put(p2, p1);
            friendNum.put(p1, num1 + num2); //부모의 친구 수 업데이트
        }
    }

    public static int getFriendNum(String name) {
        String parent = find(name); //부모 찾기
        return friendNum.get(parent); //부모를 기준으로 친구 수 가져오기
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuffer sb = new StringBuffer();
        N = Integer.parseInt(br.readLine());
        network = new HashMap<>();
        friendNum = new HashMap<>();
        for (int i = 0; i < N; i++) {
            F = Integer.parseInt(br.readLine());
            network.clear();
            friendNum.clear();

            for (int j = 0; j < F; j++) {
                String n1, n2;
                st = new StringTokenizer(br.readLine());
                n1 = st.nextToken();
                n2 = st.nextToken();

                if (!network.containsKey(n1)) { //해당 이름이 처음 나왔다면 초기 세팅
                    network.put(n1, n1); //부모 자신으로
                    friendNum.put(n1, 1); //친구 수 1
                }

                if (!network.containsKey(n2)) { //해당 이름이 처음 나왔다면 초기 세팅
                    network.put(n2, n2); //부모 자신으로
                    friendNum.put(n2, 1); //친구 수 1
                }

                String p1 = find(n1);
                String p2 = find(n2);

                if (!p1.equals(p2)) { //두 부모가 일치하지 않으면 새로운 친구관계 맺기
                    union(n1, n2);
                }
                sb.append(getFriendNum(n1)).append("\n");
            }
        }
        System.out.println(sb);
    }
}