[문제 풀이] 백준 20055번 컨베이어 벨트 위의 로봇 JAVA

문제

  문제접근 방법   

해당 문제는 컨베이어 벨트의 길이 N과 종료조건인 내구도가 몇개가 0이어하는지의 K가 주어지고 컨베이어 벨트의 각각의 칸의 내구도가 주어진다. 컨베이어 벨트는 위와 아래 각각 N의 길이라 총길이는 2N이며 로봇을 벨트에 순서에 맞게 올리고 벨트 끝으로 옮기려한다. 이때 아래 단계에 맞춰 진행한다고 할때 몇번째 진행중일때 종료되는지를 출력하는 문제이다.

각각의 단계는 다음과 같다.

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

문제를 처음보고 이해하는데까지 굉장히 오랜시간이 걸렸고 완전히 이해하지 못한채 문제에 접근하였다. 

초기 해석은 각단계라는 부분을 위에 나와있는 1~4의 과정을 각각의 단계로 해석해 각 로직인 진행될때마다 카운트를 해주는 방식으로 코드를 작성하였다. 또 총 3가지 로직이 존재하는데 회전, 로봇의 이동, 로봇을 벨트 올리는 위치에 올리는 3가지과정을 진행하는데 초기에 로봇이 올려져있는 상태로 시작해한다고 생각해 그렇게 코드를 작성하였다.

또 로봇과 벨트 배열을 각각 선언하고 이를 회전시키는 느낌으로 작성해야겠다는 생각이 들어 원형큐처럼 접근하는데 큐를 사용하는 것이 아니라 배열 인덱스로 이를 계산하는 식으로 접근하였다.

 

< 초기 코드  >

import java.util.*;

public class Main{
    public static int zero=0;
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        int k=s.nextInt();
        int index=0;
        int beltN=0;
        int robotN=0;
        int cnt=1;

        
        int belt[]=new int[n*2];
        boolean robot[]=new boolean[n];
        
        for(int i=0;i<n*2;i++){
            belt[i]=s.nextInt();
        }
        robot[robotN]=true;
        belt[beltN]--;
        while(true){
            zeroN(belt);
            if(zero==k)break;
            
            // 벨트 회전
            cnt++;
            zeroN(belt);
            if(zero==k)break;
            // 로봇 이동
            cnt++;
            zeroN(belt);
            if(zero==k)break;
            //올리는 위치에 로봇 올리기
            cnt++;
            
        }
        System.out.println(cnt);
    }
    
    public static void zeroN(int belt[]){
        int cnt=0;
        for(int i=0;i<2*n;i++){
            if(belt[i]==0){cnt++;}
        }
        zero=zero>cnt?zero:cnt;
    }
    
    public static void 
}

초기 코드를 제출하지 않고 문제를 이해하면서 맞는 방향으로 수정해 슈도코드처럼 약간만 흐름만 남아있음을 양해바란다.

먼저 설명하였듯이 로봇과 벨트 배열을 선언해주었고 처음 시작할때 로봇이 존재해야한다고 판단해 로봇을 올려주고 시작하였다.

또 여기에도 작성되어 있듯이 벨트와 로봇의 처음위치를 가르킨는 beltN과 robotN을 선언해주어 각각의 인덱스 변화를 추적하고자하였다. 마지막으로 벨트 회전, 로봇이동, 올리는 위치에 로봇올리기 함수를 각각 선언하고 함수 호출때마다 cnt의 카운트를올려주는 식으로 구현하였다. 하지만 해당 방식에는 여러문제가 존재하는데 먼저

로봇과 벨트의 인덱스 관리부분이었다 벨트는 회전하는 것이 맞기때문에 틀린 방식은 아니었지만 로봇같은경우 회전하는 것이 아니라 벨트의 마지막 부분에서는 로봇이 옮겨지는 것을 고려하지 못하였다. 또 벨트 회전, 로봇이동, 올리는 위치에 로봇올리기 이 3가지 로직인 하나의 단계인데 본인은 각각 별도의 단계로 인지하고 문제를 접근한것이 문제가 되었다. 마지막으로 로봇을 올리는 것이 아니라 위의 순서대로 진행해야한다는 것까지 인지하고 아래와 같이 코드를 최종 작성하였다.

< 최종 코드 >

import java.util.*;

public class Main{
    public static int zero=0;
    public static int beltN=0;
    public static int robotN=0;
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        int k=s.nextInt();
        
        int cnt=0;

        
        int belt[]=new int[n*2];
        boolean robot[]=new boolean[n];
        
        for(int i=0;i<n*2;i++){
            belt[i]=s.nextInt();
        }

        
        while(zero<k){
            // 벨트 회전
            rotate(belt,robot,n);

            // 로봇 이동
            moveRobot(belt,robot,n);


            //올리는 위치에 로봇 올리기
            if(belt[beltN]>0&&!robot[0]){
                robot[0]=true;
                belt[beltN]--;
            }
            
            zeroN(belt,n);
            cnt++;
            
        }
        System.out.println(cnt);
    }
    
    public static void zeroN(int belt[],int n){
        int cnt=0;
        for(int i=0;i<2*n;i++){
            if(belt[i]==0){cnt++;}
        }
        
        zero=cnt;
    }
    
    public static void rotate(int belt[],boolean robot[],int n){
        beltN=(beltN-1+(2*n))%(2*n);
        
        
        for(int i=n-1;i>=0;i--){
            if(robot[i]){
                if(i+1>n-1){
                    robot[i]=false;
                }
                else{
                    robot[i]=false;
                    robot[i+1]=true;
                }
            }
            else{
                if(i+1<n){
                   robot[i+1]=false; 
                }
                
            }
        }
        
    }
    public static void moveRobot(int belt[],boolean robot[],int n){
            for(int i=n-1;i>=0;i--){
                if(robot[i]){
                    if(i+1>n-1){
                        robot[i]=false;
                    }
                    else{
                        if(!robot[i+1]&&belt[(beltN+i+1)%(2*n)]>0){
                            robot[i]=false;
                            robot[i+1]=true;
                            belt[(beltN+i+1)%(2*n)]--;
                        }
                        
                    }
                }
            }
        
    }
}

먼저 아래와 같이 총 3가지 함수를 별도로 선언해주었다.

• belt의 내구도에서 0이 몇개인지를 판단하는 zeroN함수
• 벨트의 회전을 담당하는 rotate 함수
• 로봇의 이동을 담당하는 moveRobot함수

이렇게 3가지함수를 선언해주었고 while문에서 3가지를 호출해 단계를 진행하는 방식이다. 

또 로봇의 경우 N-1의 위치에 도착하면 끝으로 옮겨주어야하기 때문에 벨트와 달리 회전하는 방식이 아닌 각 위치의 값을 이동하는 식으로 코드를 작성하였다.

  마무리  

사실 차근차근 침착하게 하나씩 해결하면 어렵지 않은 문제일 수도 있다. 하지만 아직 구현 문제들이 익숙하지 않아서 

그게 쉽지 않은 것같다. 해당 문제도 이런식으로 푸는게 맞나? 라고 계속 의심하면서 문제를 풀고 제출했는데 통과한 경우이다.

다음에 구현문제를 풀게된다면 위에서처럼 급하게 풀지말고 확실하게 전체 틀을 잡아두고 문제를 해결해야겠다.

  추가 코드 분석 및 풀이  

다른 분들의 코드를 확인해본 결과 인덱스로 접근하는 것이 아닌 직접 내구도를 옮기는 방식으로 코드를 구현하였다는 

차이는 조금 있었지만 큰틀의 차이는 없어 추가 코드는 작성하지 않겠다.