codingtest

4195번 - 친구 네트워크

2024-07-09
3분 분량
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);
    }
}

함께 읽으면 좋은 글

코딩 테스트2026-04-02

5430번 - AC

함수 R은 배열을 뒤집는 연산 함수 D는 첫 번째 원소를 버리는 연산 단, 배열이 비어 있을 때 D를 수행하면 error 주어진 함수 문자열을 순서대로 수행한 뒤 최종 배열을 출력하는 문제 처음에는 문제 설명 그대로 R이 나올 때마다 배열을 실제로 뒤집고, D가 나오면 맨 앞…

코딩 테스트2026-04-02

1966번 - 프린터 큐

여러 문서가 큐에 들어 있고, 각 문서마다 중요도가 있음 맨 앞 문서를 확인했을 때, 더 높은 중요도의 문서가 뒤에 하나라도 있으면 맨 뒤로 보냄 그렇지 않으면 바로 인쇄 특정 위치의 문서가 몇 번째로 인쇄되는지 구하는 문제 이 문제는 프린터의 동작을 그대로 구현하면 되는…

코딩 테스트2026-03-29

1158 - 요세푸스 문제

1번부터 N번까지 사람이 원형으로 앉아 있음 순서대로 K번째 사람을 제거 모든 사람이 제거될 때까지 반복 제거되는 순서를 출력하는 문제 이 문제는 원형으로 순회하면서 K번째를 제거하는 과정을 그대로 구현하면 된다.

코딩 테스트2026-03-29

2164번 - 카드2

1부터 N까지 카드가 순서대로 쌓여 있음 맨 위 카드를 버리고, 그다음 맨 위 카드를 맨 아래로 옮기는 과정을 반복 마지막에 남는 카드 번호를 구하는 문제 이 문제는 규칙을 찾기보다, 문제에서 하라는 과정을 그대로 구현하면 된다. 카드 더미에서 반복되는 동작은 두 가지다.

← 서재 목록으로 돌아가기