[JAVA] 백준 5107번: 마니또

https://www.acmicpc.net/problem/5107

5107번: 마니또

✅ 실버Ⅰ

 

🔶 풀이

A에서 출발해서 B, C, ··· 를 지나서 다시 A로 돌아오는 경우가 몇 개나 발생하는가.

 

1️⃣ 선행을 베푸는 사람과 선행을 받는 사람은 결코 중복되지 않는다.

2️⃣ 이름의 길이는 10글자가 넘지 않고 테스트 케이스마다 사람은 3명에서 20명이다.

 

해당 문제에서는 딱히 신경써야할 조건은 없다.

1️⃣번 조건을 봤을 때 HashMap을 사용하면 될 것 같다고 생각했다.

 

HashMap으로 마니또 목록을 입력해주고, ArrayList 배열로 참여한 사람들의 이름을 저장해줬다.

ArrayList 배열을 다 돌면서 마니또 체인을 찾아주면 된다.

 

찾는 과정에서 마니또 체인을 발견했다면 해당 마니또 목록은 제거한다.

또한, 제거를 했기 때문에 추후에 발생하는 NullPointerException을 방지하기위해 조건문으로 처리해줬다.

 

 

<최종코드>

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        boolean flag = true;
        int level = 1;
		
        while (true) {
            int N = Integer.parseInt(br.readLine());
            int cnt = 0;
			
            // 0을 입력하면 종료
            if (N == 0) return;
			
            ArrayList<String> person = new ArrayList<>(); // 참여한 사람 이름
            HashMap<String, String> hm = new HashMap<>(); // 마니또 목록
						
            for (int i=0; i<N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
				
                String from = st.nextToken();
                String to = st.nextToken();
				
                hm.put(from, to);
                person.add(from);
            }
			
            for (String from : person) {
                String to = hm.get(from);
				
                while (true) {
                    to = hm.get(to);
					
                    // 이미 방문했을 경우 remove 처리를 했기 때문에 값이 null
                    // NullPointerException 에러 방지
                    if (to == null) {
                        break;
                    } else if (to.equals(from)) {
                        hm.remove(to);
						
                        cnt++;
                        break;
                    }
                }
            }
			
            System.out.println(level + " " + cnt);
            level++;
        }
    }
}