[백준] 20055 컨베이어 벨트 위의 로봇 - 구현 + 시뮬레이션 JAVA

https://www.acmicpc.net/problem/20055

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

코드설명

구현과 시뮬레이션 문제입니다.

 

문제에서 유의해야할점들입니다.

1. 문제에 대한 이해가 헷갈릴 수 있습니다.

- 1. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다. 의 문제조건을 보면 벨트와 로봇이 먼저 함께 움직입니다. 이 경우 내구도가 떨어지지 않습니다.

 

 

2. 얕은복사일시 객체의 값이 참조되어 변합니다.

- 얕은복사이기에 모든 작업을 다 처리한 후 robot.idx += 1 을 처리하여 인덱스값이 섞이지 않도록 조심합니다.

//2단계 : 로봇이 이동하는 과정
for(int i=0;i<robotArr.size();i++) {
    Node robot = robotArr.get(i);

    //이동할 칸의 내구도가 0이 아니라면 올리는 위치에 로봇을 올립니다.
    if(arr[robot.idx + 1] > 0 && visited[robot.idx + 1] == false) {
        arr[robot.idx+1] -= 1;
        visited[robot.idx] = false;
        visited[robot.idx + 1] = true;
        robot.idx += 1; //얕은 복사로 인해 해당 객체의 참조값을 바라보고있으므로 모든 작업을 처리한 후 바꿔야함. 이런식으로 해야 계산하기 편합니다.
    }

    if(robot.idx == N-1) { //만약 로봇이 내리는 위치라면
        visited[robot.idx] = false;
        robotArr.remove(i);
        i-=1; //로봇을 삭제했으니 처리 			
    }
}

 

3. 벨트와 로봇이 함께 이동할시 벨트의 내구도 값들과 로봇들의 방문배열의 위치를 잘 옮겨야합니다.

//벨트 먼저 이동
int lastConveyBelt = arr[N*2 - 1];
boolean lastVisitedBelt = visited[N*2 - 1];
for(int i=N*2-1;i>0;i--) {
    arr[i] = arr[i-1];
    visited[i] = visited[i-1];
}
arr[0] = lastConveyBelt;
visited[0] = lastVisitedBelt;

 

구현을 하는 문제이기에, 문제의 조건을 완전히 이해하고 구현하면 됩니다.

구현하면서 생각한 내용들은 주석으로 남겨보았습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	public static int N, K;
	public static int[] arr;
	public static int answer = 0;
	public static boolean[] visited;
	public static int kCount = 0;
	public static ArrayList<Node> robotArr = new ArrayList<Node>();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	K = Integer.parseInt(st.nextToken());
    	
    	arr = new int[N*2];
    	visited = new boolean[N*2];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N*2;i++) {
    		arr[i] = Integer.parseInt(st.nextToken()); 
    	}
    	
    	simulate();
    	
		System.out.println(answer);
    }
    
    public static void simulate() {
    	
    	while(true) {
	    	answer += 1;
	    	
	    	//1단계. 벨트가 각 칸위에 있는 로봇과 함께 한칸 회전합니다.
	    	rotateConveyBelt();
	    	
	    	//2단계 : 로봇이 이동하는 과정
	    	for(int i=0;i<robotArr.size();i++) {
	    		Node robot = robotArr.get(i);
	    		
	    		//이동할 칸의 내구도가 0이 아니라면 올리는 위치에 로봇을 올립니다.
	    		if(arr[robot.idx + 1] > 0 && visited[robot.idx + 1] == false) {
	    			arr[robot.idx+1] -= 1;
	    			visited[robot.idx] = false;
	    			visited[robot.idx + 1] = true;
	    			robot.idx += 1; //얕은 복사로 인해 해당 객체의 참조값을 바라보고있으므로 모든 작업을 처리한 후 바꿔야함. 이런식으로 해야 계산하기 편합니다.
	    		}
	    		
	    		if(robot.idx == N-1) { //만약 로봇이 내리는 위치라면
	    			visited[robot.idx] = false;
	    			robotArr.remove(i);
	    			i-=1; //로봇을 삭제했으니 처리 			
	    		}
	    	}
	    	
	    	//3. 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다.
	    	if(arr[0] > 0 && visited[0] == false) {
	    		arr[0] -= 1;
	    		robotArr.add(new Node(0));
	    		visited[0] = true;
	    	}
	    	
	    	//4.내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다. 
	    	if(getKCount() == false) {
//	    		System.out.println("check");
	    		break;
	    	}
    	
    	}
    	
    }
    
    public static void rotateConveyBelt() {
    	//벨트와 로봇이 함께 움직입니다. 이 경우 내구도가 감소되지 않습니다. (벨트와 함께 이동하는것이기에)
    	
    	//벨트 먼저 이동
    	int lastConveyBelt = arr[N*2 - 1];
    	boolean lastVisitedBelt = visited[N*2 - 1];
    	for(int i=N*2-1;i>0;i--) {
    		arr[i] = arr[i-1];
    		visited[i] = visited[i-1];
    	}
    	arr[0] = lastConveyBelt;
    	visited[0] = lastVisitedBelt;
    	
    	//로봇도 함께 이동
    	for(int i=0;i<robotArr.size();i++) {
    		Node robot = robotArr.get(i);
    		robot.idx = robot.idx + 1; //로봇 이동처리
    		
    		if(robot.idx == N-1) {  //만약 로봇이 내리는 위치라면 
    			robotArr.remove(i);	//robot을 삭제
    			i-=1; //로봇 사이즈가 줄어들었으니 robot의 size도 함께 줄어드므로 처리
    			visited[robot.idx] = false; //내렸으니 로봇 삭제
    		}
    	}
    }
    
    
    public static boolean getKCount() {
    	kCount = 0;
    	for(int i=0;i<N*2;i++) {
    		if(arr[i] == 0) {
    			kCount += 1;
    		}
    	}
    	
    	
    	if(kCount >= K) {
    		return false;
    	}
    	return true;
    }
    
}

class Node{
	int idx;
	public Node(int idx) {
		this.idx = idx;
	}
}