[BOJ] 마니또

문제

N명의 사람들이 있다. 이들은 각자 다른 한 명의 이름이 적힌 쪽지를 받아서, 그 사람에게 몰래 선행을 베푼다.

이때 자기 자신의 이름을 받을 수는 없으며, 선행을 받은 사람은 누가 자신을 도와줬는지도 알 수 없다.

그런데 이런 마니또 활동을 하던 중 할 짓이 지지리도 없던 세종이는 여기서 "마니또 체인"이라는 개념을 발견했다!

세종이가 동우에게 선행을 베풀고, 동우가 재혁이에게 선행을 베풀고, 재혁이가 호용이에게 선행을 베풀고...
이렇게 하다 보면 언젠가 누군가는 처음 선행을 베푼 세종이에게 선행을 베풀게 되리라는 것이다.

이렇게 선행을 베푸는 연결 고리가 반드시 생긴다! 이 고리는 그냥 2명일 수도 있고, 아예 N명 모두가 포함될 수도 있다.

우리가 할 일은 N명의 사람들 사이에서 이러한 연결 고리가 몇 개나 발생하는지를 알아내는 것이다. 문제는 여러 개로 이루어져 있다.

풀이

환형을 이루는 경우를 찾아서 그 갯수를 세면 된다.
map에 key와 value에 대한 정보를 담고, 이를 반복해서 찾도록 하였다.
찾은 이후에는 찾은 정보를 key에서 제거해주어야 한다.
그래야 중복되어서 찾는 순번을 제거할 수 있기 때문이다.
따라서 이를 list에 담아서 제거해주도록 하였다.
참고로 keySet으로 반복해서 돌면 키 제거시 오류가 발생하게 되므로 key정보를 담는 배열을 생성해서 이를 돌게 하였다.

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int caseNum = 1;
        while(true) {
            int N = Integer.parseInt(br.readLine());
            int count = 0;
            if (N == 0) {
                break;
            }

            Map<String, String> map = new HashMap<>();
            String[] keyArr = new String[N];
            for(int i = 0; i < N; i++) {
                String[] str = br.readLine().split(" ");
                map.put(str[0], str[1]);
                keyArr[i] = str[0];
            }

            for(String st : keyArr) {            
                List<String> keyList = new ArrayList<>();
                String value = map.get(st);
                keyList.add(st);
                while(true) {
                    keyList.add(value);
                    value = map.get(value);
                    if (value == null) {
                        break;
                    }

                    if (value.equals(st)) {
                        count++;
                        for(String key : keyList) {
                            map.remove(key);
                        }
                        break;
                    }

                }
            }

            System.out.println(caseNum + " " + count);
            caseNum++;
        }
    }
}

https://github.com/Win-9/Algorism/tree/main/BOJ/%EB%A7%88%EB%8B%88%EB%98%90