통나무 옮기기
[백준] 통나무 옮기기 -Kotlin풀이
https://www.acmicpc.net/problem/1938
통나무 옮기기
문제 설명
입력
첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다 (4<=N<=50).
이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다.
한 줄에 입력되는 문자열의 길이는 N이며 입력 문자 사이에는 빈칸이 없다. 통나무와 최종 위치의 개수는 1개이다.
출력
첫째 줄에 최소 동작 횟수를 출력한다. 이동이 불가능하면 0만을 출력한다.
입출력예
풀이
골드3 난이도를 가진 문제로 BFS, 시뮬레이션 문제다.
BFS탐색 문제를 풀 때 중요한 것이 어떤 데이터를 가지고 탐색할 것인가 이다.
통나무의 길이가 3이라서 3개의 좌표를 가지고 탐색할 수 도 있는데, 나는 그 중에 중심점 좌표만 가지고 탐색했다.
또 이 문제에서는 가로,세로로 돌리는 경우도 있기 때문에 가로인지 세로인지 그 상태를 저장도 해주어야 한다.
그리고 세로로 특정좌표를 방문했어도, 가로로도 한번 더 방문할 수 있게 처리를 해줘야한다.
나는 visited배열에 0,1,2,3 의 숫자를 사용하여 이를 처리했다.
그래서 Position 데이터 클래스를 만들어 중심점의 좌표, 몇번 이동 했는지, 그리고 가로인지 세로인지를 1,2로 표현하고 큐에 담아 탐색했다.
나의 코드는 다음과 같은 흐름을 가진다.
-
입력을 받으면서 통나무의 위치와 도착지점의 위치를 파악하고 가로인지 세로인지를 파악해준다.
(x값이 같으면 가로라고 판단했다) -
크게 가로와 세로로 나누고 상하좌우 4번의 이동이 가능한지 보고 이동시킨다.
간단하게 하는법은 없고 일일이 다 코드를 짜야하는 것 같다. -
가로일 경우 Y좌표가, 세로일 경우 X좌표가 1 과 n-2 사이에 있어야한다.
가로 상태일 경우 Y좌표(중심점의 좌표)가 0이면 중심점으로 부터 왼쪽에 있는 좌표는 -1이 되버리기 때문이다. -
이동하려는 곳에 1이 없어야한다. 이 때 상하, 좌우를 나눠서 처리해야한다.
가로 상태일 경우 위로 이동할 때는 좌표 3개를 봐야하고, 좌로 이동하면 좌표 1개를 봐야하기 때문이다. -
이동하려는 지점을 같은 상태로 탐색 하지 않았어야 한다(가로, 세로).
0이면 방문을 안한 상태라 가로,세로 다 탐색 가능하다.
1이면 가로로 탐색했다는 뜻으로 세로로 탐색 가능하다.
2이면 세로로 탐색했다는 뜻으로 가로로 탐색 가능하다.
3이면 가로,세로로 다 탐색했기 때문에 더 이상 탐색을 안해도 된다. -
탐색이 가능하다면 해당 지점을 탐색했다고 처리하고 큐에 넣는다.
0이면 1 또는 2로, 1 또는 2면 3으로 바꾸어준다. -
turnCheck 함수를 통해 회전이 가능한지 체크해준다( 중심점 기준으로 3X3영역에 1이 없는지).
범위 체크와 탐색 여부를 확인해주고 탐색이 가능하다면 큐에 넣는다. -
큐에 넣을때 목표지점인 goal과 중심점좌표와 가로,세로의 상태가 같으면 출력하고 return 해주었다.
찾지 못했으면 마지막에 0을 출력하고 끝난다.
시뮬레이션 문제 답게 뇌가 말랑말랑해지는 문제 였던거 같다..
풀고 보니까 코틀린으로는 딱 한분만 이 문제를 푸셨다.
코드 길이가 2배정도 짧아서 코드를 참고했다.
나는 탐색 여부를 0,1,2,3으로 했는데 3차원 배열로 처리를 하니까 훨씬 깔끔했고 set과 IntRange의 활용법까지 배우게 되었다.
tn*****21님의 코드를 참고한 코드는 맨 밑 “펼치기”에 있다😁
시간은 조금 더 걸리지만 가독성면에서 훨씬 좋다!!
답을 원하시는 분들은 그 코드를 보면 더 좋을거 같다.
코드
import java.util.ArrayDeque
fun main() { // 😁😊
data class Position(var x: Int, var y: Int, var cnt: Int, var garo: Int) //1가로,2세로
val br = System.`in`.bufferedReader()
val bw = System.out.bufferedWriter()
val n = br.readLine().toInt()
val arr = Array(n) { CharArray(n) }
val visited = Array(n) { IntArray(n) } // 0방문안함, 1가로로 방문함,2 세로로방문함, 3둘다 방문
val dx = intArrayOf(-1, 1, 0, 0)
val dy = intArrayOf(0, 0, -1, 1)
val dq = ArrayDeque<Position>()
val g = arrayListOf<Pair<Int, Int>>()
val s = arrayListOf<Pair<Int, Int>>()
for (i in 0 until n) { // 위치 파악
val x = br.readLine()
for (j in 0 until n) {
if (x[j] == 'B') {
g.add(Pair(i, j))
arr[i][j] = '0'
} else if (x[j] == 'E') {
s.add(Pair(i, j))
arr[i][j] = '0'
} else arr[i][j] = x[j]
}
}
// 가로,세로 파악
if (g[0].first == g[1].first) {
visited[g[1].first][g[1].second] = 1
dq.addLast(Position(g[1].first, g[1].second, 0, 1))
} else {
visited[g[1].first][g[1].second] = 2
dq.addLast(Position(g[1].first, g[1].second, 0, 2))
}
val goal = if (s[0].first == s[1].first)
Position(s[1].first, s[1].second, 0, 1)
else
Position(s[1].first, s[1].second, 0, 2)
fun turnCheck(x: Int, y: Int): Boolean {
for (i in x - 1..x + 1)
for (j in y - 1..y + 1)
if (arr[i][j] == '1')
return false
return true
}
while (dq.isNotEmpty()) {
val v = dq.removeFirst()
for (i in 0 until 4) {
val nextX = v.x + dx[i]
val nextY = v.y + dy[i]
if (v.garo == 1) { //가로
if (nextY !in 1 until n - 1 || nextX !in 0 until n) continue
else if ((i == 0 || i == 1) && (arr[nextX][nextY - 1] == '1' || arr[nextX][nextY] == '1' || arr[nextX][nextY + 1] == '1')) continue
else if ((i == 2 && arr[nextX][nextY - 1] == '1')||(i == 3 && arr[nextX][nextY + 1] == '1')) continue
else if (visited[nextX][nextY] == 0 || visited[nextX][nextY] == 2) {
if (goal.x == nextX && goal.y == nextY && goal.garo == 1) {
bw.write("${v.cnt + 1}")
bw.close()
return
}
visited[nextX][nextY]++ // 0이면 1, 2면 3
dq.addLast(Position(nextX, nextY, v.cnt + 1, 1))
}
} else { //세로
if (nextX !in 1 until n - 1 || nextY !in 0 until n) continue
else if ((i == 0 && arr[nextX-1][nextY] == '1')||(i == 1 && arr[nextX+1][nextY] == '1')) continue
else if ((i == 2 || i == 3) && (arr[nextX-1][nextY] == '1' || arr[nextX][nextY] == '1' || arr[nextX+1][nextY] == '1')) continue
else if (visited[nextX][nextY] == 0 || visited[nextX][nextY] == 1) {
if (goal.x == nextX && goal.y == nextY && goal.garo == 2) {
bw.write("${v.cnt + 1}")
bw.close()
return
}
visited[nextX][nextY] += 2 // 0이면 2, 1이면 3
dq.addLast(Position(nextX, nextY, v.cnt + 1, 2))
}
}
}
if (v.garo == 1 && v.x != 0 && v.x + 1 != n && turnCheck(v.x, v.y)) {
if (goal.x == v.x && goal.y == v.y && goal.garo == 1) {
bw.write("${v.cnt + 1}")
bw.close()
return
} else if (visited[v.x][v.y] != 2 && visited[v.x][v.y] != 3) {
visited[v.x][v.y] += 2
dq.addLast(Position(v.x, v.y, v.cnt + 1, 2))
}
} else if (v.garo == 2 && v.y != 0 && v.y + 1 != n && turnCheck(v.x, v.y)) {
if (goal.x == v.x && goal.y == v.y && goal.garo == 2) {
bw.write("${v.cnt + 1}")
bw.close()
return
} else if (visited[v.x][v.y] != 1 && visited[v.x][v.y] != 3) {
visited[v.x][v.y]++
dq.addLast(Position(v.x, v.y, v.cnt + 1, 1))
}
}
}
bw.write("0")
bw.close()
br.close()
}
😁펼치기/접기 버튼
import java.util.ArrayDeque
fun main() { // 😁😊
data class Position(var x: Int, var y: Int, var cnt: Int, var garo: Int) //0가로,1세로
val br = System.`in`.bufferedReader()
val bw = System.out.bufferedWriter()
val n = br.readLine().toInt()
val arr = Array(n) { br.readLine() }
val visited = List(2) { Array(n) { BooleanArray(n) } } // *[가로세로][x][y]로 구현
val dq = ArrayDeque<Position>()
var start = Position(0, 0, 0, 0)
var goal = Position(0, 0, 0, 0)
var find = false
for (i in 0 until n) { // *setOf로 가로 세로를 판별
for (j in 0 until n) {
if (j in 1 until n - 1 && setOf(arr[i][j - 1], arr[i][j], arr[i][j + 1]) == setOf('B'))
start = Position(i, j, 0, 0)
if (i in 1 until n - 1 && setOf(arr[i - 1][j], arr[i][j], arr[i + 1][j]) == setOf('B'))
start = Position(i, j, 0, 1)
if (j in 1 until n - 1 && setOf(arr[i][j - 1], arr[i][j], arr[i][j + 1]) == setOf('E'))
goal = Position(i, j, 0, 0)
if (i in 1 until n - 1 && setOf(arr[i - 1][j], arr[i][j], arr[i + 1][j]) == setOf('E'))
goal = Position(i, j, 0, 1)
}
}
fun moveCheck(xr: IntRange, yr: IntRange) = //*IntRange를 매개변수로 활용하여 이동가능한지 판단
xr.all { x -> yr.all { y -> x in 0 until n && y in 0 until n && arr[x][y] != '1' } }
fun doNext(x: Int, y: Int, cnt: Int, garo: Int, xRange: IntRange, yRange: IntRange) {
if (moveCheck(xRange, yRange) && !visited[garo][x][y]) { // *3차원배열로 탐색 가능 여부 판단
if (goal.x == x && goal.y == y && goal.garo == garo) {
bw.write("$cnt")
find = true
}
visited[garo][x][y] = true
dq.addLast(Position(x, y, cnt, garo))
}
}
visited[start.garo][start.x][start.y] = true
dq.addLast(start)
while (dq.isNotEmpty()) {
val v = dq.removeFirst()
if (v.garo == 0) { // 가로 세로를 나눠서 중심좌표를 넘기고, 1이 있는지 없는지를 판단할 x,y의 범위를 넘겨준다.
doNext(v.x - 1, v.y, v.cnt + 1, 0, v.x - 1..v.x - 1, v.y - 1..v.y + 1)
doNext(v.x + 1, v.y, v.cnt + 1, 0, v.x + 1..v.x + 1, v.y - 1..v.y + 1)
doNext(v.x, v.y - 1, v.cnt + 1, 0, v.x..v.x, v.y - 2..v.y - 2)
doNext(v.x, v.y + 1, v.cnt + 1, 0, v.x..v.x, v.y + 2..v.y + 2)
doNext(v.x, v.y, v.cnt + 1, 1, v.x - 1..v.x + 1, v.y - 1..v.y + 1)
} else {
doNext(v.x - 1, v.y, v.cnt + 1, 1, v.x - 2..v.x - 2, v.y..v.y)
doNext(v.x + 1, v.y, v.cnt + 1, 1, v.x + 2..v.x + 2, v.y..v.y)
doNext(v.x, v.y - 1, v.cnt + 1, 1, v.x - 1..v.x + 1, v.y - 1..v.y - 1)
doNext(v.x, v.y + 1, v.cnt + 1, 1, v.x - 1..v.x + 1, v.y + 1..v.y + 1)
doNext(v.x, v.y, v.cnt + 1, 0, v.x - 1..v.x + 1, v.y - 1..v.y + 1)
}
if (find) break
}
if (!find) bw.write("0")
bw.close()
br.close()
}