백준 1175 - 배달 (Kotlin)

밷백준 1175 - 배달 (코틀린)

문제

어제 선물을 모두 포장한 민식이는 이제 선물을 배달하려고 한다.

민식이가 선물을 배달할 곳은 이 문제를 읽는 사람들이 앉아 있는 교실이다.

교실은 직사각형모양이고, 모두 같은 크기의 정사각형 블록으로 나누어져 있다.

입력으로 교실의 지도가 주어진다. 각각의 정사각형 블록은 다음과 같이 4가지 종류가 있다.

• S: 지금 민식이가 있는 곳이다. 이곳이 민식이가 배달을 시작하는 곳이고 1개만 있다.
• C: 민식이가 반드시 선물을 배달해야 하는 곳이다. 이러한 블록은 정확하게 2개 있다.
• #: 민식이가 갈 수 없는 곳이다.
• .: 민식이가 자유롭게 지나갈 수 있는 곳이다.

민식이가 한 블록 동서남북으로 이동하는데는 1분이 걸린다. 민식이는 네가지 방향 중 하나로 이동할 수 있으며, 교실을 벗어날 수 없다.
민식이가 선물을 배달해야 하는 곳에 들어갈 때, 민식이는 그 곳에 있는 사람 모두에게 선물을 전달해야 한다.

이 상황은 동시에 일어나며, 추가적인 시간이 소요되지 않는다.

민식이는 어느 누구도 자신을 보지 않았으면 하기 때문에, 멈추지 않고 매 시간마다 방향을 바꿔야 한다.

이 말은 같은 방향으로 두 번 연속으로 이동할 수 없다는 말이다.

민식이가 선물을 모두 배달하는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

 

---

입력

첫째 줄에 교실의 세로 크기 N과 가로 크기 M이 주어진다.

N과 M은 50보다 작거나 같은 자연수이다.

둘째 줄부터 N개의 줄에 교실의 지도가 주어진다.

 

---

출력

첫째 줄에 민식이가 선물을 모두 배달하는데 걸리는 시간의 최솟값을 출력한다. 만약 불가능 할 때는 -1을 출력한다.

 

---

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

---

해설

이번 문제는 너비 우선 탐색(BFS) 문제이다.

 

이번 문제는 이전에 풀었던 프로그래머스 - 경주로 건설과 유사한 문제이다.

 

기존의 BFS랑은 다르게 방문해야하는 위치가 2개이다.

또한 똑같은 방향으로 2번 이동할 수 없다.

 

우선 map 배열에 다음과 같은 값을 추가했다.

• . : 0으로 변환
• # : 1로 변환
• S : 2로 변환
• C : 3으로 변환
• C(두 번째) : 4로 변환

사실 문제를 다 풀고나서 굳이 Int 형으로 변환할 필요는 없단 걸 깨달았으나.. 늦었따..😫

 

대신 2개의 C를 다른 문자 또는 정수형으로 변환해줘야 후에 쉽게 처리할 수 있다.

 

아무튼 넘어가서 visited 를 5차원 배열로 만들어주었다.

visited[N][M][4][2][2] 이런식으로 만들어 주었다.

 

즉 (x, y, d, f1, f2) 로 만들어줬는데 이것이 의미하는 바는

d방향에서 접근한 (x, y)좌표는 C1, C2를 방문했다. (0이면 미방문, 1이면 방문)

 

그 후 완전탐색을 하며 f1, f2 == 1 가 될 때 까지 탐색한 후 출력하였다.

 

---

전체 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

private var N = 0
private var M = 0
private lateinit var map: Array<MutableList<Int>>
private val dx = intArrayOf(0, 1, 0, -1)
private val dy = intArrayOf(1, 0, -1, 0)
private var ans = -1

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (n, m) = br.readLine().split(" ").map { it.toInt() }
    var s = 0 to 0
    var sl = 3

    N = n
    M = m

    map = Array(n) { mutableListOf() }

    repeat(n) { idx ->
        val str = br.readLine()

        for (i in str.indices) {
            //이동 가능한 길
            if (str[i] == '.') {
                map[idx].add(0)
                //민식쨩이 서있는 위치
            } else if (str[i] == 'S') {
                map[idx].add(2)
                s = idx to i
                //이동 불가능한 위치
            } else if (str[i] == '#') {
                map[idx].add(1)
                //택배 배당해야하는 위치
            } else {
                map[idx].add(sl++)
            }
        }
    }

    bfs(s)
    println(ans)
}

private fun bfs(s: Pair<Int, Int>) {
    data class MN(val x: Int, val y: Int, val v: Int, val d: Int, val f1: Int, val f2: Int)

    var visited = Array(N) { Array(M) { Array(4) { Array(2) { Array(2) { false } } } } }
    val q: Queue<MN> = LinkedList()

    q.offer(MN(s.first, s.second, 0, -1, 0, 0))
    visited[s.first][s.second][3][0][0] = true

    while (q.isNotEmpty()) {
        var (x, y, v, d, f1, f2) = q.poll()

        if (f1 == 1 && f2 == 1) {
            ans = v
            return
        }

        for (i in 0..3) {
            val nx = x + dx[i]
            val ny = y + dy[i]
            var nf1 = f1
            var nf2 = f2

            if (d != i && nx in 0 until N && ny in 0 until M && map[nx][ny] != 1 && !visited[nx][ny][i][f1][f2]) {
                if (map[nx][ny] == 3) {
                    nf1 = 1
                }
                if (map[nx][ny] == 4) {
                    nf2 = 1
                }

                visited[nx][ny][i][f1][f2] = true
                q.offer(MN(nx, ny, v + 1, i, nf1, nf2))

            }
        }
    }
}

 

 

---

정답

 

프로그래머스의 경주로 건설 문제와 유사하다고 하여 시도하였으나 실패했따...

다른사람의 코드를 보고 풀었는데 그래도 나름 유사한 것 같긴하다..

사실 코드 자체는 정말 간단하다. 

최근 문제풀며 이런 접근방식을 자주 접하는데 아직까지는 그런 연습이 부족하다