[BOJ20055 - Python] 컨베이어 벨트 위의 로봇

문제

---

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

길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 시계 방향으로 돌고 있다.

 

그림 상 1번 칸이 있는 위치가 로봇을 올리는 위치, N번 칸이 있는 위치가 로봇을 내리는 위치이다.

로봇이 내리는 위치에 도달하면 바로 즉시 컨베이어 벨트에서 내린다.

 

칸마다 내구도가 정해져 있으며, 로봇이 올라가는 순간 1만큼 감소한다.

 

컨베이어 벨트를 이용해 로봇들을 건너편으로 옮기는 과정에서 아래의 일들이 순서대로 일어난다.

 

1. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.
2. 가장 먼저 벨트에 올라간 로봇부터 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다.
3. 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다.
4. 내구도가 0인 칸의 개수가 K개 이상이라면 종료, 그렇지 않다면 1번으로 돌아간다.

로봇이 이동 가능한 조건은 1. 이동하려는 칸에 로봇이 없어야 하고, 2. 그 칸의 내구도가 1 이상이어야 한다.

 

가장 처음 수행되는 단계를 1번째 단계라고 했을 때

종료 시 몇 번째 단계가 진행 중이었는지를 구하는 것이 문제이다.

 

 

풀이

---

컨베이어 벨트가 한 칸씩 회전한다는 부분에서 양방향 큐(deque)가 떠올랐다.

from collections import deque

q = deque([ ... ])
q.appendleft(q.pop())

위처럼 deque로 회전하는 것을 구현할 경우

1. 로봇을 올리는 위치의 인덱스 :  0

2. 로봇을 내리는 위치의 인덱스 : N-1

이렇게 항상 고정되므로 로봇을 올리고 내릴 수 있는지를 쉽게 확인할 수 있다.

 

나는 아래의 두 리스트를 양방향 큐(deque)로 선언하였다.

1. robot : 로봇이 올라가 있는지 유무 (길이 : N)

2. A : 각 칸의 내구도 (길이 : 2N)

 

문제에 나와있는 대로 순서대로 구현해주면 되는데,

로봇이 내리는 위치에 도달하면 즉시 내린다는 것을 주의해야 한다.

 

구현 순서는 다음과 같다.

1. 벨트 회전 → 내리는 위치에서 로봇을 내릴 수 있는지 확인 후 내리기

2. 로봇 이동 → 내리는 위치로 로봇이 이동한 경우 내리기

3. 올리는 위치에서 로봇을 올릴 수 있는지 확인 후 올리기

4. 내구도가 0인 칸의 개수 확인 → K개 이상이라면 종료

 

 

코드

---

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())

robot = deque([False for _ in range(N)])  # 로봇 유무
A = deque(list(map(int, sys.stdin.readline().split())))  # 내구도

level = 0  # 단계

while True:
    level += 1

    # 1. 벨트 회전
    robot.appendleft(robot.pop())
    A.appendleft(A.pop())

    # 내리는 위치 : N-1
    if robot[N - 1]:
        robot[N - 1] = False

    # 2. 로봇 이동
    for i in range(N - 2, -1, -1):
        next = i + 1
        if robot[i] and not robot[next] and A[next] > 0:
            robot[i] = False
            if next != N - 1:  # 내리는 위치일 경우 로봇은 바로 내림
                robot[next] = True
            A[next] -= 1

    # 3. 올리는 위치 : 0
    if not robot[0] and A[0] > 0:
        robot[0] = True
        A[0] -= 1

    # 4. 내구도가 0인 칸의 개수가 K개 이상이라면 종료
    count = 0
    for i in range(2 * N):
        if A[i] == 0:
            count += 1
    if count >= K:
        break

print(level)