[Java] 백준 26069번: 붙임성 좋은 총총이

hansung's·2024년 3월 25일

문제 url:
붙임성 좋은 총총이

문제:

🤔 문제 알아보기

일단, 문제를 잘못 이해하면 문제가 안풀린다.
필자도 문제를 잘못 이해한 상태로 푸니깐(tc는 맞췄지만, 잘못 이해해 틀렸다.) 약간 미궁속으로 빠지는 문제이다.

문제는 다음과 같다.
먼저, ChongChong을 만난 사람은 반드시 춤을 추게 되어 있다.
즉, tc에서 A ChongChong or B ChongChong 이런식으로 입력되었을 때, A와 B는 춤을 추게 되는 것이다.

그런 다음 C A or A C || C B or B C 가 나왔다면, C 역시 춤을 추게 될 것이다.
왜? A와 B는 ChongChong한테 총총춤이 감염되었기 때문이다.

하지만, 필자도 그렇고 아마 해당 문제를 틀린분들은 대게 이 반례를 해결하지 못했을 것인데,
바로 ChongChong ChongChong -> B C or ChongChong A -> B C
총총 또는 총총으로 감염된 인원이 다른 인원을 감염시키지 못한 상황이라면, 여기서 B C는 어느 누구하나 총총춤에 감염되지 않은 사람이다.

그래서 해당 반례에 대해서 고려해줄 필요가 있는 것이다.
이제 코드와 함께 문제를 알아보면 이해가 더욱 쉽다.

🐱‍👤 실제코드

import java.io.*;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        Set<String> set = new HashSet<>();

        //총총은 춤을 추는 친구이기 때문에
        //추후, 해당 친구를 이용해 문제를 푼다.
        set.add("ChongChong");

        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            String A = st.nextToken();
            String B = st.nextToken();

            /*
             * 집합 자료구조에 현재 A나 B가 들어가 있다면
             * A또는 B는 춤을 추게 될 것이기 때문
             * 또는 ChongChong을 보게 될 것이기 때문.
             */
            if(set.contains(A) || set.contains(B)) {
                set.add(A);
                set.add(B);
            }

        }

        System.out.println(set.size());


    }
}