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

문제

---

생각하기

---

• BFS 문제이다.

• 문제를 풀이하자면, 출발지에서 거점을 한 군데 방문하고, 다시 집으로 돌아오는데, 최단거리로 돌아와야 한다.

  • 그래서 BFS를 사용
  • 처음에 물고기 서식지 거리 구해놓고 거기서 맨하탄으로 거리 계산했는데, 자꾸 오답이 나와서 뭐가 문제인가 했는데, 장애물이 있기 때문에 맨하탄은 사용할 수 없다는 부분을 놓치고 있었다.

동작

            if (nowCoor.fishCnt >= 1) {
                if (!ableCheck(nextX, nextY, isVisitedAfter)) continue
                next = map[nextX][nextY]
                when (next) {
                    'F' -> {
                        que.offer(Penguin(nextX, nextY, nowCoor.fishCnt + 1, nowCoor.time + 1))
                        isVisitedAfter[nextX][nextY] = true
                    }

                    'H' -> {
                        ans = nowCoor.time + 1
                        return ans
                    }

                    else -> {
                        que.offer(Penguin(nextX, nextY, nowCoor.fishCnt, nowCoor.time + 1))
                        isVisitedAfter[nextX][nextY] = true
                    }
                }
            } else {
                if (!ableCheck(nextX, nextY, isVisitedBefore)) continue
                next = map[nextX][nextY]

                when (next) {
                    'F' -> {
                        que.offer(Penguin(nextX, nextY, nowCoor.fishCnt + 1, nowCoor.time + 1))
                        isVisitedAfter[nextX][nextY] = true
                    }

                    'H' -> {
                        que.offer(Penguin(nextX, nextY, nowCoor.fishCnt, nowCoor.time + 1))
                        isVisitedBefore[nextX][nextY] = true
                    }

                    else -> {
                        que.offer(Penguin(nextX, nextY, nowCoor.fishCnt, nowCoor.time + 1))
                        isVisitedBefore[nextX][nextY] = true
                    }
                }
            }

isVisited를 생선서식지 방문 전과 방문 후 이렇게 2개를 만들어 두고 구분해서 BFS를 순회하도록 만들었다.

BFS특성상 S에서 F까지 자연스럽게 가장 최단거리로 갈 수 있고 F를 찍고 다시 H로 돌아간다.
여기서 H가 F로 가는 길에 있었을 수도 있기 때문에 이전에 사용하지 않은 isVsiited를 사용해야한다.

결과

코드

---

Kotlin

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

// input
private lateinit var br: BufferedReader

// variables
private var N = 0
private var M = 0
private lateinit var start: Penguin
private lateinit var map: Array<CharArray>

private var dirX = arrayOf(-1, 1, 0, 0)
private var dirY = arrayOf(0, 0, -1, 1)

private data class Penguin(var x: Int = 0, var y: Int = 0, var fishCnt: Int = 0, var time: Int = 0)

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()

    val ans = BFS()
    if (ans == -1) {
        sb.append(-1)
    } else {
        sb.append(ans)
    }
    return sb.toString()
} // End of solve()


private fun BFS(): Int {
    var ans = -1
    val que: LinkedList<Penguin> = LinkedList()
    que.offer(start)

    val isVisitedBefore = Array(N) { BooleanArray(M) }
    val isVisitedAfter = Array(N) { BooleanArray(M) }

    isVisitedBefore[start.x][start.y] = true

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

        for (i in 0 until 4) {
            val nextX = dirX[i] + nowCoor.x
            val nextY = dirY[i] + nowCoor.y
            var next = ' '

            if (nowCoor.fishCnt >= 1) {
                if (!ableCheck(nextX, nextY, isVisitedAfter)) continue
                next = map[nextX][nextY]
                when (next) {
                    'F' -> {
                        que.offer(Penguin(nextX, nextY, nowCoor.fishCnt + 1, nowCoor.time + 1))
                        isVisitedAfter[nextX][nextY] = true
                    }

                    'H' -> {
                        ans = nowCoor.time + 1
                        return ans
                    }

                    else -> {
                        que.offer(Penguin(nextX, nextY, nowCoor.fishCnt, nowCoor.time + 1))
                        isVisitedAfter[nextX][nextY] = true
                    }
                }
            } else {
                if (!ableCheck(nextX, nextY, isVisitedBefore)) continue
                next = map[nextX][nextY]

                when (next) {
                    'F' -> {
                        que.offer(Penguin(nextX, nextY, nowCoor.fishCnt + 1, nowCoor.time + 1))
                        isVisitedAfter[nextX][nextY] = true
                    }

                    'H' -> {
                        que.offer(Penguin(nextX, nextY, nowCoor.fishCnt, nowCoor.time + 1))
                        isVisitedBefore[nextX][nextY] = true
                    }

                    else -> {
                        que.offer(Penguin(nextX, nextY, nowCoor.fishCnt, nowCoor.time + 1))
                        isVisitedBefore[nextX][nextY] = true
                    }
                }
            }
        }
    }

    return ans
} // End of BFS

private fun ableCheck(nextX: Int, nextY: Int, isVisited: Array<BooleanArray>): Boolean {
    return nextX in 0 until N && nextY in 0 until M && !isVisited[nextX][nextY] && map[nextX][nextY] != 'D'
} // End of ableCheck

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

    map = Array(N) {
        br.readLine().toCharArray()
    }

    repeat(N) { x ->
        repeat(M) { y ->
            if (map[x][y] == 'S') {
                start = Penguin(x, y)
            }
        }
    }
} // End of input()