[BOJ/Java] 20055 : 컨베이어 벨트 위의 로봇

문제

www.acmicpc.net/problem/20055

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

 

풀이

주의해야 할 점은 이 컨베이어벨트는 위에서 바라본 방향이 아니라 옆에서 바라본 거라는 점이다. 정말 시키는 대로만 구현하면 되지만 처음에는 로직이 잘 이해가 안 가서 헤맸다.

컨베이어벨트는 다음의 순서를 반복한다.

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

 

각 단계별로 살펴보자. 

1. 벨트가 한 칸 회전한다

우선 컨베이어벨트는 n개짜리 윗부분과 n개짜리 아랫부분으로 나누어주었고 ArrayList를 사용해 컨베이어벨트가 회전하는 경우 맨앞과 뒤를 삭제하고 붙여넣기 쉽도록 했다. 

내구도의 값을 가지고 있는 컨베이어벨트가 회전한 뒤에는 rotateRobot() 메소드에서 컨베이어벨트가 로봇을 가지고 있는지에 대한 정보를 업데이트 해주어야 한다. (한 칸 씩 회전 방향으로 민다)

 

2. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다. 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.

내구도를 꼭 고려해주어야 하며, 윗부분 컨베이어벨트 중 내려가는 위치의 바로 옆에 있던 로봇이 내려가는 위치로 이동하는 경우, 로봇은 바로 내려오게 된다.

 

3. 올라가는 위치에 로봇이 없다면 로봇을 하나 올린다. 

'올라가는 위치에 로봇이 없다면' 이라는 말이 왜 있는지 모르겠다. 이 모호한 말때문에 컨베이어벨트 아래쪽에도 로봇이 있을 수 있다는 말인 줄 알았다. 컨베이어벨트 아래쪽에는 로봇이 있을 수 없기 때문에 올라가는 위치에는 로봇이 이미 있을 리가 없다. 올라가는 위치에 로봇이 없다면 보다는 '올라가는 위치의 내구도가 1 이상이라면'으로 해석하는 게 적절하다.

 

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

내구도가 0인 칸의 개수를 센 다음 K개 이상이면 while문을 종료하도록 구현한다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class BOJ20055 { //컨베이어 벨트 위의 로봇
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int n, k;
	static ArrayList<Integer> topBelt; //위쪽 컨베이어벨트
	static ArrayList<Integer> bottomBelt; //아래쪽 컨베이어벨트
	static boolean[] isRobot; //컨베이어벨트 위에 로봇이 있는지 (있으면 true)
	static int count;

	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(in.readLine(), " ");
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		topBelt = new ArrayList<Integer>();
		bottomBelt = new ArrayList<Integer>();
		
		st = new StringTokenizer(in.readLine(), " ");
		for(int i = 1; i <= n; i++) {
			topBelt.add(Integer.parseInt(st.nextToken()));
		}
		for(int i = n ; i > 0 ; i--) {
			bottomBelt.add(0, Integer.parseInt(st.nextToken()));
		}
		isRobot = new boolean[n];
		int step = 1;
		while(true) {
			//1. 벨트가 한 칸 회전한다
			rotateBelt();
			//2. 벨트 로봇이 이동할 수 있으면 이동한다
			moveRobot();
			//3. 로봇이 올라갈 수 있으면 올라간다
			if(topBelt.get(0) > 0) {//올라가는 위치의 내구도가 1이상이면 올린다
				isRobot[0] = true;
				topBelt.set(0, topBelt.get(0) - 1);	
			}
			//4. 내구도가 0인 칸의 개수가 k개 이상이면 과정을 종료한다
			if(count() >= k) break;
			step++;
		}
	
		System.out.println(step);
		
		
	}

	private static void rotateBelt() {// 컨베이어벨트 회전
		// 내구도 회전
		topBelt.add(0, bottomBelt.get(0));
		bottomBelt.remove(0);
		bottomBelt.add(topBelt.get(n));
		topBelt.remove(n);
		// 로봇위치가 컨베이어벨트와 함께 움직인다(이 때는 내구도 고려x)
		rotateRobot();
	}

	private static void rotateRobot() {//내구도 고려 x 그냥 한 칸씩만 로봇 위치 조정
		for(int i = n-2; i >=0; i--) {
			if(isRobot[i]) {
				isRobot[i+1] = true;
				isRobot[i] = false;
			}
		}
		isRobot[isRobot.length - 1] = false;//내려가는 위치에 있는 로봇은 내린다
	}
	
	private static void moveRobot() {//로봇이 스스로움직인다(다음 위치의 내구도 고려)
		for (int i = n - 2; i >= 0; i--) {
			if (isRobot[i] && !isRobot[i + 1] && topBelt.get(i + 1) > 0) {
				isRobot[i + 1] = true;
				isRobot[i] = false;
				topBelt.set(i + 1, topBelt.get(i + 1) - 1);
			}
		}
		isRobot[n - 1] = false;//내려가는 위치에 있는 로봇은 내린다

	}
	
	private static int count() {//컨베이어벨트 전체 중 내구도가 0인 칸의 개수를 return
		count = 0;
		for(int i = 0; i < n; i++) {
			if(topBelt.get(i) == 0) count++;
		}
		for(int j = 0; j < n; j++) {
			if(bottomBelt.get(j) == 0) count++;
		}
		return count;
	}
}

 

느낀점

• 시뮬레이션 문제인 만큼 기존의 배경지식이나 개인적 생각은 완전히 배제한 채로 정말 '문제에서 시키는 대로' 구현해야 한다. 문제를 처음 보고 컨베이어벨트의 작동 로직이 이상하다고 생각했다. 그런 생각 하지 말고 시키는 대로 구현이나 하자 .. !
• 디버깅의 중요성