[알고리즘] 프로그래머스 - 네트워크

DFS를 풀었다면, 당연히 BFS도 풀어주는게 알고리즘의 도리이다. 이번에 볼 내용은 프로그래머스의 네트워크이다. 문제를 먼저 보겠다.

 

문제

문제설명

2차원 배열로 주어진 computers에서 서로 연결된 네트워크의 개수를 구하는 것이다. 이때 제한사항 중에서 아래와 같은 사항을 알 수 있다.

• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현한다는 것은, 모든 배열을 다 탐색할 필요가 없고, n^2 / 2 + n 만큼 탐색을 진행하면 된다. O(n^2)로 O(n^2/2)로 시간 복잡도를 줄일 수 있다.
• 노드 1개 자체만으로도 네트워크가 될 수 있다.

접근방법

BFS로 진행했다. 이때 1노드와 2노드가 연결되었다고 할 때 탐색을할 때 1노드에서만 진행하고 2노드는 따로 진행하지 않아도 1노드 연결되있으므로, visited는 2차원 배열이 아니라 1차원 배열로만 진행했다.

 

정답코드

import java.util.LinkedList
import java.util.Queue

class Solution {
    fun solution(n: Int, computers: Array<IntArray>): Int {
        var answer = 0
        val visited = BooleanArray(n)

        for (i in computers.indices) {
            if (!visited[i]) { //탐색하지 않은 노드를 간다.
                // 탐색을 하지 않았다는건 이전에 노드와 연결된 노드가 아니라 새로운 네트워크를 의미한다.
                // 따라서 answer를 증가시켜준다.
                answer++ 
                go(computers, visited, n, i)
            }
        }
        return answer
    }

    private fun go(computers: Array<IntArray>, visited: BooleanArray, n: Int, idx: Int) {

        val queue: Queue<Int> = LinkedList<Int>()
        queue.offer(idx)
        visited[idx] = true

        while(queue.isNotEmpty()){
            val node = queue.poll()

            for(i in 0 until n){
                //xpos는 동일하고, ypos는 다른데, 이때 해당 값이 1이라는건
                //서로 연결된 네트워크를 의미한다.
                //따라서 동일한 네트워크 이므로 visited만 true로 해준다.
                //어차피 해당 xpos의 네트워크는 연결된 노드이니까 나중에 방문 안해도 된다.
                if(computers[node][i] == 1 && !visited[i]){
                    visited[i] = true
                    queue.offer(i)
                }
            }
        }
    }
}

 

문제출처 : https://school.programmers.co.kr/learn/courses/30/lessons/43162 (프로그래머스 - 코딩테스트 연습(타겟 넘버))