[Swift] 백준 도넛과 막대 그래프 - 2024 카카오 겨울 인턴십

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

프로그래머스

---

문제

• 총 3 가지 모양의 그래프 존재

도넛 모양

막대 모양

8자 모양

• 여러 그래프들로 향하는 임의의 정점(이후 중점이라고 표현)이 존재
• 간선 정보가 담긴 배열
• 정점의 번호와 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 반환

 

조건

• 그래프의 수는 2개 이상 존재
• 간선은 최대 1,000,000개

 

풀이

일단 자료가 1,000,000개 라면 단순한 반복문으로 푸는 거에 문제가 생긴다.

1. Dictionary로 간선의 정보를 담는다.
2. 간선의 정보에서 화살표를 받는(incoming) / 화살표를 주는(outgoing) 정보를 담는다.

각 그래프마다의 특징이 존재한다.

• 도넛 모양의 노드들은 1개의 incoming과 1개의 outgoing을 가진다.
• 직선 모양의 마지막 노드는 1개의 incoming과 0개의 outgoing을 가진다.
• 8자 모양의 노드들은 도넛 모양과 동일하게 1개의 incoming과 1개의 outgoing을 가진다.
  추가로 중심이 되는 노드는 2개의 incoming과 2개의 outgoing을 가진다.

중점도 특징이 존재한다.

• 0개의 incoming과 2개 이상의 outgoing을 가진다.

 

그림을 통한 예시

Dictionary를 사용한 이유는 Array로 만들기에는 어떤 숫자가 모른다는 부분도 있다.

"예시 1"에서도 위에서 언급된 특징을 가지게 된다.

예시 1

"예시 2"에서는 보다 복잡한 그래프가 존재하지만, 언급된 특징을 가지게 된다.

예시 2

특징들을 조합하면 공식이 만들어지게 된다.

▶ 1개의 incoming과 0개의 outgoing 노드는 막대 모양의 그래프에 단 하나만 존재
▶ 2개의 incoming과 2개의 outgoing 노드는 8자 모양의 그래프에 단 하나만 존재
▶ 0개의 incoming과 2개 이상의 outgoing 노드는 중점이다.
▶ 중점에서 outgoing의 갯수는 그래프의 총합과 같다.

 

코드

import Foundation

func solution(_ edges:[[Int]]) -> [Int] {
    var nodes = [Int: [Int]]()
    var main = 0, stick = 0, eight = 0
    
    for edge in edges {
        var outgoing = nodes[edge[0], default: [0, 0]]
        outgoing[0] += 1
        nodes.updateValue(outgoing, forKey: edge[0])
        
        // outgoing하고 나서 incoming하는 이유는
        // [1, 1]과 같은 노드의 값을 제대로 전달하기 위함이다.
        var incoming = nodes[edge[1], default: [0, 0]]
        incoming[1] += 1
        nodes.updateValue(incoming, forKey: edge[1])
    }
    
    for node in nodes {
        let outgoing = node.value[0]
        let incoming = node.value[1]
        
        if outgoing > 1, incoming == 0 {          // "중점"의 특징
            main = node.key
        } else if outgoing > 1, incoming > 1 {    // "8자 모양"의 특징
            eight += 1
        } else if outgoing == 0 {                 // "막대 모양"의 특징
            stick += 1
        }
    }
    
    // main의 given에서 막대 모양과 8자 모양을 제외
    let graphs = nodes[main]![0]
    let donut = graphs - stick - eight 
    
    return [main, donut, stick, eight]
}