[Kotlin, Lv.3] 프로그래머스 네트워크

출처: unsplash.com

 

네트워크

Level 3

https://school.programmers.co.kr/learn/courses/30/lessons/43162

 

문제 내용

 

 

문제 접근

각 컴퓨터 간 네트워크가 형성되어 있으면 1이고 아니면 0으로 입력된다.

n의 값만큼의 길이를 가지는 n * n의 2차원 배열이 입력으로 주어진다.

배열의 첫 번째 index가 각 컴퓨터에 대한 다른 컴퓨터와의 연결 상태를 볼 수 있다.

 

입력 예시 1에서 [[1, 1, 0], [1, 1, 1], [0, 1, 1]]가 입력값인데, 위 리스트의 첫 번째 값인 [1, 1, 0]은 0번째 컴퓨터에 연결되어 있는 컴퓨터들을 뜻한다.

0번째 index의 값인 1은 0번 컴퓨터 자기 자신이기 때문에 무조건 1이 들어온다. 다음 값인 index 1의 값이 1인데 이 뜻은 1번 컴퓨터와 연결되어 있다는 뜻이다.

나머지 배열들도 각각의 컴퓨터의 연결되어 있는 컴퓨터들을 확인할 수 있다.

 

입력 예제 1을 그림으로 나타내면 다음과 같다.

사진 1-1

3번은 자기 자신을 제외하고 누구와도 연결되어 있지 않아서 따로 독립된 네트워크를 가지고, 1번과 2번은 서로 연결되어 있기 때문에 두 컴퓨터끼리 하나의 네트워크를 형성해서 정답은 2다.

 

 

문제 해결 코드

private var visited = booleanArrayOf()
private var graph = arrayOf<IntArray>()
private var answer = 0

fun solution(n: Int, computers: Array<IntArray>): Int {
    graph = computers
    visited = BooleanArray(n)

    for (i in graph.indices) {
        if (!visited[i]) {
            answer++
            dfs(i)
        }
    }

    return answer
}

private fun dfs(num: Int) {
    visited[num] = true
    val data = graph[num]

    for (n in data.indices) {
        if (!visited[n] && data[n] == 1) {
            visited[n] = true
            dfs(n)
        }
    }
}

 

문제 풀이

computers를 함수 안에서 쓰기 위해 graph를 생성하고, 컴퓨터를 지나왔음을 확인하는 변수 visited를 생성한다.

visited가 여러 번 컴퓨터에 접근하는 것을 막아줄 것이다.

answer는 네트워크의 개수이다.

 

컴퓨터의 대수만큼 반복해야 한다. 그리고 visited[i]가 false여야 한 번도 방문하지 않은 컴퓨터이기 때문에 dfs 함수를 실행할 수 있다.

dfs 함수에서는 들어온 값을 방문하고 내부 리스트에서 1이면서 아직 방문하지 않은 값이 있으면 재귀로 다시 들어가는 구조이다. dfs가 끝나고 나서 연결되지 않은 컴퓨터는 visited가 false 상태일 텐데, 반복문으로 모두 잡아내기 때문에 새로운 네트워크가 있다고 판단할 수 있다.

 

예시 1의 경우에는 컴퓨터 1, 2는 연결되어 있고 3은 연결되어 있지 않은데, dfs를 호출하면서 1, 2를 순회하고 dfs가 끝나는데, 이를 solution의 반복문에서 visited가 false인 3을 타깃으로 다시 dfs를 호출하는 것이다. 이러면 dfs가 새로 호출될 때마다 새로운 네트워크가 있다는 것을 알 수 있기 때문에 answer를 늘려 준다.

solution의 반복이 끝나고 최종 answer가 정답이다.

 

 

문제 해결 과정

입력받는 그래프 구조가 백준 그래프와는 달랐다.

백준의 경우는 내가 생각하고 구상해야 하지만, 프로그래머스는 그래프가 통으로 주어졌다.

그래프를 파악하는 데 오랜 시간이 걸리지는 않았지만, 어색했던 건 사실이다.