<백준> 컨베이어 벨트 위의 로봇(Gold 5)

[백준]

20055번: 컨베이어 벨트 위의 로봇

[깃허브]

ForCodeKata/baekjoon 문제집/컨베이어 벨트 위의 로봇 at main · heesoo-park/ForCodeKata

제출결과

---

진짜 문제를 이해하는게 어려웠던 문제였다...

진짜 계속 삽질을 하면서도 삽질인지 모른채 계속 시간을 부었다.

 

처음에 나는 문제를 어떻게 이해했냐면

컨베이어벨트가 계속 원형으로 회전하고 그 위에 로봇이 계속 쌓인다.

 

지금 보니 정말 이상하게 이해했었다.

내리는 위치에 대해서는 전혀 고려하지 않았기 때문이다...

그래서 계속 돌면서 로봇이 섞이니까 BFS도 써야하나 하면서 대입하고 그랬다...ㅎ

그런데 이렇게 이해하게 된 거는 원형으로 회전한다는 것 때문이었다.

 

이후에 컨베이어 벨트는 그렇게 돌지만 로봇은 N의 위치에서 뺀다는 걸 깨닫고 나서야 정말 이상하게 이해했음을 깨달았다.

컨베이어 벨트 절반에서만 로봇이 한쪽에서 반대쪽으로 이동하고 나머지 절반은 그저 컨베이어 벨트만 이동하는 거다..!

문제 조건을 해석하면 다음과 같아진다.

1. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.
   → 컨베이어 벨트가 회전하고 로봇도 회전방향대로 1칸씩 이동한다.(이 때 내리는 위치에 로봇이 있다면 내려줘야한다.)
2. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.(로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.)
  → 로봇만 회전방향대로 1칸씩 이동한다.(이 때 내리는 위치에 로봇이 있다면 내려줘야한다.)
3. 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다.
  → 올리는 위치의 내구도를 확인하고 로봇을 올린다.
4. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.
  → 컨베이어 벤트의 내구도 0인 칸의 개수 확인하고 종료 or 처음부터 반복

 

간단하게 말하면 사이클 한 번을 반복할 때 컨베이어벨트는 1번, 로봇은 2번을 움직이는 것이다.

로봇이 2번 움직이니까 내리는 위치에서 로봇을 내리는 것에 대한 코드는 2번 체크를 해야한다.

한 번 문제 이해가 뚫리고 나니까 코드는 쉽게 접근할 수 있었다.

구현 문제고 알고리즘 자체는 어렵지 않았기 때문이다.

 

문제 이해가 중요하다는 걸 깨닫는 문제....이지만 설명이 좀 그렇지 않나요?

 

해당 방법으로 작성한 코드는 다음과 같다.

fun main() = with(System.`in`.bufferedReader()) {
    val (n, k) = readln().split(' ').map { it.toInt() }
    // 컨베이어 벨트의 내구도를 저장하는 변수
    val conveyorBelt = readln().split(' ').map { it.toInt() }.toMutableList()
    // 현재 로봇의 위치를 저장하는 변수
    val visited = Array(n * 2) { false }
    var result = 0

    while (true) {
        // 한 사이클마다 단계 1씩 상승
        result++

        // 단계 1. 컨베이어벨트와 로봇 회전방향으로 한칸씩 움직이기
        val tempBelt = conveyorBelt[n * 2 - 1]
        val tempVisit = visited[n * 2 - 1]
        for (i in n * 2 - 1 downTo 1) {
            conveyorBelt[i] = conveyorBelt[i - 1]
            visited[i] = visited[i - 1]
        }
        conveyorBelt[0] = tempBelt
        visited[0] = tempVisit

        // 내리는 위치에 로봇이 있다면 내리기
        if (visited[n - 1]) {
            visited[n - 1] = false
        }

        // 단계 2. 로봇만 따로 조건에 맞춰 회전방향으로 한칸씩 움직이기
        for (i in n - 2 downTo 0) {
            if (!visited[i]) continue

            if (conveyorBelt[i + 1] > 0 && !visited[i + 1]) {
                conveyorBelt[i + 1]--
                visited[i] = false
                visited[i + 1] = true
            }
        }

        // 내리는 위치에 로봇이 있다면 내리기
        if (visited[n - 1]) {
            visited[n - 1] = false
        }

        // 단계 3. 올리는 위치가 비어있다면 로봇을 올리기
        if (conveyorBelt[0] > 0 && !visited[0]) {
            conveyorBelt[0]--
            visited[0] = true
        }

        // 단계 4. 내구도가 0인 칸의 개수가 k개를 넘을 시 종료
        if (conveyorBelt.count { it == 0 } >= k) break
    }

    println(result)
}

 

참고)

https://devyeonnn.tistory.com/3