[백준] 20055 - 컨베이어 벨트 위의 로봇

난이도 - G5

사용 개념 - 구현, 자료구조(Queue)

핵심 키워드 

 * 1. 로봇은 n-1위치에 존재할 때 내릴 수 있다면 무조건 내린다.

 * 2. 컨베이어 벨트의 작업 순서에 유의해야 한다.

          1) 컨베이어 벨트가 먼저 회전한다. 벨트 위에 로봇이 존재한다면 로봇을 포함하여 회전한다.

          2) 이후 로봇이 움직일 수 있다면 "먼저 들어온 로봇의 순서대로" 앞으로 1칸 이동한다.

          3) 이후 0번 인덱스에 존재하는 컨베이어 벨트의 내구도가 1보다 크고 로봇이 없다면, 로봇을 올리고 내구도를 1 감                소한다.

          4) 이 과정 속에서 로봇이 n-1에 존재한다면, 무조건 내린다.

* 3. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    static StringTokenizer st;
    static StringBuilder sb;
    static int n,m,k;
    static int[] conveyor;
    static Queue<Integer> q;
    public static void main(String[] args)throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        q = new ArrayDeque<>();
        conveyor = new int[n*2];
        int loop = 1;
        st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<conveyor.length; i++){
            conveyor[i] = Integer.parseInt(st.nextToken());
        }
        int[] isRobot = new int[n*2];
        while(true){
            moveConveyor(isRobot); // 1. 컨베이어 이동
            moveRobot(isRobot); // 2. 로봇 이동
            if(conveyor[0] > 0){ // 3. 0번 위치가 비어있다면 올리기.
                if(isRobot[0] != 1){
                    isRobot[0] = 1;
                    conveyor[0] --;
                    q.offer(0);
                }
            }
 
            int cnt = isEmpty(); // 4. 빈 컨베이어 체크
            if(cnt>=m)break;
            loop++;
        }
        sb = new StringBuilder();
        sb.append(loop);
        System.out.println(sb.toString());
    }
    static void moveRobot(int[] isRobot){
        int size = q.size();
        for(int i=0; i<size; i++){
            int index = q.poll();
            int now = (index+1)>=(n*2-1)?(index+1)%(n*2) : index+1;
            int next = (index+2)>=(n*2-1)?(index+2)%(n*2) : index+2;
            if(conveyor[next]>0){
                if(isRobot[next]==1){
                    q.offer(now);
                    continue;
                }
                conveyor[next]--;
                isRobot[now] = 0;
                if(next == n-1){
 
                }
                else{
                    isRobot[next] = 1;
                    q.offer(next);
                }
            }
            else{
                q.offer(now);
            }
        }
    }
    static int isEmpty(){
        int cnt =0 ;
        for(int i=0; i<conveyor.length; i++){
            if(conveyor[i]<=0){
                cnt++;
            }
        }
        return cnt;
    }
    static void moveConveyor(int[] isRobot){
        int last = conveyor[conveyor.length-1];
        boolean flag = false;
        if(isRobot[conveyor.length-1] == 1){
            flag = true;
            isRobot[conveyor.length-1]=0;
        }
        for(int i = conveyor.length-2; i>=0; i--){
            if(isRobot[i] == 1){
                if(i+1 == n-1){
                    isRobot[i]=0;
                    q.remove(i);
                }
                else{
                    isRobot[i+1] = 1;
                    isRobot[i] = 0;
                }
            }
            conveyor[i+1] = conveyor[i];
        }
        conveyor[0] = last;
        if(flag){
            isRobot[0] = 1;
        }
    }
}

 

어려웠던 점

- 로봇이 "먼저 들어온 순서"대로 처리하는 점이 생각보다 어려웠다. Queue의 선입선출 개념을 활용하여 로봇이 존재했던 Index를 Queue에 저장하여 해결하고자 하였는데, 로봇이 0번 인덱스에 저장되어도 "벨트 이동" + "로봇 이동"의 결과가 정상적으로 처리되면 해당 Index를 가공처리 해줘야 했다.