(BOJ) 1325 효율적인 해킹

1325 효율적인 해킹

  • 분류 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

문제

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다.

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

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

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

입력

첫째 줄에, N과 M이 들어온다.

N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다.

둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, “A가 B를 신뢰한다”를 의미한다.

컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

출력

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

예제 입력 1

1
2
3
4
5
5 4
3 1
3 2
4 3
5 3

예제 출력 1

1
1 2

Solution

Exapnder
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import java.util.*

private var N: Int = 0
private var M: Int = 0

private lateinit var graph: Array<MutableList<Int>>
private lateinit var visited: BooleanArray
private lateinit var answer: IntArray

fun main() {
input()
solve()
}

private fun input() = with(Scanner(System.`in`)) {
N = nextInt() // N개의 컴퓨터
M = nextInt() // M개의 줄에 신뢰하는 관계
init()
repeat(M) {
val A = nextInt()
val B = nextInt()
graph[A].add(B)
}
}

private fun init() {
graph = Array(N + 1) {
mutableListOf()
}
answer = IntArray(N + 1) { 0 }
}

private fun solve() {
for (i in 1 .. N) {
visited = BooleanArray(N + 1) { false }
bfs(i)
}

var max = Int.MIN_VALUE
for (i in 1 .. N) {
max = Math.max(max, answer[i])
}

for (i in 1 .. N) {
if (max == answer[i]) {
print("$i ")
}
}
println()
}

private fun bfs(_node: Int) {
var node = _node
val queue = LinkedList<Int>()
queue.add(node)
visited[node] = true
while (queue.isNotEmpty()) {
node = queue.remove()
graph[node].forEach {
if (!visited[it]) {
answer[it]++
visited[it] = true
queue.add(it)
}
}
}
}

Point of Thinking

  • 전형적인 그래프 이론 문제이다.
  • BFS / DFS 두 기법으로 모두 풀 수 있다.
  • 다만 모든 노드를 순회하면 타임아웃이 될 확률이 높으므로 방문자 배열을 통해 노드 접근 수를 최대한 줄여야 한다.

References