백준 6129번
https://www.acmicpc.net/problem/6129

문제

---

생각하기

---

• A에서 B로 가는 가장 방향을 적게 틀어서 갈 수 있는 길을 찾는 문제이다.
  • 방향을 트는 최소값을 답으로 내면 됨
• 다익스트라 문제인데 오랜만에 막혀서 힘들었다.
  

동작

    val isVisited = Array(N) { Array(N) { IntArray(4) { INF } } }

3차원 배열 isVisited 을 통해서 각 map에 4가지 방향 최소값을 갱신해가면서 답을 찾는다

코드

---

Kotlin

import java.io.*
import java.util.*

// input
private lateinit var br: BufferedReader

// variables
private var N = 0
private const val INF = Int.MAX_VALUE
private lateinit var startCoor: Coordinate
private lateinit var endCoor: Coordinate

private lateinit var map: Array<CharArray>
private val dirX = arrayOf(-1, 1, 0, 0) // 상 하 좌 우
private val dirY = arrayOf(0, 0, -1, 1)

private data class Coordinate(var x: Int, var y: Int, var beforeDir: Int)

fun main() {
    br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    input()

    bw.write(solve())
    bw.close()
} // End of main

private fun solve(): String {
    val sb = StringBuilder()

    sb.append(BFS(startCoor.x, startCoor.y))
    return sb.toString()
} // End of solve

private fun BFS(x: Int, y: Int): Int {
    val isVisited = Array(N) { Array(N) { IntArray(4) { INF } } }
    val dist = Array(N) { IntArray(N) { INF } }
    val que: Queue<Coordinate> = LinkedList()


    // 이전 방향을 기준으로 01이 되거나 23이 되거나 둘 중에 하나로 방향이 바뀌면 Count
    for (i in 0 until 4) {
        que.offer(Coordinate(x, y, i))
        isVisited[x][y][i] = 0
    }

    while (que.isNotEmpty()) {
        val pollCoor = que.poll()

        for (dir in 0 until 4) {
            if ((pollCoor.beforeDir == 0 && dir == 1) || (pollCoor.beforeDir == 1 && dir == 0)) {
                continue
            } else if ((pollCoor.beforeDir == 2 && dir == 3) || (pollCoor.beforeDir == 3 && dir == 2)) {
                continue
            }

            val nextX = dirX[dir] + pollCoor.x
            val nextY = dirY[dir] + pollCoor.y
            var curveCount = 1
            if (!rangeCheck(nextX, nextY) || map[nextX][nextY] == 'x') continue

            //같은 방향은 커브 증가 안함
            if (dir == pollCoor.beforeDir) curveCount = 0

            // 이전 커브 횟수 보다
            if (isVisited[pollCoor.x][pollCoor.y][pollCoor.beforeDir] + curveCount < isVisited[nextX][nextY][dir]) {
                isVisited[nextX][nextY][dir] = isVisited[pollCoor.x][pollCoor.y][pollCoor.beforeDir] + curveCount
                que.offer(Coordinate(nextX, nextY, dir))
            }
        }
    }

    var min = Int.MAX_VALUE
    for (i in 0 until 4) {
        min = Math.min(min, isVisited[endCoor.x][endCoor.y][i])
    }

    return min
} // End of BFS

private fun rangeCheck(nextX: Int, nextY: Int): Boolean {
    return nextX in 0 until N && nextY in 0 until N
} // End of rangeCheck

private fun input() {
    N = br.readLine().toInt()

    map = Array(N) { CharArray(N) }
    for (i in 0 until N) {
        val temp = br.readLine()

        for (j in 0 until N) {
            map[i][j] = temp[j]

            if (map[i][j] == 'A') {
                startCoor = Coordinate(i, j, 0)
            } else if (map[i][j] == 'B') {
                endCoor = Coordinate(i, j, 0)
            }
        }
    }
} // End of input