[백준] 1325 - 효율적인 해킹

[문제링크]

1325번: 효율적인 해킹

 

0. 방향 그래프에서, 가장 많은 노드를 방문할 수 있는 노드 찾기

 

1. 정점 N에 비해 간선 M의 범위가 작으므로, 그래프의 저장은 List로 한다

 

2. 모든 정점에 대해 BFS로 방문 가능한 노드 갯수를 탐색, 저장한다

 

3. 최댓값을 가지는 정점들을 출력한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		int[] result = new int[n];
		int max=0;
		List<List<Integer>> graph = new ArrayList<>();
		
		for (int i = 0; i < n; i++)graph.add(new ArrayList<>());
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int a = pint(st.nextToken())-1;
			int b = pint(st.nextToken())-1;
			graph.get(b).add(a);
		}
		
		for (int i = 0; i < n; i++) {
			//각각 서치 돌려보고, 결과값 추리기
			int cnt=0;
			
			Queue<Integer>qu = new LinkedList<Integer>();
			qu.offer(i);
			boolean[] isV=new boolean[n];
			isV[i]=true;
			while(!qu.isEmpty()) {
				int cur = qu.poll();
				cnt++;
				for (int next : graph.get(cur)) {
					if(!isV[next]) {
						isV[next]=true;
						qu.offer(next);
					}
				}
			}
			result[i]=cnt;
			if(max<cnt)max=cnt;
		}
		for(int i=0; i<n; i++) {
			if(result[i]==max)sb.append(i+1).append(" ");
		}sb.setLength(sb.length()-1);
		System.out.println(sb);
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면