[백준] (Swift) 1707번 - 이분그래프 (DFS로 풀기!)

👉 문제 링크

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

1707번: 이분 그래프

 

🧑🏻‍💻 문제 풀이

• 이분그래프 이면 1, 이분그래프가 아니면 -1를 flag에 저장해주었다.
• 정점은 각각 1과 -1로 구별해주었다. 만약 인접한 정점이 둘다 1이거나, 둘다 -1이라면 이건 이분그래프가 아닌거다! 이 값들은 visited 에 넣어주었다.

 

아래 코드는 main으로 돌아가는 부분이다. 차례대로 설명을 작성해보자면

• 처음 입력받는 K 만큼 result가 출력되어야 하므로 모든 과정을 for문으로 묶어야 한다.
• VE에 정점갯수 V, 간선갯수 E를 받는다.
• grpah 는 아래와 같은 형태로 받을 것이다.

• 이 문제에서 핵심은, 비연결 그래프도 모두 탐색해주어야 한단 것이다. 그렇기 떄문에 모든 정점을 탐색해보기 위해서 for문을 돌릴 때, 1부터 VE[0]+1 까지 돌려주어야 한다. 그래야 for문에서 하나하나 모든 정점을 탐색하고, 인접한 곳을 탐색해볼 수 있다.
• 첫 정점부터 차례대로 visited를 확인한다. 0이게 되면 방문하지 않았던 노드이므로 bfs를 진행해서 탐색해 줄 것이다.
  • 만약 bfs에서 false 가 나오게 된다면, 이분그래프가 아닌 것이다. 
  • 바로 flag에 -1을 넣어주고 break해서 for문을 탈출한다.
• 그리고 지금 돌고있는 가장 최상단 for문이 끝나기전에 YES or NO 를 판단해서 출력해주어야한다.

for _ in 0..<K {
    let VE = readLine()!.split(separator: " ").map{ Int(String($0))! }
    graph = Array(repeating: [Int](), count: VE[0]+1) // node 수 보다 +1
    visited = Array(repeating: 0, count: VE[0]+1)
    flag = 1 // 1: 이분그래프, -1: 아닌그래프
    for _ in 0..<VE[1] {
        let uv = readLine()!.split(separator: " ").map{ Int(String($0))! }
        graph[uv[0]].append(uv[1])
        graph[uv[1]].append(uv[0])
    }
    
    for k in 1..<VE[0]+1 {
        if visited[k] == 0 {
            let tem = bfs(k)
            if tem == false {
                flag = -1
                break
            }
        }
    }
    
    if flag == 1 {
        print("YES")
    } else if flag == -1 {
        print("NO")
    }
}

 

• DFS 코드는 다음과 같다.
• 우선 DFS에 진입하자마자 방문처리를 해준다. 
• 그리고 deque 배열에 현재 방문한 정점을 넣어준다. 
  • deque에는 다음 방문할 노드들을 넣어주는 리스트로 활용할 것이다. 그래서 해당 deque는 연결그래프가 끝날때까지 비지 않는다. deque가 비어있다는 것은, 그래프가 끊겼다는 뜻이다.
• while문에 진입해서 deque에서 값을 앞에서부터 하나씩 빼서 탐색해줄 것이다.

func bfs(_ v: Int) -> Bool {
    visited[v] = 1
    var deque: [Int] = []
    deque.append(v)

    while !deque.isEmpty {
        let a = deque.removeFirst()

        for i in graph[a] {
            if visited[i] == 0 { //방문하지 않은 노드라면
                visited[i] = -visited[a] // visited 에는 1, -1 로 정점 색을 구별
                deque.append(i) //연결된 다음 노드느 i가 될 것
            } else {
                if visited[i] == visited[a] { // 같다면, 접한 정점의 색이 같다는 뜻 -> false
                    return false
                }
            }
        }
    }
    return true
}

 

💻 전체코드

https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/1707_%EC%9D%B4%EB%B6%84%20%EA%B7%B8%EB%9E%98%ED%94%84/main.swift

GitHub - deslog/Algorithm

let K = Int(String(readLine()!))!
var flag = 0
var graph: [[Int]] = [[]]
var visited: [Int] = []

for _ in 0..<K {
    let VE = readLine()!.split(separator: " ").map{ Int(String($0))! }
    graph = Array(repeating: [Int](), count: VE[0]+1) // node 수 보다 +1
    visited = Array(repeating: 0, count: VE[0]+1)
    flag = 1 // 1: 이분그래프, -1: 아닌그래프
    for _ in 0..<VE[1] {
        let uv = readLine()!.split(separator: " ").map{ Int(String($0))! }
        graph[uv[0]].append(uv[1])
        graph[uv[1]].append(uv[0])
    }
    
    for k in 1..<VE[0]+1 {
        if visited[k] == 0 {
            let tem = bfs(k)
            if tem == false {
                flag = -1
                break
            }
        }
    }
    
    if flag == 1 {
        print("YES")
    } else if flag == -1 {
        print("NO")
    }
}

func bfs(_ v: Int) -> Bool {
    visited[v] = 1
    var deque: [Int] = []
    deque.append(v)

    while !deque.isEmpty {
        let a = deque.removeFirst()

        for i in graph[a] {
            if visited[i] == 0 { //방문하지 않은 노드라면
                visited[i] = -visited[a] // visited 에는 1, -1 로 정점 색을 구별
                deque.append(i) //연결된 다음 노드느 i가 될 것
            } else {
                if visited[i] == visited[a] { // 같다면, 접한 정점의 색이 같다는 뜻 -> false
                    return false
                }
            }
        }
    }
    return true
}