[백준] 13335. 트럭 (Java)

 

문제

13335번: 트럭

 

알고리즘

구현, 시뮬레이션, 큐

 

 

풀이

모든 트럭이 다리를 건널 때까지 1초씩 시뮬레이션하며 트럭이 다 건너는 시간을 출력한다.

 

[대기 중인 트럭]과 [이동 중인 트럭]으로 나뉘어지고, 트럭은 순서대로 이동해야하므로 2개의 큐를 사용한다.

그렇다면 [대기 중인 트럭] 큐도 비어있고, [이동 중인 트럭] 큐도 비어있을 때가 모든 트럭이 다리를 건넜을 때이다.

 

각 초마다 다음 과정을 진행한다.

1. 다리 위의 트럭들이 1 단위 길이만큼 움직인다.

2. 다리를 다 건넌 트럭을 [이동 중인 트럭] 큐에서 제거한다.

3. 대기 중인 맨 앞의 트럭을 다리 위에 올릴 수 있다면 [대기 중인 트럭] 큐에서 제거하고 [이동 중인 트럭] 큐에 추가한다.

 

과정을 반복하면서 모든 트럭이 다리를 건넜다면 그때의 시간을 출력한다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine(), " ");
		int n = Integer.parseInt(st.nextToken());
		int w = Integer.parseInt(st.nextToken());
		int L = Integer.parseInt(st.nextToken());

		ArrayDeque<Truck> queue = new ArrayDeque<>();
		ArrayDeque<Truck> progress = new ArrayDeque<>();

		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < n; i++) {
			queue.add(new Truck(Integer.parseInt(st.nextToken()), 1));
		}

		int t = 0;
		int progressW = 0;
		while (!queue.isEmpty() || !progress.isEmpty()) {

			// 다리 위의 트럭 이동
			int size = progress.size();
			for (int i = 0; i < size; i++) {
				Truck cur = progress.poll();
				progress.add(new Truck(cur.w, cur.t + 1));
			}

			// 트럭이 다리를 다 건넜다면 제거
			if (!progress.isEmpty() && progress.peek().t > w) {
				progressW -= progress.peek().w;
				progress.poll();
			}

			// 트럭을 다리 위에 추가할 수 있다면 추가
			if (!queue.isEmpty() && progressW + queue.peek().w <= L) {
				progressW += queue.peek().w;
				progress.add(queue.poll());
			}

			t++;
		}
		
		System.out.println(t);
	}

	static class Truck {
		int w, t;

		public Truck(int w, int t) {
			this.w = w;
			this.t = t;
		}
	}
}