백준 12886 돌 그룹 Kotlin (bfs)

문제 출처 : https://www.acmicpc.net/problem/12886

12886번: 돌 그룹

문제

오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다.

강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다.

크기가 같지 않은 두 그룹을 고른다. 그다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.

A, B, C가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 주어진다. (1 ≤ A, B, C ≤ 500)

출력

돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력한다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

풀이

머리 좀 써야 하는 bfs 문제이다.

크기가 같지 않은 두 그룹을 골라서 연산을 진행하면, 작은 쪽에 X를 더하고, 큰 쪽에 X를 뺀다. 따라서 전체 합은 변하지 않음을 알 수 있다.

그렇다면 두 그룹을 골라서 연산을 할 때마다, 나머지 한 그룹은 연산한 두 그룹에 의해서 숫자가 자동으로 정해진다.

이를 이용해 방문체크 배열을 visited[][] 이차원 배열로 처리할 수 있다.

visited[i][j]에서 i값은 A그룹의 수, j값은 B그룹의 수를 의미한다.

그럼 visited의 사이즈는 어떻게 줘야 할까? 

499 + 498 + 500으로 최대 1501 주면 된다.

 

이후 bfs를 돌리면 되는데, bfs의 이동 경로는 다음과 같다.

A<B

B<A

A<C

C<A

B<C

C<B

이 6가지 경우로 A,B,C의 상태를 바꿔가며 visisted 체크하면서 bfs를 돌리면 된다.

 

코드

import java.util.*
val br = System.`in`.bufferedReader()

fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()
//fun Char.chToInt() = Character.getNumericValue()
fun chToInt(ch: Char) = Character.getNumericValue(ch)

data class State(
    val a: Int,
    val b: Int,
    val c: Int
)

val visited = Array(1501){BooleanArray(1501)}


fun move(cur: State,dir: Int): State{
    when(dir){
        0->{
            if(cur.a<cur.b){
                return State(cur.a*2, cur.b-cur.a, cur.c)
            }
        }
        1->{
            if(cur.a>cur.b){
                return State(cur.a-cur.b, cur.b*2, cur.c)
            }
        }
        2->{
            if(cur.b<cur.c){
                return State(cur.a, cur.b*2, cur.c-cur.b )
            }
        }
        3->{
            if(cur.b>cur.c){
                return State(cur.a, cur.b-cur.c, cur.c*2)
            }
        }
        4->{
            if(cur.a<cur.c){
                return State(cur.a*2,cur.b,cur.c-cur.a)
            }
        }
        else->{
            if(cur.a>cur.c){
                return State(cur.a-cur.c, cur.b, cur.c*2)
            }
        }
    }
    return cur
}

fun bfs(a: Int, b: Int, c: Int): Int{
    val q: Queue<State> = LinkedList()
    q.add(State(a,b,c))

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

        //종료 검사
        if(cur.a == cur.b && cur.a  == cur.c) return 1
        
        for(i in 0 until 6){
            val next = move(cur, i)
//            println(next)
            if(visited[next.a][next.b]) continue
            visited[next.a][next.b] = true
            q.add(next)
        }

    }

 return 0
}


fun main() = with(System.out.bufferedWriter()){

    //input
    val (a,b,c) = getIntList().also {
        if(it.sum()%3 !=0){
            write("0")
            close()
            return
        }
    }

    //solve
    visited[a][b] = true
    write("${bfs(a,b,c)}")

    close()
}