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

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

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

---

문제 해석

컨베이어 벨트와 로봇의 상호작용을 시뮬레이션하는 본 문제에서는 벨트가 원형으로 연결되어 있으며, 로봇이 올라갈 수 있는 위치와 올라갈 수 없는 위치로 구분되어 있다. 각 칸에는 내구도가 존재하며, 로봇이 칸 위로 이동하거나 벨트가 회전할 때마다 내구도가 감소된다. 주어진 조건 하에서 내구도가 0인 칸의 수가 특정 값(K) 이상이 될 때까지의 반복 과정을 통해 진행 단계 수를 출력하는 것이 문제의 목표이다.

풀이 과정

1. rotate() 함수를 통해 벨트를 한 칸 회전시킨다. 이 과정에서 벨트의 마지막 칸이 첫 칸으로 이동하며, 로봇들도 함께 이동한다. 로봇이 내리는 위치에 도달하면 로봇이 내려진다.
2. move() 함수는 모든 로봇을 검사하여, 이동 가능한 조건(다음 칸에 로봇이 없고, 내구도가 1 이상)을 만족하면 로봇을 한 칸 이동시키고, 해당 칸의 내구도를 1 감소시킨다.
3. put() 함수는 로봇을 올리는 위치(벨트의 시작점)에 내구도가 0이 아니면 로봇을 올리고 내구도를 감소시킨다.
4. count() 함수는 내구도가 0인 칸의 수를 세어, 그 수가 K 이상이면 시뮬레이션을 종료한다.

코드

package edu.ssafy.im.BOJ.Gold.G5.No20055;

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    private static int N;
    private static int K;
    private static int[] A;
    private static boolean[] visited;
    private static int ans;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        A = new int[2*N];
        visited = new boolean[2*N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < A.length; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        sol();
        sb.append(ans);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static void sol() {
        ans = 1;
        while(true) {
            rotate(); // 1번 동작
            move(); // 2번 동작
            put(); // 3번 동작
            if(count()) return; // 4번 동작
            ans++;
        }
    }

    // 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다.
    private static boolean count() {
        int cnt = 0;
        for (int i = 0; i < A.length; i++) {
            if(A[i] == 0) cnt++;
        }
        if (cnt >= K) return true;
        return false;
    }

    // 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다.
    private static void put() {
        if (A[0] != 0) {
            visited[0] = true;
            // 로봇을 올리는 위치에 올리거나 로봇이 어떤 칸으로 이동하면 그 칸의 내구도는 즉시 1만큼 감소한다.
            A[0]--;
        }
    }

    // 가장 먼저 벨트에 올라간 로봇 찾기
    private static int findLast() {
        for (int i = N-2; i >= 0; i--) {
            if(visited[i]) return i;
        }
        return -1;
    }

    private static void move() {
        int key = findLast();
        if (key == -1) return;
        for (int i = key; i >= 0; i--) { // 가장 먼저 벨트에 올라간 로봇부터,
            // 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
            if (visited[i] && !visited[i+1] && A[i+1] != 0) {
                visited[i] = false;
                visited[i+1] = true;
                // 로봇을 올리는 위치에 올리거나 로봇이 어떤 칸으로 이동하면 그 칸의 내구도는 즉시 1만큼 감소한다.
                A[i+1]--;
            }
        }
        // 언제든지 로봇이 내리는 위치에 도달하면 그 즉시 내린다.
        visited[N-1] = false;
    }

    // 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.
    private static void rotate() {
        int tmp = A[2*N-1];
        boolean tmp2 = visited[2*N-1];
        for (int i = A.length - 1; i > 0; i--) {
            A[i] = A[i-1];
            visited[i] = visited[i-1];
        }
        A[0] = tmp;
        visited[0] = tmp2;
        visited[N-1] = false;
    }
}

시간 복잡도 분석

본 코드의 시간 복잡도는 O(N*T)이다. 여기서 T는 시뮬레이션의 종료까지 걸리는 단계 수를 나타내며, 각 단계에서 벨트의 회전, 로봇의 이동 및 상태 체크가 모두 최대 O(N)의 시간이 소요된다.

느낀점

컨베이어 벨트와 로봇의 동시 관리가 요구되는 시뮬레이션 문제를 통해 복잡한 로직의 구현 및 상태 관리의 중요성을 배울 수 있었다. 시뮬레이션 유형의 문제 해결을 통해 문제 해석 및 해결 방안 도출 능력을 향상시킬 수 있었다.