[2023-05-05] 1325 효율적인 해킹 (Kotlin) + 5문제

 

문제 링크 : https://www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

 

문제를 보자마자 BFS 유형이라 판단을 했습니다.

 

 

첫 번째 시도 (시간 초과)

 

package thirtyfifth
import java.io.*
import java.util.*
import kotlin.collections.ArrayList

fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))
    val (n,m) = br.readLine().split(' ').map{it.toInt()}
    
    // 인덱스마다 신뢰하는 컴퓨터를 저장
    // ex) 3 -> 4,5
    val map = Array(n+1){arrayListOf<Int>()}
    
    repeat(m){
        val token = StringTokenizer(br.readLine())
        val a = token.nextToken().toInt()
        val b = token.nextToken().toInt()
        map[b].add(a)
    }
    
    // 1 ~ n 별로 해킹 가능한 횟수를 저장할 배열
    val countArr = Array(n+1){0}
    
    // 최대 횟수를 저장할 변수
    var maxCount = 0
	
    // 1 ~ n까지 반복
    for (index in 1..n){
		
        // 방문 배열
        val visit = Array(n+1){false}


        val queue = LinkedList<Int>()

        queue.add(index)
        var count = 0
		
        while (queue.isNotEmpty()){
            val first = queue.poll()
            
            // queue내의 원소가 처음 등장하는 원소라면
            if (!visit[first]){
                visit[first] = true
                // count 1 증가
                count += 1
                // 해당 번호의 컴퓨터와 연결된 컴퓨터들  queue에 추가
                map[first].forEach{queue.add(it)}
            }
        }
        // 최대값 설정, 해당 index의 해킹 가능 횟수 저장
        maxCount = Math.max(count, maxCount)
        countArr[index] = count

    }
    
    // 최대값에 해당하는 컴퓨터 번호 출력
    for (index in countArr.indices){
        if (countArr[index] == maxCount)
            bw.write("$index ")
    }
    bw.flush()
}

 

 

시간 복잡도를 줄이려 시도하다 실패하여 다른 분의 풀이를 봤습니다.

 

논리가 완전히 같았고, 풀이가 다른 곳이 한 구간이 있었습니다.

 

 

 

두 번째 시도 (맞았습니다.)

 

package thirtyfifth
import java.io.*
import java.util.*
import kotlin.collections.ArrayList

fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.`out`))
    val (n,m) = br.readLine().split(' ').map{it.toInt()}
    
    // 인덱스마다 신뢰하는 컴퓨터를 저장
    // ex) 3 -> 4,5
    val map = Array(n+1){arrayListOf<Int>()}
    
    repeat(m){
        val token = StringTokenizer(br.readLine())
        val a = token.nextToken().toInt()
        val b = token.nextToken().toInt()
        map[b].add(a)
    }
    
    // 1 ~ n 별로 해킹 가능한 횟수를 저장할 배열
    val countArr = Array(n+1){0}
    
    // 최대 횟수를 저장할 변수
    var maxCount = 0
	
    // 1 ~ n까지 반복
    for (index in 1..n){
		
        // 방문 배열
        val visit = Array(n+1){false}
        visit[index] = true

        val queue = LinkedList<Int>()

        queue.add(index)
        var count = 0
		
        while (queue.isNotEmpty()){
            val first = queue.poll()
            
            // 이 부분이 다릅니다.
                map[first].forEach{
                if (!visit[it]){
                    visit[it] = true
                    queue.add(it)
                    count+=1
                }
            }
        }
        // 최대값 설정, 해당 index의 해킹 가능 횟수 저장
        maxCount = Math.max(count, maxCount)
        countArr[index] = count

    }
    
    // 최대값에 해당하는 컴퓨터 번호 출력
    for (index in countArr.indices){
        if (countArr[index] == maxCount)
            bw.write("$index ")
    }
    bw.flush()
}

 

 

 

첫 번째 코드는 현재의 컴퓨터의 방문 여부를 확인한 후, 방문 처리를 하며

연결된 컴퓨터들을 일괄적으로 추가합니다.

 

이 경우, 이미 방문한 노드가 큐에 추가될 수 있기 때문에 시간 복잡도가 증가합니다.

 

 

 

 

두 번째 코드는 컴퓨터를 방문할 때마다 방문 처리를 하고 큐에 추가하기 때문에,

 

불필요한 컴퓨터를 큐에 추가하지 않으므로 더 효율적입니다.