[java] 백준(BOJ) - 컨베이어 벨트 위의 로봇

문제

백준-컨베이어 벨트 위의 로봇
컨베이어 벨트의 내구도가 0인 칸의 개수가 K개 이상일 때 몇 번째 단계가 진행중이었는지 구하는 문제.

• 제한 사항
  컨베이어 벨트 길이 N : 2 <= N <= 100
  0인 칸의 개수 제한 K : 1 <= K <= 2N
  각 칸의 내구도 Ai : 1<= Ai <= 1,000

예시

이동방법을 헷갈려서 처음에 애를 썼다

여기서 1이 올라가는 위치이고, N이 내려가는 위치이다
컨베이어 벨트는 그림처럼 회전한다

여기서 컨베이어 벨트가 회전한다는게 1 ~ 2N까지고, (이건 맞고)
로봇도 1 ~ 2N까지 회전하는줄 알았다 (이건 아님, N에서 하차)
문제에서 이동 순서는 다음과 같다

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

N = 3이고, 1 2 3 4 5 6을 입력으로 받았다고 했을 때, 초기 컨베이어 벨트는 다음과같다

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

이런식으로 돌아간다.. 로봇이 전체가 아닌 N까지만 돌아감

풀이

컨베이어 벨트를 나타내는 2차원 배열을 map이라는 이름으로 잡았다
map[i][0]은 내구도를, map[i][1]은 내구도가 0이 되었을 때 카운트 했는지 여부를 주려고 넣었다

처음 1.벨트가 한 칸 회전한다에서 map도 돌리고, 로봇도 돌리는데 로봇이 N위치면 없앤다
나는 컨베이어 벨트 상태를 2차원 배열로 저장했으니 둘다([i][0], [i][1]) 옮겨야했다

2. 가장 먼저 올라간 로봇부터 이동한다에서 로봇을 옮길 때
로봇의 위치를 i로 잡고, 다음위치(i+1)가 N이면 로봇 제거
내구도가 0이면 그냥 두고, 내구도가 0보다 크면 이동한다

이 때 해당 칸의 내구도가 0이면서(map[i][0]==0) 카운트 한 적 없으면 (map[i][1]==0) 0인 칸 수를 저장하는 변수 cnt를 1 증가시킨다

이후 cnt >= K를 통해서 종료한다
매번 배열을 다 돌지않고 0의 갯수를 바로 확인하기 위해 cnt와 flag용(map[i][1])을 사용했다
굳이 int따로 안끼고 boolean 배열 하나 만들어도 될듯..

소스코드

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

public class Main {

	private static int K;
	private static int N;
	private static int[][] map;
	private static boolean[] robot;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		map = new int[N * 2][2];
		robot = new boolean[N];
		for (int i = 0; i < 2 * N; i++) {
			map[i][0] = Integer.parseInt(st.nextToken());
		}
		int cnt = 0;
		int time = 1;
		while (true) {
			// 벨트가 한칸 회전한다
			turnAroundMap();
			turnAroundRobot();
			// 가장 먼저 올라간 로봇부터 벨트가 회전하는 방향으로 한칸 이동할 수 있으면 이동한다
			// 이동시에는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아있어야한다
			for (int i = robot.length - 1; i > -1; i--) {
				if (robot[i]) {
					int nxt = i + 1;
					if(nxt==N) {
						robot[i]=false;
						continue;
					}
					if (nxt < N && !robot[nxt]) {
						if (map[nxt][0] > 0) {
							robot[nxt] = true;
							robot[i] = false;
							map[nxt][0]--;

							if (map[nxt][0] == 0 && map[nxt][1] == 0) {
								cnt++;
								map[nxt][1] = 1;
							}
						}
					}
				}
			}
			// 올라가는 위치에 로봇이 없으면 로봇을 하나 올린다
			if (!robot[0] && map[0][0] > 0) {
				map[0][0]--;
				robot[0] = true;
				if (map[0][0] == 0 && map[0][1] == 0) {
					cnt++;
					map[0][1] = 1;
				}
			}
			// 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다
			if (cnt >= K)
				break;
			time++;
		}
		// 끝
		System.out.println(time);
	}

	private static void turnAroundRobot() {
		for (int i = robot.length - 1; i > 0; i--) {
			robot[i] = robot[i - 1];
		}
		robot[0] = false;
	}

	private static void turnAroundMap() {
		int tmp1 = map[map.length - 1][0];
		int tmp2 = map[map.length - 1][1];
		for (int i = map.length - 1; i > 0; i--) {
			map[i][0] = map[i - 1][0];
			map[i][1] = map[i - 1][1];
		}
		map[0][0] = tmp1;
		map[0][1] = tmp2;
	}
}