[Programmers] 네트워크

문제

Level 3 문제이다.

 

문제 이해하기

 

여타 다른 문제와 입력값이 좀 다른데

다른 문제는 보통 graph matrix를 제시하고 1,0으로 vertex가 존재하는지 존재하지 않는지를 표현한다면

이 문제는 adjacecy matrix를 아예 입력값으로 제시한다.

때문에 다음과 같이 해석했다.

행번호와 열번호가 같은 위치 원소는 모두 1일 수 밖에 없다. 자기 자신과는 연결된 상태로 보기 때문이다.

 

(i,j) == (j,i)로 양방향 연결그래프 라는 사실도 한눈에 알 수 있어야한다,

 

(0)번 노드 기준

0번 노드를 기준으로 1번과 3번에 연결되어있다.

(1)번 노드 기준

1번 노드 기준으로 0번 (이미 연결했었음) 과 3번과 연결되어있다.

(2)번 노드는 아무런 노드와도 연결되지 않았다. (2번 행 또는 열에서 자기 자신을 제외한 모든 원소 0)

(3)번 노드 기준

3번 노드 기준으로 0, 1은 이미 앞에서 연결했다.

인접 행렬을 해석하고 나면 이런 그림이 그려진다.

 

따라서 위와 같은  4*4 인접 행렬이 주어졌을때 return 값 (그래프 수)는 2가된다.

---

해결 방법

방문 여부를 keep하는 visited[]행렬 대신

BFS로 방문하며 방문했던 노드의 자리를 0값으로 대치하여 모든 행렬의 원소가 0이될 때까지

BFS의 호출 수를 증가시키는 식으로 풀었다.

 

 

 

Source (Java)

 

Source (Kotlin)

import org.junit.jupiter.api.Assertions.assertEquals
import org.junit.jupiter.api.Test
import java.util.LinkedList
import java.util.Queue

class Network {
    fun bfs(i: Int, visited: Array<Boolean>, computers: Array<IntArray>) {
        // 3. Create queue
        val queue : Queue<Int> = LinkedList<Int>()

        // 4. visit first node
        queue.add(i)
        visited[i] = true

        // 5. while queue is not empty,
        while (queue.isNotEmpty()) {
            // visit adjacent nodes
            val rowIdx = queue.poll()
            for (colIdx in computers[rowIdx].indices) {
                if (!visited[colIdx] && computers[rowIdx][colIdx] == 1) {
                    visited[colIdx] = true
                    queue.add(colIdx)
                }
            }
        }

    }

    fun network(n: Int, computers: Array<IntArray>): Int {
        var answer = 0

        // 1. create visited arr
        val visited = Array<Boolean>(n) { false }

        // 2. Define end condition
        for (i in 0 until n) {
            if (!visited[i]) {
                bfs(i, visited, computers)
                answer++
            }
        }


        return answer
    }

    @Test
    internal fun testNetwork() {
        assertEquals(1, network(4, arrayOf(intArrayOf(1, 0, 0, 1), intArrayOf(0, 1, 1, 0), intArrayOf(0, 1, 1, 1), intArrayOf(1, 0, 1, 1))))
    }
}

 

속도 측정