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

요구능력 : DFS와 인접리스트와 이분그래프에 대한 이해

 

코드설명 : 

 

이분그래프에 대해 알면 문제가 대충 보인다.

구글링하면 좋은자료가 많으니 구글링으로..

 

일단 DFS와 BFS둘다 가능하다는데, 나는 DFS로 풀었다.

저번에도 비슷한문제를 푼적이 있는데, 이런식으로 간선에 대한 정보가 주어지는 DFS의 경우 인접리스트를 활용해줘야한다.

 

인접리스트를 하나씩 돌면서 방문하지 않은 노드에 대해서는 이전에 방문한 노드와 다른색을 지정해준다.(이분그래프의 특성)

그리고 이미 방문한 노드는 현재노드와 이전에 방문한 노드가 색이 같다면 그건 이분그래프가 아니므로 스위치(isColor)를 설정하여 NO를 프린트하도록 한다.

 

후기 : 이분그래프에 대해 이해하고 DFS를 잘 연계한다면 어렵지 않은 문제이다.

요즘 골드문제들도 이해가 잘가고 풀리는것도 많아서 성장한게 느껴진다.

백준골드 달성 Vv

let k = Int(String(readLine()!))!
for _ in 1...k {
    let ve = readLine()!.split(separator: " ").map{Int(String($0))!}
    let v = ve[0]
    let e = ve[1]
    var visited: [Bool] = Array(repeating: false, count: v + 1)
    var color = Array(repeating: false, count: v + 1)
    var list: [[Int]] = Array(repeating: [], count: v + 1)
    list[0].append(0)
    var isColor = false
    
    for _ in 1...e{
        let line = readLine()!.split(separator: " ").map{Int(String($0))!}
        list[line[0]].append(line[1])
        list[line[1]].append(line[0])
    }
    
    func dfs(_ depth: Int) {
    
        for i in 0..<list[depth].count{
            let node = list[depth][i]
            if !visited[node]{
                visited[node] = true
                color[node] = !color[depth]
                dfs(node)
            }else {
                if color[node] == color[depth]{
                    isColor = true
                    return
                }
                
            }
        }
    }
    
    for i in 1..<list.count {
        dfs(i)
    }
    print(isColor ? "NO" : "YES")
}