[프로그래머스] 도넛과 막대 그래프

문제

프로그래머스

입력

edges:[[Int]] = [[출발정점 번호, 도착 정점번호]]

결과

answer [Int] = [중앙정점, 도넛 그래프 개수, 막대 그래프 개수, 8자 그래프 개수]

해석

각 그래프의 특징을 살펴보자.

 

그래프 특징

1. 막대 그래프: 그래프 내에 나가는 간선이 없는 정점이 있다.

2. 8자 그래프: 그래프 내에 들어오는 간선과 나가는 간선이 모두 2개 이상인 정점이 있다.

3. 도넛 그래프: 판단할 큰 특징이 없어 전체 그래프에서 막대그래프와 8자 그래프를 뺀 나머지로 개수를 세준다.

 

(도넛그래프 수 = 전체 그래프 수 -  (막대 그래프 수 + 8자 그래프 수))

 

그래프 특징은 정리가 되었다.

해야할 것을 정리해보자.

 

1. 우리는 나가는 간선과 들어가는 간선의 개수를 카운팅해야한다.

2. 정점간의 연결관계인 그래프를 그린다.

3.  (1<= 정점 번호 <= ?? ) 이므로 최대 정점번호도 구해줘야한다.

4. 여기서 중요한 특징은 정점이 1 ,2,3,4 연속적으로 나온다는 조건이 없으므로 , 존재하지 않는 정점인지 역시 판단해야한다.

코드

import Foundation

func solution(_ edges:[[Int]]) -> [Int] {
    // 중앙 정점이 가르키는 각 그래프 정점 특징
    // n 도넛 = 규칙이 크게 없음, 그냥  막대와 8자를 구하고 나머지를 도넛
    // n 막대 = 나가는 정점 없음 
    // 8자 막대 = 나가는 정점 들어오는 정점 2개 이상
    // 입력 = [[출발 정점, 도착정점]]
    // 결과 = [정점, 도넛, 막대, 8자]
    // 중앙정점 = 들어가는 간선이 없고 나가는 간선이 2이상
    var answer: [Int] = [0, 0, 0, 0]
    var graph: [Int: [Int]] = [:]
    var inDegrees: [Int: Int] = [:]
    var outDegrees: [Int : Int] = [:]
    
    var maxVertex: Int = -1
    
    for edge in edges {
        let departureVertex = edge[0]
        let destinationVertex = edge[1]
        
        maxVertex = max(departureVertex, maxVertex)
        maxVertex = max(destinationVertex, maxVertex)
        
        
        outDegrees[departureVertex, default: 0] += 1
        inDegrees[destinationVertex, default: 0] += 1
        graph[departureVertex, default: []].append(destinationVertex)
        
        
    }

    for v in 1...maxVertex {
    
        let inCount = inDegrees[v, default: 0]
        let outCount = outDegrees[v, default: 0]
        
        // 존재하지 않는 정점
        if inCount == 0 && outCount == 0 { continue }
        
        if inCount == 0 && outCount >= 2 { // 들어가는 간선이 없고 나가는 간선이 2이상이면 중앙 점점
            // 나가는 간선이 2 이상인 이유는 , 그래프 수의 합이 2 이상이기때뮨에
            answer[0] = v 
        } else if inCount >= 2 && outCount >= 2 { // 8자
            // inCount: (정점에서 가르키는 간선 + 8자 가운데 간선)
            // outCount: 8자 가운데에서 나가는 간선
            answer[3] += 1 
        } else if inCount <= 2 && outCount == 0 { // 막대 
            // inCount: (정점에서 가르키는 간선 + 막대 그래프 내에서 가르키는 간선)
            // outCount: 나가는 간선이 없음
            answer[2] += 1 
        }
        
    }
    
    // 도넛그래프 수 = 전체그래프 수 - (막대 + 8자)
    answer[1] = graph[answer[0]]!.count - (answer[2] + answer[3])  

    return answer
}