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

20055 컨베이어 벨트 위의 로봇 - (https://www.acmicpc.net/problem/20055)

• 접근

  무슨 말인지 모르겠다.

  컨베이어 벨트를 이용해 로봇들을 건너편으로 옮기려고 한다. 로봇을 옮기는 과정에서는 아래와 같은 일이 순서대로 일어난다.
  1. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.
  2. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
  	2-1. 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
  3. 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다.
  4. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.
  종료되었을 때 몇 번째 단계가 진행 중이었는지 구해보자. 가장 처음 수행되는 단계는 1번째 단계이다.

  벨트가 각 칸 위에 있는 로봇과 한 칸 회전한다. 올리는 위치에서 로봇을 올리고 벨트가 회전하는게 아닌, 어떤 상황이든 막론하고 일단 벨트를 회전한다.가 중요한 포인트였다.
  회전을 하고, 벨트 위 로봇들을 한 칸 앞으로 이동할 수 있으면 한다. 단, 내리는 위치에서부터 올리는 위치 방향으로 로봇이 이동해야한다.가 두 번째 중요한 포인트였다.
  로봇을 올리거나, 로봇이 이동할 때 해당 칸의 벨트의 내구도는 1만큼 감소하고, 총 K개 이상의 내구도가 0인 벨트인 시점의 단계를 구하는 것이다.

• 풀이

  컨베이어 벨트를 먼저 구현한다. int[][] board = new int[2][N]
  로봇이 올라갔는지 체크하기 위한 로봇벨트도 구현한다. boolean[] robot = new boolean[N]
  결국 벨트가 회전하는게 중요하기에 spinning() 메서드 구현한다. (컨베이어 벨트, 로봇 벨트 둘다 회전 할 수 있게)

  벨트가 회전할 때, spinning()할 때 마다, 내구도가 0인 벨트의 갯수가 K개인지 확인

컨베이어 벨트, 로봇 벨트 회전 메서드

 static void spinning() {

        // 컨베이어 벨트 자체
        int first = board[0][N - 1];
        int last = board[1][0];

        // 상단
        for (int i = N - 1; i >= 1; i--) {
            board[0][i] = board[0][i - 1];
        }

        // 하단
        for (int i = 1; i < N; i++) {
            board[1][i - 1] = board[1][i];
        }

        board[0][0] = last;
        board[1][N - 1] = first;

        // 로봇 자체
        // 상단
        for (int i = N - 1; i >= 1; i--) {
            robot[i] = robot[i - 1];
        }
        robot[0] = false;
    }

내구도 0개 벨트 갯수 체크 메서드

static int check_strength() {
        int cnt = 0;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] == 0) {
                    cnt++;
                }
            }
        }
        return cnt;
    }

나머지 코드

public class BOJ20055 {
    static int N, K;
    static int[][] board;
    static boolean[] robot;
    static int time = 1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");

        N = Integer.parseInt(s[0]);
        int tmp = N;
        K = Integer.parseInt(s[1]);

        String[] ss = br.readLine().split(" ");
        board = new int[2][N];
        robot = new boolean[N];

        for (int i = 0; i < ss.length / 2; i++) {
            board[0][i] = Integer.parseInt(ss[i]);
        }
        for (int i = ss.length / 2; i < ss.length; i++) {
            board[1][tmp - 1] = Integer.parseInt(ss[i]);
            tmp--;
        }

        while(true) {
            // 1. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전
            spinning();
            time++;
//            print_convey();
//            print_robo();

            // 2. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
            //로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
            int idx = N - 2;
            while(idx >= 0) {
                if(robot[N - 1]) {
                    robot[N - 1] = false;
                }
                if (robot[idx] && board[0][idx + 1] >= 1 && !robot[idx + 1]) {
                    board[0][idx + 1] -= 1;
                    robot[idx + 1] = true;
                    robot[idx] = false;
                }
                idx--;
            }

            // 3. 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다.
            if (board[0][0] >= 1) {
                board[0][0] -= 1;
                robot[0] = true;
            }

            if (check_strength() >= K) {
                break;
            }

            // 4.
//            print_convey();
//            print_robo();
        }
        System.out.println(time - 1);
    }
}

• 결론

  이 문제는 알고리즘이 아닌 구현 문제이다.
  1. 문제 설명을 정확하게 이해해야 함.
  2. 순서에 따른 조건 체크 중요.
  3. 로봇 벨트를 따로 구현한 것 처럼 검증할 리스트 필요.