인접한 두 정점의 번호이므로 서로 연결 관계. 즉, 무방향이다.그래프의 모든 정점이 서로 연결되어 있다라는 문구가 없으므로 미연결일 가능성이 존재하다.
위와 같은 이유로 미연결 무방향 그래프로 가정하고 BFS 를 이용하여 인접하는 서로 다른 정점이 인접하지 않도록 (다른 값을 가지도록) 분할할 수 있어야 한다.
즉, 1 - 3, 2 - 3 관계라면 1은 0, 2는 0, 3은 1이어야 한다.
풀이
/*
* 정점 - 1 ~ V 차례대로
* 각 테스트 케이스 첫줄 정점의 개수 V, 간선의 개수 E
* */
private const val IS_NOT_SET = -1
private lateinit var state: IntArray
private lateinit var graph: Array<MutableList<Int>>
fun `1707-이분 그래프`(){
val br = System.`in`.bufferedReader()
val bw = System.out.bufferedWriter()
val k = br.readLine().toInt()
val stringBuilder = StringBuilder()
repeat(k){
val (vertex, edge) = br.readLine().split(" ").map { it.toInt() }
var result = "YES"
graph = Array(vertex + 1){ mutableListOf() }
state = IntArray(vertex + 1){ IS_NOT_SET }
repeat(edge){
val token = java.util.StringTokenizer(br.readLine())
val from = token.nextToken().toInt()
val to = token.nextToken().toInt()
graph[from].add(to)
graph[to].add(from)
}
// 미연결 그래프일 수 있으므로 bfs 를 반복 실행
for(i in 1 .. vertex){
// 시작 정점이 아직 설정되지 않았따면
if(state[i] == IS_NOT_SET) {
if(!bfs(i)){
result = "NO"
break
}
}
}
if(stringBuilder.isNotEmpty()) stringBuilder.append("\n")
stringBuilder.append(result)
}
bw.write(stringBuilder.toString())
bw.flush()
bw.close()
br.close()
}
private fun bfs(start: Int): Boolean {
val arrayDeque = ArrayDeque<Int>()
arrayDeque.addLast(start)
state[start] = 0
while(arrayDeque.isNotEmpty()){
val from = arrayDeque.removeFirst()
for(to in graph[from]){
// 대상 정점이 설정되지 않은 상태라면 이분 그래프이므로 현재 정점의 값과 다른 값을 준다.
if(state[to] == IS_NOT_SET){
state[to] = if(state[from] == 1) 0 else 1
arrayDeque.addLast(to)
}
// 현재 정점과 대상 정점이 같다면 이분 그래프가 아니다.
else if(state[from] == state[to]) return false
}
}
return true
}후기
꽤나 많은 실패를 겪었다.
자체적으로 디버깅했을때는 정답이 잘 나온 것 같은데, 왜 틀렸나 싶었다.
AI 에게 풀이를 물어보니 어느 부분에서 틀렸는지 잘 알려주었으나, 대부분 사소한 오해나 실수로 인한 것임을 알아차렸다.
이미 알고 있는 풀이 방법이었음에도 문제를 제대로 읽지 못하고, 생각이 짧아 틀린 문제여서 너무 아쉽다.
첫 번째 실패
처음에는 그래프를 무방향이 아닌 방향 그래프로 설정하였고, 정점과 연결된 그래프가 존재해야 arrayDeque.add 를 진행하여 틀렸다.
private data class GraphState(
var value: Int,
var isQueueAdded: Boolean
)
private const val IS_NOT_SET = -1
private lateinit var state: Array<GraphState>
private lateinit var graph: Array<MutableList<Int>>
// 첫 시작이 1이 아닐수 있으므로 설정
private var start = 0
fun `1707-이분 그래프`(){
val br = System.`in`.bufferedReader()
val bw = System.out.bufferedWriter()
val k = br.readLine().toInt()
val stringBuilder = StringBuilder()
repeat(k){
val (vertex, edge) = br.readLine().split(" ").map { it.toInt() }
graph = Array(vertex + 1){ mutableListOf() }
state = Array(vertex + 1){ GraphState(IS_NOT_SET, false) }
for(i in 0 until edge){
val token = java.util.StringTokenizer(br.readLine())
val from = token.nextToken().toInt()
val to = token.nextToken().toInt()
if(i == 0) start = from
graph[from].add(to)
}
if(stringBuilder.isNotEmpty()) stringBuilder.append("\n")
stringBuilder.append(bfs())
}
bw.write(stringBuilder.toString())
bw.flush()
bw.close()
br.close()
}
private fun bfs(): String {
val arrayDeque = ArrayDeque<Int>()
arrayDeque.addLast(start)
state[start].value = 0
while(arrayDeque.isNotEmpty()){
val from = arrayDeque.removeFirst()
for(i in graph[from].indices){
val to = graph[from][i]
if(state[from].value == state[to].value) return "NO"
if(state[to].value == IS_NOT_SET) state[to].value = if(state[from].value == 1) 0 else 1
if(graph[to].isNotEmpty() && !state[to].isQueueAdded) {
state[to].isQueueAdded = true
arrayDeque.addLast(to)
}
}
}
return "YES"
}두 번째 실패
첫 번째 실패 이후 방향 그래프인 것을 깨닫고 인접 리스트의 양쪽에 모두 추가해주었다.
또한 정점과 연결된 그래프가 존재하지 않더라도 arrayDeque.add 를 진행해주었다.
/*
* 정점 - 1 ~ V 차례대로
* 각 테스트 케이스 첫줄 정점의 개수 V, 간선의 개수 E
* */
private const val IS_NOT_SET = -1
private lateinit var state: IntArray
private lateinit var graph: Array<MutableList<Int>>
fun `1707-이분 그래프`(){
val br = System.`in`.bufferedReader()
val bw = System.out.bufferedWriter()
val k = br.readLine().toInt()
val stringBuilder = StringBuilder()
repeat(k){
val (vertex, edge) = br.readLine().split(" ").map { it.toInt() }
var result = "NO"
graph = Array(vertex + 1){ mutableListOf() }
state = IntArray(vertex + 1){ IS_NOT_SET }
repeat(edge){
val token = java.util.StringTokenizer(br.readLine())
val from = token.nextToken().toInt()
val to = token.nextToken().toInt()
graph[from].add(to)
graph[to].add(from)
}
for(i in 0 until vertex){
// 연결된 정점이 존재하고, 시작 정점이 아직 설정되지 않았따면
if(graph[i].isNotEmpty() && state[i] == IS_NOT_SET) {
result = if(bfs(i)){
"YES"
} else{
"NO"
break
}
}
}
if(stringBuilder.isNotEmpty()) stringBuilder.append("\n")
stringBuilder.append(result)
}
bw.write(stringBuilder.toString())
bw.flush()
bw.close()
br.close()
}
private fun bfs(start: Int): Boolean {
val arrayDeque = ArrayDeque<Int>()
arrayDeque.addLast(start)
state[start] = 0
while(arrayDeque.isNotEmpty()){
val from = arrayDeque.removeFirst()
for(to in graph[from]){
if(state[to] == IS_NOT_SET){
state[to] = if(state[from] == 1) 0 else 1
arrayDeque.addLast(to)
} else if(state[from] == state[to]) return false
}
}
return true
}그러나 미연결 그래프이므로 시작점이 여러 곳일 수 있어 bfs 를 반복실행하는 때에, 정점과 연결된 그래프가 존재하는 경우에만 bfs() 를 실행하도록 설정하여 실패하였다.
또한 for(i in 0 until vertex) 를 보면 1-based Index Array 를 설정하였음에도 0 ~ vertex - 1 로 지정하여 범위 설정도 잘못하였다.
이후 풀이 성공 ... !!
안드로이드 개발자 Gyu 의 개발 블로그 !