[백준] 1707번 - Swift

https://www.acmicpc.net/problem/1707
문제링크!!

코드

import Foundation

let a = Int(readLine()!)!

for _ in 0..<a {
    let num = readLine()!.split(separator: " ").map{Int($0)!}
    let N = num[0]
    let M = num[1]
    var dic = [Int:[Int]]()
    var visited = Array(repeating: false, count: N+1)
    // 이분 그래프를 찾기 위해 노드 색 임의 설정
    var color = Array(repeating: false, count: N+1)
    
    // 그래프 생성
    for _ in 0..<M {
        let n = readLine()!.split(separator: " ").map{Int($0)!}
        let x = n[0]
        let y = n[1]
        
        if dic[x] != nil {
            dic[x]?.append(y)
        } else {
            dic[x] = [y]
        }
        
        if dic[y] != nil {
            dic[y]?.append(x)
        } else {
            dic[y] = [x]
        }
    }
    
    // 하나의 그래프로 이어져 있는지 확인하기 위한 array
    var arr = [String]()
    
    func dfs(_ start: Int) {
        visited[start] = true
        
        for i in dic[start] ?? [] {
            if !visited[i] {
                color[i] = !color[start]
                dfs(i)
            } else {
                if color[i] == color[start] {
                    arr.append("NO")
                    return
                }
            }
        }
    }
    
    for i in 1...N {
        dfs(i)
    }
    
    if arr.isEmpty {
        print("YES")
    } else {
        print("NO")
    }
}

회고

• 골드4인데 스스로 풀었다 (성장했다)
• 이분 그래프를 찾는 방법은 노드에 색을 칠하고 이전 노드와 현재 노드의 색이 다르면 이분 그래프이다