프로그래머스 - 네트워크(43162)

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

프로그래머스

 

 

아이디어

네트워크는 최대 n개 컴퓨터간 연결을 확인하고 끊어지면 네트워크 개수 + 1

1. 1번 컴퓨터 큐에 추가
2. 큐에서 하나씩 빼면서 해당 컴퓨터에 연결되어 있는 컴퓨터들을 탐색
3. 탐색한 컴퓨터는 visited 처리
4. 연결되어 있는 컴퓨터를 큐에 추가
   • 제외: 자신, 방문했던 컴퓨터, 연결되지 않은 컴퓨터
5. 큐가 비면(연결 되어 있는 컴퓨터를 모두 탐색했다면) 네트워크 + 1
6. 방문하지 않은 컴퓨터를 찾아 큐에 추가 (모든 컴퓨터를 방문할 때까지 반복)
7. 네트워크 개수 반환

 

첫 번째 시도

import Foundation

func solution(_ n:Int, _ computers:[[Int]]) -> Int {
    var visited = Array(repeating: false, count: n) // 방문 표시
    var count = 0 // 네트워크 개수
    var queue = [0] // 연결되어 있는 컴퓨터의 인덱스 저장 (첫 번째 컴퓨터부터 방문)
    
    while true { // 모든 컴퓨터 방문할 때까지 반복
        if let computer = queue.popLast() { // 큐에서 방문할 컴퓨터 제거
            visited[computer] = true // 방문 처리
            for (i, connect) in computers[computer].enumerated() { // 방문한 컴퓨터와 연결된 컴퓨터 탐색
			        // 자신, 방문했던 컴퓨터, 연결되지 않은 컴퓨터 제외 
                if i == computer || visited[i] || connect == 0 { continue }
                queue.append(i) // 큐에 추가 
            }
        } else { // 비어있으면
            count += 1 // 네트워크 1 증가
            if let index = visited.firstIndex(of: false){ // 아직 방문하지 않은 컴퓨터 찾기
                queue.append(index) // 아직 방문하지 않은 컴퓨터 큐에 추가
            } else {
                break // 모두 방문했으면 break
            }
        }
    }
    return count
}

→ 시간초과 발생 (시간 초과가 나지 않을 때도 있음)

예외 발생 가능성

1. 큐가 비어지지 않는 경우?
2. 모든 컴퓨터가 true가 되지 않는 경우?

만약 컴퓨터의 최대 개수인 200개의 컴퓨터가 모두 연결되어 있을 때를 생각해보면

computers 배열은 [[1, 1, 1, 1, 1, … , 1], [1, 1, 1, 1, …. 1] …. [1, 1, 1, 1, … ,1]] 이처럼 모두 1일 것이다

큐에 자신과 연결된 컴퓨터를 추가할 때, 자신, 방문한 노드, 연결되지 않은 노드를 제외하지만 이렇게 된다면

1번 컴퓨터에서는 자신을 제외한 199개의 컴퓨터를 추가하고, 2번 컴퓨터에서는 이미 방문한 1번과 자신을 제외하고 198번을 추가하며 계속 추가될 것이다

따라서 시간 초과가 날 가능성이 있음

제외 조건에 큐에 포함된 컴퓨터 제외를 추가!

1. 연결되어 있는 컴퓨터를 큐에 추가
   • 제외: 자신, 방문했던 컴퓨터, 연결되지 않은 컴퓨터, + 큐에 이미 포함된 컴퓨터

import Foundation

func solution(_ n:Int, _ computers:[[Int]]) -> Int {
    var visited = Array(repeating: false, count: n) // 방문 표시
    var count = 0 // 네트워크 개수
    var queue = [0] // 연결되어 있는 컴퓨터의 인덱스 저장 (첫 번째 컴퓨터부터 방문)
    
    while true { // visited가 모두 true일 때까지(모든 컴퓨터 방문할 때까지)
        if let computer = queue.popLast() { // 큐에서 방문할 노드 제거
            visited[computer] = true // 방문 처리
            for (i, connect) in computers[computer].enumerated() {
                if i == computer || visited[i] || connect == 0 || queue.contains(i) { continue }
                queue.append(i)
            }
        } else { // 비어있으면
            count += 1 // 네트워크 1 증가
            if let index = visited.firstIndex(of: false){ // 아직 방문하지 않은 컴퓨터 찾기
                queue.append(index) // 아직 방문하지 않은 컴퓨터 큐에 추가
            } else {
                break // 모두 방문했으면 break
            }
        }
    }
    return count
}

시간이 확실하게 감소되었다