[2023-05-09] 24479 알고리즘 수업 - 깊이 우선 탐색 1 (Kotlin) + 7문제

 

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

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

 

첫 번째 시도 (틀렸습니다.)

 

package thirtynineth
import java.io.*
import java.util.*

fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (n, m, r) = br.readLine().split(' ').map{it.toInt()}
    
    // 넣자마자 오름차순으로 정렬되게 하기 위해
	// priroityqueue로 선언하기
    
    val mp = Array(n+1){PriorityQueue<Int>()}
    repeat(m){
        val (u,v) = br.readLine().split(' ').map{it.toInt()}
        mp[u].add(v)
        mp[v].add(u)
    }
	
    // 각 노드별 방문한 순서를 저장할 배열
    //ex) visit[1]=1,  visit[2] = 2, visit[3] = 3
    val visit = Array(n+1){0}
    var count = 1
    
    fun dfs(start: Int){
        visit[start] = count
        for (child in mp[start]){
            if (visit[child] == 0){
                count++
                dfs( child)
            }
        }
    }
    dfs(r)
    for (index in 1..n){
        println(visit[index])
    }


}

 

시간초과를 해결할 방법이 보이지 않아, 다른 분의 코드를 참고하였습니다.

 

저 PriorityQueue 자료구조를 사용하는 부분을 제외하고, 모든 부분이 똑같았습니다.

 

다음과 같이 코드를 수정하였습니다.

 

 

 

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

 

package thirtynineth
import java.io.*
import java.util.*

fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (n, m, r) = br.readLine().split(' ').map{it.toInt()}
    // 그냥 arrayList로 선언
    val mp = Array(n+1){arrayListOf<Int>()}
    repeat(m){
        val (u,v) = br.readLine().split(' ').map{it.toInt()}
        mp[u].add(v)
        mp[v].add(u)
    }
	
    // arrayList를 오름차순으로 정렬
    for (index in mp.indices){
        mp[index].sort()
    }


    val visit = Array(n+1){0}
    var count = 1
    fun dfs(start: Int){
        visit[start] = count
        for (child in mp[start]){
            if (visit[child] == 0){
                count++
                dfs( child)
            }
        }
    }
    dfs(r)
    for (index in 1..n){
        println(visit[index])
    }


}

 

 

왜 첫 번째 시도가 틀렸는지 원인을 모르겠습니다.

 

알게 되면 다시 정리해 보도록 하겠습니다.