(BOJ) 1325 효율적인 해킹

1325 효율적인 해킹

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

문제

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

이 회사는 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

Solution

Exapnder

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

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