백준 1525 퍼즐 Kotlin (bfs)

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

1525번: 퍼즐

문제

3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다.

1	2	3
4	5	6
7	8

어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 다음의 예를 보자.

1		3
4	2	5
7	8	6

1	2	3
4		5
7	8	6

 

1	2	3
4	5
7	8	6

1	2	3
4	5	6
7	8

가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오.

입력

세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.

출력

첫째 줄에 최소의 이동 횟수를 출력한다. 이동이 불가능한 경우 -1을 출력한다.

알고리즘 분류

• 그래프 이론
• 자료 구조
• 그래프 탐색
• 너비 우선 탐색

메모리 제한

• Java 8: 256 MB
• Java 8 (OpenJDK): 256 MB
• Java 11: 256 MB
• Kotlin (JVM): 256 MB

풀이

재밌는 bfs 문제이다!

아이디어가 필요한 문제인데,

bfs라 하면 보통 방문 체크를 통해 재방문을 없애고, 아직 방문하지 않은 상태만 방문한다.

이 문제에선, 3x3 표의 상태를 통해 방문 체크한다.

예를 들어, 

1 0 3

4 2 5

7 8 6

이 현재 표의 상태라고할 때,

"103425786"처럼

이를 1차원으로 문자열을 이용해 나타낼 수 있다.

이 상태에서 방문 가능한 상태는 0의 상하좌우 중 이동 가능한 좌표인 빨간색 부분과 swap한 상태이다.

한 번의 이동으로 방문 가능한 상태는

"013425786"

"130425786"
"123405786"

이 된다.

문자열로 저장된 표의 상태를 set에 저장하고, set을 검사함으로써 방문 처리, 확인을 할 수 있다.

 

0의 이동도 어렵지 않다.

2차원 좌표에서 인접 4방향에서 nextR과 nextC를 구하고,

nextR*3 + nextC는 곧 문자열에서의 0이 이동할 인덱스가 된다. 

 

코드

//코드3 : 좌표 이동 방식 변경(nr,nc구해서 문자열 인덱스로 변)
import java.util.*
val dirXY = arrayOf(arrayOf(0,1),arrayOf(0,-1),arrayOf(1,0),arrayOf(-1,0))
//val dir = arrayOf(1,3,-1,-3)
val br = System.`in`.bufferedReader()
val visited = mutableSetOf<Int>()
fun bfs(input : String) : Int{
    //pair.first = 상태, pair.second = 이동횟수
    val q : Queue<Pair<String,Int>> = LinkedList<Pair<String,Int>>()
    q.add(Pair(input,0))
    visited.add(input.toInt())
    while(q.isNotEmpty()){
        val cur = q.poll()
        val curIdx = cur.first.indexOf('0')
        val cr = curIdx/3
        val cc = curIdx%3
        if (cur.first == "123456780") return cur.second
        for (j in 0 until 4) {
            val nr = cr + dirXY[j][0]
            val nc = cc + dirXY[j][1]
            //그래프 벗어나면 스킵
            if(nr !in 0 until 3 || nc !in 0 until 3) continue
            //nr,nc로 문자열에서 0의 인덱스 구하기
            val nextIdx = nr*3+nc
            var nextState = cur.first
            var temp = nextState.toCharArray()
            //swap
            temp[curIdx] = temp[nextIdx].also { temp[nextIdx] = temp[curIdx] }
            nextState = String(temp)
            if (visited.contains(nextState.toInt())) continue
            q.add(Pair(nextState, cur.second+1))
            visited.add(nextState.toInt())
        }
    }
    return -1
}
fun main() = with(System.out.bufferedWriter()){
    var input = (br.readLine()+br.readLine()+br.readLine()).replace(" ","")
    write("${bfs(input)}")
    close()
}