백준 1525 퍼즐 Kotlin (bfs)

백준 1525 퍼즐 Kotlin (bfs)

반응형

문제 출처 : https://www.acmicpc.net/problem/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() fun bfs(input : String) : Int{ //pair.first = 상태, pair.second = 이동횟수 val q : Queue> = LinkedList>() 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() }

반응형

from http://ongveloper.tistory.com/390 by ccl(A) rewrite - 2021-12-20 14:27:47