[백준][코틀린] 1707 이분 그래프

문제 내용

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다.

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

제한

2 ≤ K ≤ 5
1 ≤ V ≤ 20,000
1 ≤ E ≤ 200,000

예제 입력	예제 출력
2 3 2 1 3 2 3 4 4 1 2 2 3 3 4 4 2	YES NO

문제 풀이

오늘 가장 힘들었던 문제다..

우선 문제 이해부터 낯설었다. 이분 그래프 자체를 몰랐어서 그런지 이분 그래프 = 두개의 그래프로 생각을 했다. 예제 출력을 확인했을 때 이상함을 느끼고 이분 그래프에 대해 검색해보았다.

자료구조 - 이분 그래프(Bipartite Graph)

관련 글 그래프 관련 글은 여기를 참조 그래프 탐색 - BFS는 여기를 참조 그래프 탐색 - DFS는 여기를 참조 1. 이분 그래프 이분 그래프는 그래프 형태의 자료구조인데 정점을 2그룹으로 나눌 수 있

hongjw1938.tistory.com

위의 링크를 참고하여 이분 그래프에 대해 이해하였다. 결국 각 그룹을 구분하여 그룹 안에서는 간선이 없어야 되었다.

처음 풀이

처음에는 그래프를 입력받아서 인접 행렬로 표현하였다. 그러고 나서 BFS 함수를 도는데

루프가 있다면 false를 반환한다.
인접 정점이면서 아직 그룹이 정해지지 않았다면 그룹을 정해준다. (현재 정점이 1이면 -1, 현재 정점이 -1이면 1)
인접 정점인데, 같은 그룹이라면 false를 반환한다.

이렇게 풀고, 예제 출력도 무난하게 통과했다. 백준 사이트에 제출했는데... 메모리 초과 가 떴다.

두번째 풀이 (메모리 초과를 없애기 위한 노력들)

메모리 초과를 확인하고, 객체 생성이 많이 되어 그런지, 입력받을 때 메모리를 많이 차지 하는지 검토를 하였고 여러가지 방법으로 시도하였으나 끄떡없었다...

그러다 인접행렬 크기가 너무 커서 그런가 라고 생각이 들어 Array<BooleanArray> → Array<MutableList<Int>>로 변경하고, 인접 정점인지 확인하기 위해 in 함수를 사용하였다.

이 방식으로 풀었더니 메모리 초과 대신 시간 초과 가 떴다..

세번째 풀이 (시간 초과와 메모리 초과를 없애기 위한 노력들)

다시 인접 행렬로 돌리고 이것저것 시도 해보다가 불현듯 아이디어가 떠올랐다. in 함수로 매번 확인하지 말고, mutableList를 순회해서 확인해보면 어떨까? for (i in graph[cur]) { ... }로 시도 해보았다.

이렇게 변경하니, 메모리 초과와 시간 초과는 뜨지 않았다. 하지만 틀렸습니다 가 떴다..

네번째 풀이 (왜 틀렸지?)

코드를 재 검토하면서 생각해보니, bfs를 첫 정점 (0)에서만 출발했다는 사실을 알았다. 바로 bfs 함수에 인자로 start를 넘겨주고 for문을 돌아 확인하는 과정을 추가하였다.

이젠 맞았습니다가 뜨겠지 했지만 틀렸습니다 가 떴고 난 멘붕이 왔다.

다섯번째 풀이 (맞왜틀?)

멘붕이 온 나는 더이상 잘못된게 없는데 이상하다 생각을 하고 초기화가 잘못되었나 하여 top level에 있던 변수들을 지역변수로 옮기는 등 여러 시도를 하고 제출했지만 계속해서 틀렸다고 떴다....

상심하던 와중 눈에 들어온 코드가 있었다.

print(if(isBipartite) "YES" else "NO")

?????????????????????????????????????
내가 왜 println이 아니라 print를 적었지?????????????????????????

~~세번째 풀이부터 println이 아니라 print로 바뀐 것을.. 아래에서 확인할 수 있다.~~

