[ 알고리즘 ] 코딩 - 백준 20055번 - 컨베이어 벨트 위의 로봇.java

---

문제 링크

www.acmicpc.net/problem/20055

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

---

문제개요

BOJ 20055번 - (자바)컨베이어 벨트 위의 로봇 - 시뮬레이션

길이가 N인 기기를 길이 2N의 벨트가 돌고있다.

벨트 그림 예시

1번위치는 로봇을 올리는 곳이며 N위치에 도달하면 로봇은 땅으로 내려간다(대기열에서 제거)

무조건 1번에서 추가되고, N위치에서 제거된다

로봇을 건너편으로 넘기려고 할 때, 아래와 같은 일이 순서대로 일어난다.

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

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

위 1~4번 단계가 몇번 최대 몇번 수행되는지 알아내는 문제.

---

 

로직

Step 01. 모든 필요 정보를 입력받는다. 

Step 02. 1번 단계를 수행한다. 일단 벨트부터 이동시킨다. 벨트만 움직이므로 내구도에 영향은 없다. %연산을 이용해서 길이보다 커지면 다시 0번 인덱스부터 시작하게 하자.

Step 02-1. 벨트가 이동된 만큼 로봇도 이동시킨다. 이때 내려가는 위치를 잘 파악해서 Queue 관리를 한다. 벨트만 움직인 것이므로 내구도에 영향은 없다.

Step 03. Step 02에서 Queue의 길이가 변동되었을 수도 있으므로 size를 변경한 후, 전체 로봇을 이동시킨다. 이때 가려는 벨트의 내구도와 로봇이 있는 위치인지, 내려가는 위치인지 모두 판단해서 옮겨야한다. 만약 움직이지 못한다면 제자리의 정보를 Queue에 담아주자

Step 04. 가장 앞자리에 내구도와 로봇의 유무를 판단해서 로봇을 올려주고 내구도를 깍아주자

Step 05. Step 02 ~ Step 04를 반복하며 균열을 조사한다.

K보다 커지면 그때 종료하고 전체 수행된 단계를 출력하면 정답!

 

문제 이해하는데 너무 시간이 오래걸렸다....

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		
		int N = Integer.parseInt(input[0]);
		int K = Integer.parseInt(input[1]);
		
		int[] belt = new int[2*N];
		
		StringTokenizer stt = new StringTokenizer(br.readLine());
		for(int i = 0; i < 2*N; i++) {
			belt[i] = Integer.parseInt(stt.nextToken());
		} // input end
		
		// belt 정보 , crack 수, 벨트의 길이
		int res = process(belt, K, 2*N);
		
		System.out.println(res);
	}

	private static int process(int[] belt, int k, int size) {
		int crack = 0;
		int step = 0;
		int half = size/2; // 로봇이 내려가는 위치
		Queue<Integer> robot_queue = new LinkedList<>(); // 로봇이 순서대로 이동하므로 Queue를 이용
		boolean[] isrobot = new boolean[size]; // 현재 위치에 로봇이 있는지 판단
		
		while(crack < k) { // 망가진 벨트의 수가 k보다 작을때만 반복
			step++;
			int robot_cnt = robot_queue.size(); // size별로 수행
			// step 01. 벨트 한칸 회전
			int pre = belt[size-1]; // 가장 끝 
			for(int i = 0; i < size; i++) { // 한칸씩 앞으로 이동하며 갱신
				int cur = belt[i];
				belt[i] = pre;
				pre = cur;
			}
			
			// 로봇위치도 이동, 여기서 내려가는 위치라면 Queue에서 빼준다.
			int cnt = 0;
			while(robot_cnt > cnt) {
				cnt++;
				int pos = robot_queue.poll();
				isrobot[pos] = false;
				int next_pos = (pos+1)%size;
				if(next_pos == half) continue; // 내려가는 위치라면 큐에 넣지않는다.
				robot_queue.offer(next_pos);
				isrobot[next_pos] = true;
			}
			
			// 위에서 큐의 길이에 변동이 생겼을 수도 있다
			robot_cnt = robot_queue.size();
			// step 02. 이동 시킬 로봇이 있다면 이동시킨다. 여기서 내려가는 위치에 도착하면 Queue에서 뺀다.
			if(robot_cnt != 0) {
				cnt = 0;
				while(robot_cnt > cnt) {
					cnt++;
					int pos = robot_queue.poll();
					isrobot[pos] = false;
					int next_pos = (pos+1)%size;
					if(next_pos == half) continue;
					// 벨트의 내구도가 남아있고, 로봇이 없는 상태.
					if(belt[next_pos] != 0 && !isrobot[next_pos]) {
						if(--belt[next_pos] == 0) {
							++crack;
						}
						
						robot_queue.offer(next_pos);
						isrobot[next_pos] = true;
					} else { // 이동 불가능한 상태
						robot_queue.offer(pos);
						isrobot[pos] = true;
					}
				}
			}
			
			// step 03. 로봇을 하나 올린다. 0번 자리에 내구도가 남아있고, 로봇이 없는 경우
			if(belt[0] != 0 && !isrobot[0]) {
				robot_queue.offer(0);
				isrobot[0] = true;
				if(--belt[0] == 0) {
					++crack;
				}
			}
		}
		return step;
	}
}