[Swift/프로그래머스] 도넛과 막대 그래프 (완전탐색, 그래프)

https://school.programmers.co.kr/learn/courses/30/lessons/258711?language=swift

프로그래머스

 

 

조건

• 1 ≤ edges의 길이 ≤ 1,000,000
  • edges의 원소는 [a,b] 형태이며, a번 정점에서 b번 정점으로 향하는 간선이 있다는 것을 나타냅니다.
  • 1 ≤ a, b ≤ 1,000,000
• 문제의 조건에 맞는 그래프가 주어집니다.
• 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수의 합은 2이상입니다.

 

도넛 모양의 모든 노드는 1개의 incoming과 1개의 outgoing을 가진다.

막대 모양은 마지막 노드는 1개의 ingoing 또는 1개의 outgoing만을 가진다.

8자 모양의 모든 노드들은 1개의 ingoing, 1개의 outgoing을 지니고 있고 중심 노드만 2개의 ingoing , 2개의 outgoing을 지가진다.

 

정점의 경우 0개의 ingoing과 2개 이상의 outgoing을 가진다.

 

풀이

import Foundation

func solution(_ edges: [[Int]]) -> [Int] {
   // 딕셔너리로 간선 정보를 받는다.
    var nodes = [Int:[Int]]()
    var main = 0, stick = 0, eight = 0
    
    for edge in edges {
        // ingoing과 outgoing count를 담는 배열
        var outgoing = nodes[edge[0] ,default: [0,0]]
        // 이때 outgoing에는 [0,0] 이 담긴다.
        outgoing[0] += 1
        
        // edge[0]값의 key의 값을 outgoing 배열로 변경한다.
        nodes.updateValue(outgoing, forKey: edge[0])
        
        // 이때 incoming을 카운트 하려면 outgoing을 먼저 해주어야한다.
        var incoming = nodes[edge[1], default:[0,0]]
        incoming[1] += 1
        nodes.updateValue(incoming,forKey: edge[1])
    }
    
    // nodes에는 해당 노드의 out, in 카운트가 전부 할당되어 있음
    
    for node in nodes {
        let value = node.value
        let outgoing = value[0]
        let incoming = 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
        }
    }
    
    let graph = nodes[main]![0]
    let doughnut = graph - stick - eight
    
    return [main,doughnut, stick, eight ]
}

 

풀이방식

 

그래프 순회를 통해 해결하지 않고, 그래프에 연결된 간선의 수를 비교해서 해결했다.

그렇기에 도넛형의 경우 중심 노드에서 이어지는 선 떄문애 오류가 발생할 수 있기에 중심에서 뻗어나가는 outgoing 카운트에서 다른 그래프들의 수를 빼서 확인했다.

 

코드 작성 유의할점

var outgoing = nodes[edge[0] ,default: [0,0]]

 

이렇게 했을떄 배열이 들어온다. default가 있다고 해서 전체 nodes가 들어온다고 착각하지말자.

그리고 값을 변경할때는

 

nodes.updateValue(outgoing, forKey: edge[0])

 

updateValue(변경할 값, forKey : 키값) 을 할당해서 바꿔주자.

 

추가로 배운점

변수를 선언할때 같은 자료형이라면 var를 한번만 선언하고 쉼표로 구분해서 선언해줄 수 있다.

 var main = 0, stick = 0, eight = 0