바로 수정하고 제출했더니 기다리고 기다리던 맞았습니다 가 떴다..

여기까지 오는 과정에 매우 험난했다.. 코드를 검토할 때는 아주 꼼꼼하게 확인하고, 백준에 있는 예제를 입력할때는 복사 붙여넣기만 사용하지 말아야겠다고 오늘 또 한번 다짐했다.. 직접 입력해보는 과정은 꼭,, 🥲

</>̆̈ 코드

첫번째 부터 네번째 까지 틀린 코드들을 보고 싶으시면 접은 글을 열어주세요..

// 첫번째 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

private val br = BufferedReader(InputStreamReader(System.`in`))
private lateinit var graph: Array<BooleanArray>
private lateinit var visited: IntArray

fun main() {
    repeat(br.readLine().toInt()) {
        val (v, e) = br.readLine().split(" ").map { it.toInt() }
        graph = Array(v) {BooleanArray(v)}
        visited = IntArray(v)

        for (i in 0 until e) {
            val (v1, v2) = br.readLine().split(" ").map { it.toInt() }
            graph[v1-1][v2-1] = true; graph[v2-1][v1-1] = true
        }

        println(if (bfs(v)) "YES" else "NO")
    }
}

private fun bfs(v: Int): Boolean {
    val queue = LinkedList<Int>()
    queue.offer(0); visited[0] = 1

    while (queue.isNotEmpty()) {
        val cur = queue.poll()

        if (graph[cur][cur]) return false

        for (i in 0 until v) {

            if (graph[cur][i] && visited[i] == 0) {
                queue.add(i); visited[i] = visited[cur] * -1

            } else if (graph[cur][i] && visited[i] == visited[cur]) return false
        }
    }

    return true
}

// 두번째 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

private val br = BufferedReader(InputStreamReader(System.`in`))
private lateinit var graph: Array<MutableList<Int>>
private lateinit var visited: IntArray
private var v = 0; private var e = 0

fun main() {
    repeat(br.readLine().toInt()) {
        StringTokenizer(br.readLine()).run {
            v = nextToken().toInt()
            e = nextToken().toInt()
        }
        graph = Array(v) { mutableListOf() }
        visited = IntArray(v)

        for (i in 0 until e) {
            StringTokenizer(br.readLine()).run {
                val v1 = nextToken().toInt()
                val v2 = nextToken().toInt()
                graph[v1-1].add(v2-1); graph[v2-1].add(v1-1)
            }
        }

        println(if (bfs()) "YES" else "NO")
    }
}

private fun bfs(): Boolean {
    val queue = LinkedList<Int>()
    queue.offer(0); visited[0] = 1

    while (queue.isNotEmpty()) {
        val cur = queue.poll()

        // 루프가 있다면 false 반환
        if (cur in graph[cur]) return false

        for (i in 0 until v) {

            // 인접 정점이면서 아직 그룹이 정해지지 X
            if (i in graph[cur] && visited[i] == 0) {
                queue.add(i); visited[i] = visited[cur] * -1

            } else if (i in graph[cur] && visited[i] == visited[cur]) return false // 인접했는데 같은 그룹이면
        }
    }

    return true
}

// 세번째 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

private val br = BufferedReader(InputStreamReader(System.`in`))
private lateinit var graph: Array<MutableList<Int>>
private lateinit var visited: IntArray
private var v = 0; private var e = 0

fun main() {
    repeat(br.readLine().toInt()) {
        StringTokenizer(br.readLine()).run {
            v = nextToken().toInt()
            e = nextToken().toInt()
        }
        graph = Array(v) { mutableListOf() }
        visited = IntArray(v)

        for (i in 0 until e) {
            StringTokenizer(br.readLine()).run {
                val v1 = nextToken().toInt()
                val v2 = nextToken().toInt()
                graph[v1-1].add(v2-1); graph[v2-1].add(v1-1)
            }
        }
        
        print(if(bfs()) "YES" else "NO")
    }
}

