[백준][Kotlin]효율적으로 해킹하기

해당 문제는 백준에서 풀었던 문제 중에서 가장 많은 시간 초과를 많이 보게 된 문제였습니다.

처음에는 BFS를 이용하여 작성하였었으나 시간 초과가 지속적으로 발생하여, 질문 게시판을 확인해 보니

코드를 잘못 작성하지 않았을 경우 선언문 및 변수 등을 줄여야 한다는 것을 알게 되었습니다. 저는 보통 작성을 하면

visit 와 문제 따른 가중치 등을 별도로 저장하기에 발생한 문제였습니다.

그래서 visit만을 이용하여 제 실력 내에서 최대한 적게 선언하여 해당 문제를 DFS및 BFS로 작성해보았습니다.

하기는 작성한 코드와 제출 결과 입니다.

 

DFS로 작성한 코드 및 제출 결과

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
import kotlin.collections.ArrayList


var N = 0
var M = 0
lateinit var loadList : Array<ArrayList<Int>>
lateinit var visit : IntArray
lateinit var count : IntArray

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt()
    M = st.nextToken().toInt()

    loadList = Array(N+1){ArrayList<Int>() }

    repeat(M){
        st = StringTokenizer(br.readLine())
        var service = st.nextToken().toInt() // 해킹하면
        var hacking = st.nextToken().toInt() // 추가 가능
        loadList[hacking].add(service)
    }

    count = IntArray(N+1){0}
    for(i in 1 .. loadList.size-1){
        visit = IntArray(N+1){0}
        visit[i] = 1
        dfs(i)
        count[i] = visit.sum()
    }

    var max = count.maxOrNull()!!

    for(i in 1 .. count.size-1){
        if(count[i] == max) bw.append("$i ")
    }
    
    bw.flush()
    bw.close()

}

fun dfs(i: Int){
    for(j in 0 .. loadList[i].size-1){
        if(visit[loadList[i][j]] == 0){
            visit[loadList[i][j]] = 1
            dfs(loadList[i][j])
        }
    }
}

 

BFS를 사용하여 작성한 코드 및 제출 결과

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
import kotlin.collections.ArrayList

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    var bw = BufferedWriter(OutputStreamWriter(System.out))
    var st = StringTokenizer(br.readLine())
    var N = st.nextToken().toInt()
    var M = st.nextToken().toInt()

    var loadList = Array(N+1){ArrayList<Int>() }

    repeat(M){
        st = StringTokenizer(br.readLine())
        var service = st.nextToken().toInt() // 추가 가능
        var hacking = st.nextToken().toInt() // 해킹하면
        loadList[hacking].add(service)
    }

    var count = IntArray(N+1){0}
    for(i in 1 .. loadList.size-1){
        var visit = IntArray(N+1){0}
        visit[i] = 1
        var dq = ArrayDeque<Int>()
        dq.add(i)
        while(!dq.isEmpty()){
            val now = dq.poll()
            for(j in 0 .. loadList[now].size-1){
                if(visit[loadList[now][j]] == 0){
                    visit[loadList[now][j]] = 1
                    dq.addLast(loadList[now][j])
                    count[i]++
                }
            }
        }
    }

    var max = count.maxOrNull()!!

    for(i in 1 .. count.size-1){
        if(count[i] == max) bw.append("$i ")
    }

    bw.flush()
    bw.close()

}