[Swift] 백준_이분 그래프(1707)

문제

 

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

 

풀이

 

처음엔 문제도 제대로 이해못했고, 제대로 이해하고 나서도 푸는데 오래걸렸다.

 

그래프가 두 집합으로 나뉠때 각 집합의 원소들이 연결되어있지 않아야한다.

 

나는 BFS를 이용했다. visited의 첫 값을 0으로 두고, 1부터 차례대로 반복문을 돌렸다.

그래서 visited값이 0인 경우엔 값을 1로 만들고, 해당 점과 연결된 모든 점을 확인했다. 해당 점과 연결이 되어있다는건 같은 집합에 분류될수 없다는 얘기이므로 visited의 값을 해당 점의 음수값으로 설정해주었다.

visited값이 0이 아니라 1또는 -1의 값을 가지고 있으면, 그 값을 가지고 연결된 점들을 확인해주었따. 이때 연결된 점과 현재의 점 모두 방문한 상태인데 값이 같다는 것은 모순이 되므로 이분그래프가 될 수 없다는 의미이다.

import Foundation

let k = Int(readLine()!)!
outer: for _ in 0..<k {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    let v = input[0]; let e = input[1]
    var lines: [Int: [Int]] = [:]
    var visited = Array(repeating: 0, count: v + 1)
    var queue: [Int] = []
    for _ in 0..<e {
        let line = readLine()!.split(separator: " ").map { Int(String($0))! }
        if lines[line[0]] == nil {
            lines[line[0]] = [line[1]]
        } else {
            lines[line[0]]!.append(line[1])
        }
        if lines[line[1]] == nil {
            lines[line[1]] = [line[0]]
        } else {
            lines[line[1]]!.append(line[0])
        }
    }
    for i in 1...v {
        if visited[i] == 0 {
            visited[i] = 1
        }
        queue = [i]
        while !queue.isEmpty {
            let cur = queue.removeFirst()
            if lines[cur] == nil {
                continue
            }
            for j in 0..<lines[cur]!.count {
                if visited[lines[cur]![j]] == 0 {
                    queue.append(lines[cur]![j])
                    visited[lines[cur]![j]] = -visited[cur]
                } else {
                    if visited[lines[cur]![j]] == visited[cur] {
                        print("NO")
                        continue outer
                    }
                }
            }
        }
    }
    print("YES")
}

 

 

_____________________________________________________________________________________________________

 

 

시간이 너무 길어서 라이노님의 입출력코드를 적용해보았더니 시간이 1/3로 줄어들었따. 그리고 실력이 많이 모자란 것 같다.