[백준/구현] 20055번: 컨베이어 벨트 위의 로봇(골드5, python)

https://www.acmicpc.net/problem/20055

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

아이디어

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

위 본문 내용을 따라서 구현하면 된다.

 

벨트 회전 구현

dv = [(-1,0), (0,1), (1,0), (0,-1)]

def beltMove(belts,  N):
    queue = deque([(0, 0, belts[0][0])])
    belts[0][0] = belts[1][0]
    d = 1
    while queue:
        x, y, data = queue.popleft()

        if x == 1 and y == 0: continue

        for _ in range(4):
            nx, ny = x + dv[d][0], y + dv[d][1]
            if nx < 0 or nx >= 2 or ny < 0 or ny >= N:
                d = (d+1)%4
                continue

            queue.append((nx, ny, belts[nx][ny]))
            belts[nx][ny] = data
            break

시계방향으로 한바퀴 회전하게 된다.

 

벨트와 로봇이 함께 이동해야 하므로 벨트 이동 후 로봇도 이동해준다.

    beltMove(belts, N)
    robots.rotate(1)
    robots[N-1] = 0

로봇은 N(코드 상 N-1의 인덱스)에 도착하면 바로 빼주므로 0으로 변경해주었다.

 

로봇 이동 구현

def robotMove(robots, belts, N):
    queue = deque()

    for i in range(N-2, -1, -1):
        if robots[i] == 1:
            queue.append(i)

    while queue:
        y = queue.popleft()

        ny = y + 1

        if belts[0][ny] > 0 and robots[ny] == 0:
            belts[0][ny] -= 1
            robots[y] = 0
            robots[ny] = 1
            if ny == (N - 1): robots[ny] = 0

로봇만 이동하는 경우이다. 이동하려는 위치의 내구도가 0보다 크고, 이동하려는 위치에 다른 로봇이 없다면 이동하게 된다.

마찬가지로 로봇이 N-1에 도착하면 바로 나가므로 0으로 변경해주었다.

 

로봇 출발 구현

    if belts[0][0] > 0:
        belts[0][0] -= 1
        robots[0] = 1

만약 출발지의 내구도가 0보다 크면 로봇을 출발시킨다.

 

0의 갯수가 K 이상이면 종료

    if belts[0].count(0) + belts[1].count(0) >= K: break

0의 갯수가 k 이상이면 종료하고, 현재 단계를 반환해준다.

 

전체 코드

#python3는 시간초과 pypy3는 통과
from collections import deque
import sys
input = sys.stdin.readline

N, K = map(int, input().split())

tmp = list(map(int, input().split()))
belts = [[x for x in tmp[:N]], [x for x in tmp[-1:N-1:-1]]]
dv = [(-1,0), (0,1), (1,0), (0,-1)]

def beltMove(belts,  N):
    queue = deque([(0, 0, belts[0][0])])
    belts[0][0] = belts[1][0]
    d = 1
    while queue:
        x, y, data = queue.popleft()

        if x == 1 and y == 0: continue

        for _ in range(4):
            nx, ny = x + dv[d][0], y + dv[d][1]
            if nx < 0 or nx >= 2 or ny < 0 or ny >= N:
                d = (d+1)%4
                continue

            queue.append((nx, ny, belts[nx][ny]))
            belts[nx][ny] = data
            break


def robotMove(robots, belts, N):
    queue = deque()

    for i in range(N-2, -1, -1):
        if robots[i] == 1:
            queue.append(i)

    while queue:
        y = queue.popleft()

        ny = y + 1

        if belts[0][ny] > 0 and robots[ny] == 0:
            belts[0][ny] -= 1
            robots[y] = 0
            robots[ny] = 1
            if ny == (N - 1): robots[ny] = 0

count = 1
robots = [0] * N
robots = deque(robots)
while True:
    beltMove(belts, N)
    robots.rotate(1)
    robots[N-1] = 0

    robotMove(robots, belts, N)

    if belts[0][0] > 0:
        belts[0][0] -= 1
        robots[0] = 1

    if belts[0].count(0) + belts[1].count(0) >= K: break
    count += 1

print(count)