프로그래머스 네트워크

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

문제

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

네트워크 그림 예제

문제 해결 사전 지식

• BFS/DFS를 통해서 네트워크가 어디까지 연결되어 있는지 찾고 독립된 네트워크의 개수를 출력하는 문제입니다.
  • BFS : 일반적으로 Queue를 활용해 해결합니다.
  • DFS : 일반적으로 재귀를 활용해 해결합니다.
  • computers[i][j]는 그래프 상에서 i 번째 Node(Computer)와 j 번째 Node(Computer)를 연결하는 Edge를 표현합니다.

문제 해결

1. 문제 해결을 위한 BFS를 효율적으로 만들기 위해 탐색되어야 할 대상과 제외되어야 할 대상의 조건을 정합니다.

• 제한사항을 참고하였을 때, i == j 라면 무조건 1이라고 하기에 i == j 이면, BFS의 대상이 아닙니다.
• i != j 여도 이미 방문하였을 경우 다시 BFS의 대상으로 포함되지 않게 해야 합니다. 따라서, **Node의 방문 유무를 알려주는 배열(visited)**을 생성하고 방문 시 값을 업데이트하여 대상에서 제외시켜야 합니다.
• visited에 값이 업데이트되지 않았고, Edge(computers[i][j])가 1(연결된)이라면, BFS Queue에 추가합니다.

 2. BFS가 실행될 때마다 아직 발견되지 않은 네트워크를 찾은 것이므로, 1개씩 증가시키면 됩니다. 마지막으로 혼자 독립된 노드의 경우 visited가 계속 업데이트되지 않으므로, 가장 마지막에 visited가 업데이트 되지 않은 Node의 수의 합을 답으로 제출합니다. 이제 BFS를 기반으로 네트워크의 개수를 파악하는 부분을 작성합니다.

 

 

TEST INPUT

• n = 3
• computers = [[1, 1, 0], [1, 1, 1], [0, 1, 1]]

Total Code

import Foundation

// 문제해결 2
func solution(_ n:Int, _ computers:[[Int]]) -> Int {
    var visited: [Bool] = .init(repeating: false, count: n)
    // QUEUE
    var graph = computers
    var answer = 0
    
    for rowIndex in (0..<computers.count) {
        for columnIndex in (0..<computers[rowIndex].count) {
            if rowIndex == columnIndex { continue }
            
            if visited[columnIndex] == true {
                continue
            }
            
            if computers[rowIndex][columnIndex] == 0 {
                continue
            }
            
            answer += 1
            visited[columnIndex] = true
            bfs(visited: &visited, graph: &graph, start: columnIndex)
        }
    }
    
    answer += visited.filter { !$0 }.count
    
    return answer
}

// 문제해결 1
func bfs(visited: inout [Bool], graph: inout [[Int]], start: Int) {
    var queue = [Int].init()
    queue.append(start)
    
    while !queue.isEmpty {
        let rowIndex = queue.removeFirst()
        
        for columnIndex in (0..<graph[rowIndex].count) {
            if rowIndex == columnIndex { continue }
            
            if visited[columnIndex] == true {
                continue
            }
            
            if graph[rowIndex][columnIndex] == 0 {
                continue
            }
            
            visited[columnIndex] = true
            queue.append(columnIndex)
        }
    }
}