[백준] 5107번 '마니또' - Java

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

5107번: 마니또

---

문제

---

코드

맞았습니다가 뜬 코드입니다. - 메모리 16080KB | 시간 148ms | 코드 길이 1517B

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

public class Main {
	private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	private static boolean[] visited;
	private static int cnt;
	
	public static void main(String[] args) throws IOException {
		int t = 0;
		while(true) {
			int n = Integer.parseInt(bf.readLine());
			if(n == 0) {
				break;
			} else {
				t ++;
				cnt = 0;
				int[][] node = new int[n][n];
				ArrayList<String> name = new ArrayList<>();
				
				for(int i = 0 ; i < n ; i++) {
					StringTokenizer st = new StringTokenizer(bf.readLine());
					String x = st.nextToken();
					String y = st.nextToken();
					if(!name.contains(x)) name.add(x);
					if(!name.contains(y)) name.add(y);
					
					node[name.indexOf(x)][name.indexOf(y)] = 1;
				}
				
				PriorityQueue<Integer> graph = new PriorityQueue<>();
				visited = new boolean[n];
				for(int i = 0 ; i < n ; i++) {
					if(!visited[i]) {
						bfs(graph, node, i);
					}
				}
				
				bw.write(Integer.toString(t) + " " + Integer.toString(cnt) + "\n");
			}
		}
		
		bf.close();
		bw.flush();
		bw.close();
	}
	
	private static void bfs(PriorityQueue<Integer> graph, int[][] node, int n) {
		visited[n] = true;
		graph.poll();
		for(int i = 0 ; i < node.length ; i++) {
			if(node[n][i] == 1) {
				if(!visited[i]) {
					graph.add(i);
					bfs(graph, node, i);					
				} else cnt ++;
			}
		}
	}
}

 

문제와 출력이 무슨 말인지 몰라서 약간 헤맸습니다 ;;

0은 n에 대한 입력이라 테스트 케이스가 몇 번째인지에 대한 t, 사이클 개수를 알아내면 되는 문제였습니다.

 

입력받은 이름을 숫자형태로 바꾸어 bfs로 푸는 방식으로 하였습니다.

 

자바의 HashMap을 써보고 싶어서 푼 문제인데 해시맵으로 푸는게 오히려 더 비효율적일 것 같아서 그냥 배열로 했습니다. 해시맵 쓰는 건 다른 문제로 다시 도전해봐야겠네요. 해시맵이라기 보다는 그냥 탐색 문제였던듯..