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

문제

---

생각하기

---

• BFS 문제이다

  • 방문 여부를 처리하는 isVisited 배열을 방향까지 고려하여 3차원으로 생성하여야 한다.

  • 2가지 명령어에 대응하여야 한다.

    • 이동, 방향 전환

동작

결과

코드

---

Kotlin

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

// input
private lateinit var br: BufferedReader

// variables
private var M = 0
private var N = 0

private val dirX = intArrayOf(0, 0, 1, -1) // 동 서 남 북
private val dirY = intArrayOf(1, -1, 0, 0)
private lateinit var map: Array<IntArray>

private lateinit var start: Coordinate
private lateinit var end: Coordinate

private data class Coordinate(var x: Int, var y: Int, var dir: Int, var orderCount: 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())
    return sb.toString()
} // End of solve()

private fun BFS(): Int {
    val que = LinkedList<Coordinate>()
    val isVisited = Array(M) { Array(N) { BooleanArray(4) } }
    que.offer(start)

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

        if (now.x == end.x && now.y == end.y && now.dir == end.dir) {
            return now.orderCount
        }

        // 명령 1 : Go k : 1, 2, 3 만큼 향하고 있는 방향으로 이동
        for (i in 1..3) {
            val nextX = now.x + dirX[now.dir] * i
            val nextY = now.y + dirY[now.dir] * i

            if (!isAbleCheck(nextX, nextY)) break // 진행이 불가능한 방향일 경우 더 이상 앞으로 나아가지 않음
            if (isVisited[nextX][nextY][now.dir]) continue // 이미 방문한 곳은 통과

            isVisited[nextX][nextY][now.dir] = true
            que.offer(Coordinate(nextX, nextY, now.dir, now.orderCount + 1))
        }

        // 명령 2 : Turn dir : 같은 자리에서 왼쪽 오른쪽으로 90도 만큼 회전한다.
        for (i in 0 until 4) {
            // 같은 방향은 skip
            if (i == now.dir) continue
            // 서로 반대되는 방향일 경우 skip
            if ((i == 0 && now.dir == 1) || (i == 1 && now.dir == 0) || (i == 2 && now.dir == 3) || (i == 3 && now.dir == 2)) continue
            if (isVisited[now.x][now.y][i]) continue

            isVisited[now.x][now.y][i] = true
            que.offer(Coordinate(now.x, now.y, i, now.orderCount + 1))
        }
    }

    return 0
} // End of BFS()

private fun isAbleCheck(nextX: Int, nextY: Int): Boolean {
    return nextX in 0 until M && nextY in 0 until N && map[nextX][nextY] == 0
} // End of isAbleCheck()

private fun input() {
    StringTokenizer(br.readLine()).run {
        M = nextToken().toInt()
        N = nextToken().toInt()
    }

    map = Array(M) {
        StringTokenizer(br.readLine()).run {
            IntArray(N) {
                nextToken().toInt()
            }
        }
    }

    StringTokenizer(br.readLine()).run {
        start = Coordinate(
            nextToken().toInt() - 1,
            nextToken().toInt() - 1,
            nextToken().toInt() - 1,
            0
        )
    }

    StringTokenizer(br.readLine()).run {
        end = Coordinate(
            nextToken().toInt() - 1,
            nextToken().toInt() - 1,
            nextToken().toInt() - 1,
            0
        )
    }
} // End of input()