백준 20055. 컨베이어 벨트 위의 로봇

백준 20055. 컨베이어 벨트 위의 로봇

구현 및 시뮬레이션 문제

문제가 굉장히 길지만 잘 읽으면서 하나씩 구현해나가면 된다

---

문제 분석

• 길이가 N인 컨베이어 벨트, 위 아래로 감싸므로 전체 길이는 2N이다

• 아래 그림과 같이 1부터 2N까지 번호가 매겨져있음

• 벨트가 회전하면 한칸씩 시계방향으로 이동한다

  • 1번부터 2N-1번까지의 칸은 다음 번호의 칸이 있는 위치로 이동하고, 2N번 칸은 1번 칸의 위치로 이동한다

• 각 벨트에는 내구도가 있다. A_i로 표시함

• 1번이 있는 위치를 “올리는 위치”, N이 있는 위치를 “내리는 위치”라고 한다

• 벨트 위에 로봇을 올린다

• 로봇은 “올리는 위치(1)”에만 올릴 수 있고, 언제든 “내리는 위치”에 도달하면 그 즉시 내린다

• 로봇은 컨베이어 벨트 위에서 스스로 이동할 수 있다.

• 로봇을 올리는 위치에 올리거나, 어떤 칸으로 이동하면 그 칸의 내구도는 즉시 1만큼 감소한다

• 컨베이어 벨트를 이용해 로봇들을 건너편으로 옮기려 할 때, 다음과 같은 과정이 일어난다

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

• 종료되었을 때, 몇 번째 단계가 진행중이였는지 출력하는 프로그램을 작성하기

입력

첫째 줄에 N, K, 둘째줄에 A_1, A_2, …, A_(2N)이 주어진다

출력

몇번째 단계가 진행중이였는지 출력한다

예제분석

3 2
1 2 1 2 1 2

N은 3, K는 2

초기 컨베이어 벨트 상태는 다음과 같다

1 2 3
6 5 4

1 2 1 
2 1 2

1단계:

1. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다 -> 벨트가 회전하면 다음과 같다. 아직 올라간 로봇이 없으므로 로봇은 처리하지 않는다

2 1 2 
1 2 1

1. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다. -> 마찬가지로 로봇이 없음

2. 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다. -> 현재 “올리는 위치”의 내구도는 2이므로, 로봇을 올릴 수 있다. 로봇을 올리고, 내구도를 1 감소시킨다

R
1 1 2 
1 2 1

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

2단계:

1. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다 -> 벨트 전체가 회전하면서 위에 있는 로봇과 함께 움직인다

  R
1 1 1 
2 1 2

1. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다. -> 가장 먼저 올라간 로봇부터, 시계방향으로 한칸씩 이동하고, 해당 칸의 내구도를 1 감소시킨다

    R
1 1 0 
2 1 2

-> 로봇이 “내리는 위치”에 도달했으므로 바로 내린다

1 1 0 
2 1 2

1. 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다. -> 현재 “올리는 위치”의 내구도는 1이므로, 로봇을 올릴 수 있다. 로봇을 올리고, 내구도를 1 감소시킨다

R
0 1 0 
2 1 2

1. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다. -> 내구도가 0인 칸의 개수가 2개이므로 종료한다. 현재 2단계이므로 2를 출력 후 종료한다

---

알고리즘

문제에 직접적으로 어떤 과정이 일어나있는지를 적어줬으므로 이를 바탕으로 구현함

1. N,K와 내구도 입력받기
2. 다음 과정을 계속 반복한다
	2-1. 벨트의 회전
		- 벨트를 시계방향으로 회전하면서, 로봇도 한칸씩 움직인다
	2-2. 로봇의 이동
		- 로봇이 시계방향으로 한칸씩 움직인다
	2-3. 로봇 적재
		- "올리는 위치"에 로봇을 적재한다
	2-4. 내구도 확인
		- 내구도가 0인 벨트의 개수가 K개 이상이면 종료한다

특히 언제 내구도가 닳는지를 잘 확인해야한다

1. 로봇을 올릴 때
2. 로봇이 이동할 때

또한, 2-2에서 로봇이 이동할 때, 언제 이동이 불가능한지도 잘 확인해야한다

1. 로봇이 이동하려는 다음 칸에 다른 로봇이 있을때
2. 혹은 내구도가 0이라도 이동이 불가능할 때

이런 세부사항들을 잘 체크하면서 구현하면 된다

---

소스코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, K;
vector<int> belt_durability;
vector<bool> is_robot_here;

void Input() {
	freopen("input.txt", "r", stdin);
	cin >> N >> K;
	belt_durability.resize(2 * N);
	is_robot_here.resize(2 * N);
	for (int i = 0; i < 2 * N; i++) {
		cin >> belt_durability[i];
	}
}

void DebugPrint() {
	for (int e : belt_durability) {
		cout << e << " ";
	} cout << '\n';
}

// 1. 벨트를 회전시키는 함수
void RotateBelt() {
	// 벨트 전체 오른쪽으로 한칸 회전
	rotate(belt_durability.begin(), belt_durability.end() - 1, belt_durability.end());

	// 로봇도 오른쪽으로 한칸 회전
	rotate(is_robot_here.begin(), is_robot_here.end() - 1, is_robot_here.end());

	// 로봇이 "내리는 위치"에 도달한 경우 내린다
	if (is_robot_here[N - 1]) {
		is_robot_here[N - 1] = false;
	}
}

// 2. 벨트 위의 로봇들이 벨트 방향으로 이동하는 함수
void MoveRobots() {
	// 벨트 위에서 로봇들이 벨트 방향으로 한칸씩 이동하면서 내구도를 까먹음
	for (int i = N - 2; i >= 0; i--) {
		if (is_robot_here[i] == false) continue; // 현재 칸에 로봇 없음

		// 로봇이 있다면, 다음칸으로 이동할 수 있는지 체크한다
		if (is_robot_here[i + 1] == true) continue; // 이미 로봇이 있는 경우 이동불가
		if (belt_durability[i + 1] == 0) continue; // 벨트 내구도가 0인 경우 이동불가
			
		// 이상없다면 이동 가능
		is_robot_here[i] = false;
		is_robot_here[i + 1] = true;
		belt_durability[i + 1]--;

		// 이동한 위치가 "내리는 위치"라면
		if (i + 1 == N - 1) {
			is_robot_here[i + 1] = false;
		}
			

	}
}

// 3. "올리는 위치"에 로봇을 올리는 함수
void LoadRobot() {
	// 올릴 수 없는 경우 리턴
	if (belt_durability[0] == 0 || is_robot_here[0] == true) {
		return;
	}
		
	is_robot_here[0] = true;
	belt_durability[0]--;
}

// 4. 전체 벨트의 내구도 확인
bool CheckBelts() {
	int broken_belts = 0;
	for (int i = 0; i < 2 * N; i++) {
		if (belt_durability[i] == 0) {
			broken_belts++;
		}
	}
	if (broken_belts >= K) {
		return true;
	}
	else {
		return false;
	}
}

int main() {
	Input();
	
	int steps = 1;
	while (true) {
		RotateBelt();

		MoveRobots();

		LoadRobot();

		if (CheckBelts() == true) {
			break;
		}
		steps++;
	}
	cout << steps;

	return 0;
}