백준 20055번 컨베이너 벨트 위의 로봇 (C++)

문제 링크 : www.acmicpc.net/problem/20055

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

이 문제는 구현 로직 자체가 어렵지 않다. 다만 언어시험이 아닌가 의심이 될 정도로 대충 읽었다가는 분명 틀릴 수 밖에 없는 문제였다.

해석을 대충하고 풀었던 탓에 테스트 케이스부터 실패를 겪었다. 

---

문제의 주의사항은 다음과 같다.

 

- 올라가는 위치와 내려가는 위치

: 올라가는 위치는 말 그대로 로봇을 새로 올라가는 위치이다. 내려가는 위치는 로봇을 땅으로 내려보내는, 즉, 아웃 시키는 과정이다.

파란색 : 올라가는 위치 빨간색 : 내려가는 위치

여기서 로봇을 내려보내는 과정이 중요한데, 컨베이너 벨트는 회전을 하므로 아래 두 과정에서 로봇을 아웃 시킬 수 있는지 판단을 해야한다. 

(1) 컨베이너 벨트가 회전하고 난 다음 내려가는 위치에 로봇이 있는가

(2) 회전을 마치고 로봇이 한 칸으로 이동할 수 있어서 이동하게 된 경우, 그 위치는 내려가는 위치인가

---

문제 풀이는 다음과 같다.

1. 배열의 값을 입력 받는다.

-> 배열의 값으로 주어지는 숫자들은 일렬로 1~2N까지 주어진다.

나는 2차원 배열로 저장했으며, 위의 그림과 똑같이 배치할 수 있도록 두 번째 행렬은 역으로 저장했다.

2. 배열이 아닌 로봇이 올라가는 위치와 로봇이 내려가는 위치를 회전시킨다. 

-> 배열을 하나하나 회전시키고 로봇이 올라가는 위치와 내려가는 위치를 고정시킬수도 있었겠지만, 어차피 컨베이너가 회전함과 동시에 로봇도 같이 회전한다. 때문에 나는 로봇이 올라가는 위치와 내려가는 위치만 회전시켰다. 

3. 로봇이 한 칸 이동할 수 있으면 이동한다. 

-> 이때 주의해야할 점이, 이동하기 이전에 2번의 회전을 통해서 재배열된 로봇이 내려가는 위치와 현재 로봇의 위치가 같을 경우, 해당 로봇을 무조건 아웃시켜야한다.

4. 로봇이 올라가는 위치에 새로운 로봇을 배치시키고, 내려가는 위치에 로봇이 있을 경우 아웃시킨다.

 

#include <iostream>
#include <vector>
using namespace std;
 
int n = 0, k = 0, arr[2][100] = { 0, }, ans = 0;
pair<int, int> new_robot = { 0,0 };
pair<int, int> out_robot;
bool r[2][100] = { false, }; // 로봇 여부
vector<pair<int, int>> v; // 로봇 위치를 담는 벡터

void Input() {
    for (int i = 0; i < n; i++) cin >> arr[0][i];
    for (int i = n - 1; i >= 0; i--) cin >> arr[1][i]; // 역으로 저장
}
 
void Rotate() {
    if (new_robot.first == 0) { // 윗줄
        if (new_robot.second == 0) { new_robot.first = 1; new_robot.second = 0; }
        else new_robot.second -= 1;
    }
    else { // 아랫줄
        if (new_robot.second == n - 1) { new_robot.first = 0; new_robot.second = n - 1; }
        else new_robot.second += 1;
    }
    if (out_robot.first == 0) { // 윗줄
        if (out_robot.second == 0) { out_robot.first = 1; out_robot.second = 0; }
        else out_robot.second -= 1;
    }
    else { // 아랫줄
        if (out_robot.second == n - 1) { out_robot.first = 0; out_robot.second = n - 1; }
        else out_robot.second += 1;
    }
}
 
void Move() {
    for (int i = 0; i < v.size(); i++) {
        int y = v[i].first, x = v[i].second;
		if(y==out_robot.first&&x==out_robot.second){
			r[y][x] = false;
			v.erase(v.begin()+i);
			i--;
			continue;
		}
        if (y == 0) { // 윗줄
            if (x == n - 1) {
                if (arr[1][n - 1] != 0 && !r[1][n - 1]) {
                    r[0][x] = false;
                    r[1][n - 1] = true;
                    arr[1][n - 1] -= 1;
                    if (arr[1][n - 1] == 0) k--;
                    v[i].first = 1, v[i].second = n - 1;
                }
            }
            else {
                if (arr[0][x + 1] != 0 && !r[0][x + 1]) {
                    r[0][x] = false;
                    r[0][x + 1] = true;
                    arr[0][x + 1] -= 1;
                    if (arr[0][x + 1] == 0) k--;
                    v[i].first = 0, v[i].second = x+1;
                }
            }
        }
        else { // 아랫줄
            if (x == 0) {
                if (arr[0][0] != 0 && !r[0][0]) {
                    r[1][x] = false;
                    r[0][0] = true;
                    arr[0][0] -= 1;
                    if (arr[0][0] == 0) k--;
                    v[i].first = 0, v[i].second = 0;
                }
            }
            else {
                if (arr[1][x - 1] != 0 && !r[1][x - 1]) {
                    r[1][x] = false;
                    r[1][x - 1] = true;
                    arr[1][x - 1] -= 1;
                    if (arr[1][x - 1] == 0) k--;
                    v[i].first = 1, v[i].second = x-1;
                }
            }
        }
    }
}

void RobotArrangement() {
    if (!r[new_robot.first][new_robot.second] && arr[new_robot.first][new_robot.second] > 0) { // 새 로봇 배치
        r[new_robot.first][new_robot.second] = true;
        arr[new_robot.first][new_robot.second] -= 1;
        v.push_back(make_pair(new_robot.first, new_robot.second));
        if (arr[new_robot.first][new_robot.second] == 0) k--;
    }
	for(int i=0; i<v.size(); i++){ // 내려가는 로봇 찾아내기
		if(v[i].first==out_robot.first&&v[i].second==out_robot.second){
			r[out_robot.first][out_robot.second] = false;
			v.erase(v.begin()+i);
			break;
		}
	}
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> k;
	out_robot = {0,n-1};
    Input();
    while (true) {
        Rotate(); // 로봇 배치 & 퇴장 위치 회전
        Move(); // 로봇 이동
        RobotArrangement(); // 새로운 로봇 배치 & 퇴장
        ans++;
        if (k <= 0) break;
    }
    cout << ans << "\n";
    return 0;
}