[백준] 20055번 컨베이어 벨트 위의 로봇 (파이썬)

 

문제

 

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

 

 

 

정답 소스코드 (Python)

 

from collections import deque

n,k=input().split()
n,k=int(n),int(k)

field=deque()
field.extend(list(map(int,input().split())))

step=0
robot=deque()
robot.extend([False for i in range(n)]) #로봇이 있다면 true 없다면 false

while True:
    step+=1

    #1  회전

    field.rotate(1)
    robot.rotate(1)
    robot[-1]=False  # 회전 후 로봇 내리기

    #2  로봇이 움직일 수 있다면 움직이기

    for i in range(n-2,-1,-1):    #내리는 위치에 가까운 로봇부터 움직이기
        if robot[i] and not robot[i+1] and field[i+1]>=1:
            robot[i+1]=robot[i]
            robot[i]=False
            field[i+1]-=1
    robot[-1]=False  # 로봇 이동 후 로봇 내리기

    #3 로봇 올리기

    if field[0]>=1 and not robot[0]:
        robot[0]=True        #첫번째 칸이 0이아니라면 로봇 올리기
        field[0]-=1          #로봇 올려서 내구도 감소

    #4 종료 조건
    if field.count(0)>=k:break

print(step)

 

 

풀이  (Python)

 

 

이 문제는 구현 문제로서 구현난이도가 높지 않지만, 지문의 이해가 어려운 편이다. 조건들이 불 명확하며 까다롭기 때문이다. 심지어 질문게시판을 보게 되면 오히려 더 어렵게 느껴지는 경우가 생기게 된다.

 

 

Point 1)  기본 로직

 

지문에서 핵심적으로 봐야할 것은 컨베이어 벨트의 회전과 벨트 칸의 내구도, 로봇의 이동, 로봇을 올리는 위치, 내리는 위치 등이 있다. 지문에서 나열된 수행 방법은 아래와 같으며, 저 지문 그대로 해석해야만 문제풀이가 가능하다.

필자는 처음에 1번에서 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다는 부분에서 첫 시작 시에 로봇이 먼저 첫 번째 칸에 가있는지 아닌지 헷갈렸었다. 또한 로봇의 이동은 언제 하는지, 로봇이 마지막 칸에 도착하면 내구도를 깎고 벨트에서 내리는지 내구도를 깎지 않는지에 대한 의문들이 있었다. 오히려 고민을 할수록 문제의 늪에 빠져들고 있었다.

 

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

종료되었을 때 몇 번째 단계가 진행 중이었는지 구해보자. 가장 처음 수행되는 단계는 1번째 단계이다.

 

 

위의 단계를 요약하여 크게 4가지의 단계로 나누어 작성하였다. 

1. 컨베이어 벨트의 회전 / 회전 후 로봇이 n칸에 있다면 벨트에서 내리기

2. 로봇이 움직일 수 있다면 움직이기/ 움직임 이후 로봇이 n칸에 있다면 벨트에서 내리기 

3. 로봇을 1칸에 올리기/ 1칸의 내구도가 1 이상인 경우+ 로봇이 없는 경우

4. 종료 조건에 해당하는지 확인

 

위의 각 단계를 반복문으로 지속적으로 반복하도록 하였다.

 

 

 

Point 2) 파이썬의 deque의 rotate함수 활용

 

파이썬이라는 언어적 특성으로 인해 컨베이어 벨트의 회전을 굉장히 간단하게 구현할 수 있었다.

파이썬에서 덱(deque)의 자료구조의 활용은 collection 기본 라이브러리를 통해 리스트와 같이 구현할 수 있다.

from collections import deque
field=deque()

 

 

덱(deque)으로 구성된 자료구조의 경우 다양한 함수들이 있는데 extend를 통해 값을 추가하고, rotate를 통해 회전 시켰다.

rotate(1)은 오른쪽으로 회전하고 rotate(0)은 왼쪽으로 회전한다.

    field.rotate(1)
    robot.rotate(1)

 

 

 

 

문제의 구현난이도는 높지 않지만, 실질적인 지문 이해가 매우 어려운 문제였다고 볼 수 있다.