[Baekjoon] 1325번 : 효율적인 해킹

1. 문제

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

• DFS, BFS 문제

// 문제
해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다.
이 회사는 N개의 컴퓨터로 이루어져 있다.
김지민은 귀찮기 때문에,
한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와,
신뢰하지 않는 관계로 이루어져 있는데,
A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때,
한 번에 가장 많은 컴퓨터를 해킹할 수 있는
컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

// 입력
첫째 줄에, N과 M이 들어온다.
N은 10,000보다 작거나 같은 자연수,
M은 100,000보다 작거나 같은 자연수이다.
둘째 줄부터 M개의 줄에 신뢰하는 관계가
A B와 같은 형식으로 들어오며,
"A가 B를 신뢰한다"를 의미한다.
컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

// 출력
첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

// 예제 입력 1
5 4
3 1
3 2
4 3
5 3

// 예제 출력 1
1 2

2. 핵심 아이디어

• 모든 정점에 대하여 DFS 및 BFS 수행
• DFS 혹은 BFS를 수행할 때마다 방문하게 되는 노드의 개수를 계산
• 노드의 개수가 가장 크게 되는 시작 정점을 출력

3. Python 문제풀이

import sys
from collections import deque
input = sys.stdin.readline

def bfs(v) :
  q = deque([v])
  visited = [False] * (n + 1)
  visited[v] = True
  count = 1
  while q :
    v = q.popleft()
    for e in adj[v] :
      if not visited[e] :
        q.append(e)
        visited[e] = True
        count += 1
  return count

n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]

for _ in range(m) :
  x, y = map(int, input().split())
  adj[y].append(x)

result = []
max_value = -1

for i in range(1, n + 1) :
  c = bfs(i)
  if c > max_value :
    result = [i]
    max_value = c
  elif c == max_value :
    result.append(i)
    max_value = c

for e in result :
  print(e, end = ' ')

4. Java 문제풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Main {
	static int n;
	static int[] visited;
	static List<Integer>[] adj;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		adj = new ArrayList[n+1];
		visited = new int[n+1];
		for(int i=1; i<n+1; i++) {
			adj[i] = new ArrayList<>();
		}
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			adj[x].add(y);
		}

		int max_value = Integer.MIN_VALUE;
		for(int i=1; i<n+1; i++) {
			bfs(i);
		}

		for(int i=1; i<n+1; i++) {
			max_value = Math.max(visited[i], max_value);
		}

		for(int i=1; i<n+1; i++) {
			if(max_value == visited[i]) {
				bw.write(i+" ");
			}
		}
		bw.flush();
		bw.close();
	}

	static void bfs(int start) {
		Queue<Integer> q = new LinkedList<>();
		boolean[] check = new boolean[n+1];
		q.add(start);
		check[start] = true;
		while(!q.isEmpty()) {
			int pos = q.poll();
			for(int next : adj[pos]) {
				if(!check[next]) {
					check[next] = true;
					visited[next]++;
					q.add(next);
				}
			}
		}
	}
}