[Swift 알고리즘] 백준 BOJ - 1707 이분 그래프 + 반성

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "백준 BOJ - 1707 이분 그래프" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

1707번: 이분 그래프

 

---

풀이

이번 문제는 그래프 문제입니다.

 

이분 그래프의 특징과 그래프 탐색에 대한 지식을 이용하면 풀 수 있습니다.

백준 문제에서 나오는 이분 그래프의 정의는 살짝 어렵다고 느껴집니다.

각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때

백준의 이 정의는 "노드에 색을 칠하며 탐색했을 때 인접한 정점끼리는 색이 같으면 안 된다"라고 표현할 수 있습니다.

즉 이번 문제에서는 "색을 칠하며"와 "인접한 정점끼리는 색이 같으면 안 된다"라는 것을 코드로 구현하면 됩니다.

탐색은 dfs, bfs 모두 가능하며 저는 재귀를 이용한 dfs를 이용했습니다.

 

1번 노드부터 탐색하길 시작하고 그 노드와 연결된 노드를 재귀를 이용해 탐색합니다.

방문하지 않은 노드라면 이전에 방문한 노드와 다른 색을 칠해주고 다음 노드를 탐색합니다.

이미 방문한 노드라면 현재 노드와 이전에 탐색한 노드와 색이 동일하면 이분 그래프가 아닙니다.

 

모든 그래프 문제가 그렇듯이 그림을 그리면서 하면 훨씬 수월하게 이해가 가능합니다.

공책을 피고 펜을 들어 그림을 그려보세요!

 

개선한 점

지난 문제에서는 그래프를 Directory를 이용하고, visited와 needVisit 정수 배열을 이용했습니다.

따라서 로직을 시작할 때 디렉토리를 초기화해주는 코드가 들어가 비교적 코드가 복잡해 보였고,

방문을 이미 했는가에 대한 것을 알기 위해 contains()를 호출하여 비교적 시간이 오래 걸렸습니다.

 

이번 문제부터는 graph는 2차원 배열을 이용해 Array(repeating:, count:)로 초기화하여 코드의 길이를 줄였고,

visited는 Bool 배열을 이용해 index로 바로 참조가 가능하도록 개선하였습니다.

 

반성한 점

이번 문제는 이분 그래프라는 자료구조에 대한 지식이 문제의 해결에 직접적으로 영향을 주었습니다.

저는 그것이 부족해 시간이 오래 걸렸고 결국에는 다른 사람의 코드를 참고해야 했죠.

어렴풋이 아는 자료구조가 아닌 정말 제대로 아는 자료구조가 필요한 시기라는 것을 깨달았습니다.

시간을 들여 자료구조도 함께 공부해야 겠다고 반성하였습니다.

 

---

전체 코드

//1707 이분 그래프
import Foundation

let count = Int(readLine()!)!

for _ in 0..<count {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    let nodeCount = input[0], edgeCount = input[1]
    
    var graph: [[Int]] = Array(repeating: [], count: nodeCount+1)
    var visited: [Bool] = Array(repeating: false, count: nodeCount+1)
    var color: [Bool] = Array(repeating: false, count: nodeCount+1)
    for _ in 0..<edgeCount {
        let edge = readLine()!.split(separator: " ").map { Int(String($0))! }
        graph[edge[0]].append(edge[1])
        graph[edge[1]].append(edge[0])
    }
    
    var result: Bool = true
    func dfs(_ depth: Int) {
        for node in graph[depth] {
            if visited[node] {
                if color[node] == color[depth] {
                    result = false
                    return
                }
            } else {
                visited[node] = true
                color[node] = !color[depth]
                dfs(node)
            }
        }
    }
    
    for i in 1...nodeCount {
        dfs(i)
        
        if !result {
            break
        }
    }
    
    print(result ? "YES" : "NO")
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.