private fun bfs(): Boolean {
    val queue =  LinkedList<Int>()
    queue.offer(start); visited[start] = 1

    while (queue.isNotEmpty()) {
        val cur = queue.poll()

        for (i in graph[cur]) {
            // 루프가 있다면 false 반환
            if (i == cur) return false

            // 인접 정점이면서 아직 그룹이 정해지지 X
            if (visited[i] == 0) {
                queue.add(i); visited[i] = visited[cur] * -1

            } else if (visited[i] == visited[cur]) return false // 인접했는데 같은 그룹이면
        }
    }

    return true
}

// 네번째 코드

package dfs_bfs

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

private val br = BufferedReader(InputStreamReader(System.`in`))
private lateinit var graph: Array<MutableList<Int>>
private lateinit var visited: IntArray
private var v = 0; private var e = 0

fun main() {
    repeat(br.readLine().toInt()) {
        StringTokenizer(br.readLine()).run {
            v = nextToken().toInt()
            e = nextToken().toInt()
        }
        graph = Array(v) { mutableListOf() }
        visited = IntArray(v)

        for (i in 0 until e) {
            StringTokenizer(br.readLine()).run {
                val v1 = nextToken().toInt()
                val v2 = nextToken().toInt()
                graph[v1-1].add(v2-1); graph[v2-1].add(v1-1)
            }
        }

        var isBipartite = true

        for (i in 0 until v) {
            if (visited[i] != 0) continue
            isBipartite = bfs(i)
            
            if (!isBipartite) break
        }

        print(if(isBipartite) "YES" else "NO")
    }
}

private fun bfs(start: Int): Boolean {
    val queue =  LinkedList<Int>()
    queue.offer(start); visited[start] = 1

    while (queue.isNotEmpty()) {
        val cur = queue.poll()

        for (i in graph[cur]) {
            // 루프가 있다면 false 반환
            if (i == cur) return false

            // 인접 정점이면서 아직 그룹이 정해지지 X
            if (visited[i] == 0) {
                queue.add(i); visited[i] = visited[cur] * -1

            } else if (visited[i] == visited[cur]) return false // 인접했는데 같은 그룹이면
        }
    }

    return true
}

🙆🏻‍♀️ 맞았습니다 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

private val br = BufferedReader(InputStreamReader(System.`in`))
private lateinit var graph: Array<MutableList<Int>>
private lateinit var visited: IntArray
private var v = 0; private var e = 0

fun main() {
    repeat(br.readLine().toInt()) {
        StringTokenizer(br.readLine()).run {
            v = nextToken().toInt()
            e = nextToken().toInt()
        }
        graph = Array(v) { mutableListOf() }
        visited = IntArray(v)

        for (i in 0 until e) {
            StringTokenizer(br.readLine()).run {
                val v1 = nextToken().toInt()
                val v2 = nextToken().toInt()
                graph[v1-1].add(v2-1); graph[v2-1].add(v1-1)
            }
        }

        var isBipartite = true

        for (i in 0 until v) {
            if (visited[i] != 0) continue
            isBipartite = bfs(i)

            if (!isBipartite) break // 이분 그래프가 아니라면 더 볼 필요가 없음
        }

        println(if(isBipartite) "YES" else "NO")
    }
}

private fun bfs(start: Int): Boolean {
    val queue =  LinkedList<Int>()
    queue.offer(start); visited[start] = 1

    while (queue.isNotEmpty()) {
        val cur = queue.poll()

        for (i in graph[cur]) {
            // 루프가 있다면 false 반환
            if (i == cur) return false

            // 인접 정점이면서 아직 그룹이 정해지지 X
            if (visited[i] == 0) {
                queue.add(i); visited[i] = visited[cur] * -1

            } else if (visited[i] == visited[cur]) return false // 인접했는데 같은 그룹이면
        }
    }

    return true
}

링크

1707번: 이분 그래프

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에

www.acmicpc.net

저작자표시 비영리 변경금지