[ 알고리즘 / kotlin ] 백준 2606 Virus

안녕하세요 gyub(귭)입니다 ㅎㅎㅎ
요즘 자소서 쓰고 앱 공부를 하느라 블로그 업데이트를 소홀히 해버렸네요 ㅠㅠ

아무튼 이번엔 백준 알고리즘 2602번 Virus 문제입니다.

우선 저는 DFS로 풀었어요! BFS로 푸신 분들도 보이는데 전 그냥 DFS로 했어요 암튼 그냥 DFS요 ㅎ..

 

https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

전체 코드부터 보여드리겠습니다.

// DFS 사용

// 연결된 컴퓨터의 쌍
private lateinit var myGraph: Array<IntArray>
// 방문 여부 확인
private lateinit var myVisited: BooleanArray

// 바이러스 걸린 컴 개수
private var virus: Int = 0

fun main() {

    // 총 컴퓨터 개수
    val com = readLine()!!.toInt()
    // 연결되어 있는 컴퓨터 쌍의 수
    val link = readLine()!!.toInt()

    myGraph = Array(com + 1) { IntArray(com + 1) }
    myVisited = BooleanArray(com + 1)

    for (i in 0 until link) {
        val (n, m) = readLine()!!.split(' ').map(String::toInt)
        myGraph[n][m] = 1
        myGraph[m][n] = 1
    }
    dfs(1)

    print(virus)
}

private fun dfs(n: Int) {
    // 1번 컴퓨터를 제외
    if (n != 1)
        virus++

    myVisited[n] = true
    for (i in 1 until myGraph.lastIndex + 1) {
        if (!myVisited[i] && myGraph[n][i] == 1) {
            dfs(i)
        }
    }

}

이제 세부적인(?) 설명을 해보겠슴다

 

 myGraph = Array(com + 1) { IntArray(com + 1) }
    myVisited = BooleanArray(com + 1)

    for (i in 0 until link) {
        val (n, m) = readLine()!!.split(' ').map(String::toInt)
        myGraph[n][m] = 1
        myGraph[m][n] = 1
    }

리스트의 개수에 +1을 한 것은 각 리스트의 인덱스를 사용할껀데 문제를 보시다시피

컴퓨터가 1부터 시작하기에 편의를 위해 리스트의 개수를 하나 늘려줬습니다.

 

연결되는 컴퓨터의 번호를 입력받고

myGraph리스트에 1을 넣어줌으로써 연결이 됐다고 표시합니다.

 

private fun dfs(n: Int) {
    // 1번 컴퓨터를 제외
    if (n != 1)
        virus++

    myVisited[n] = true
    for (i in 1 until myGraph.lastIndex + 1) {
        if (!myVisited[i] && myGraph[n][i] == 1) {
            dfs(i)
        }
    }

}

DFS 재귀호출 코드입니다.

1번 컴퓨터를 제외한 감염된 컴퓨터의 개수를 물어보는 문제이므로 1번 컴퓨터는 제외해줍시다!

봐주셔서 감사합니다!
질문이나 수정되어야 할 부분이 있다면 댓글로 남겨주세요!