백준 13335번 : 트럭 java

이 문제는 자료 구조 큐를 이용하여 위에서 주어진 조건에 맞게 최단시간을 구하는 알고리즘입니다.

저는 이 문제를 풀기 위해서 대기 중인 트럭들을 보관할 큐와 다리 위에 올라간 트럭들을 저장할 큐를 사용하였습니다.

각각의 큐에는 입력받은 자료의 무게와 인덱스를 저장하게 해서 문제를 해결하였습니다.

그림을 통해서 이를 자세히 설명드리도록 하겠습니다.

위의 그림은 예제 1번을 표현한 그림입니다.

truck 큐에 들어가 있는 자료들은 다리에 올라가기 위해서 대기 중인 트럭들을 의미합니다.

bridge 큐에 들어있는 자료들은 다리 위에 올라가 있는 트럭들을 의미합니다.

location배열은 몇 시간 뒤면 트럭이 다리에서 빠져나오는지를 확인하기 위해서 만든 배열입니다.

트럭이 bridge 큐에 들어가면 해당 index가 w 즉 다리의 길이로 초기화되고 다시 0이 되면 bridge 큐에서 제거됩니다.

이제 문제를 푸는 과정을 보여드리겠습니다.

이 예제에서 다리가 버틸 수 있는 최대하중은 10입니다.

0번 인덱스는 7의 무게를 가지고 있기 때문에 bridge 큐에 추가될 수 있습니다.

위의 그림에서 0번 인덱스가 bridge 큐에 추가되었기 때문에 location[0]을 다리의 길이로 초기화해줍니다.

그 후 1번 인덱스의 트럭이 bridge에 추가될 수 있는지를 확인하지만 이미 7의 무게가 올라가 있기 때문에 4의 무게가
올라가면 10을 넘어 추가되지 못합니다.

따라서 1번 인덱스의 트럭은 다리에 올리지 않고 다리에 올라가 있는 트럭만 이동시켜 줍니다.

트럭이 1번 이동한 후에는 이제 1번 더 0번 트럭이 이동한다면 location[0]은 0이 되어 다리에서 벗어나게 됩니다.

따라서 1번 인덱스의 트럭이 다리에 올라가는 게 가능해집니다.

따라서 bridge 큐에서 0번 인덱스를 제거해주고 1번 인덱스의 트럭을 truck 큐에서 꺼내서 bridge 큐에 추가해줍니다.

그리고 그 다음 트럭이 다리에 올라올 수 있는지를 확인합니다.

이미 올라가 있는 무게가 4이고 올라가려 하는 무게가 5이기 때문에 다리에 올라올 수 있습니다.

2번 인덱스의 트럭도 bridge 큐에 추가해주도록 하겠습니다.

이제 다리 위에 올라가 있는 무게는 9입니다.

그런데 1시간이 지나면 1번 인덱스의 트럭이 다리를 벗어납니다.

하지만 3번 인덱스의 트럭의 무게는 6이고 2번 인덱스의 트럭의 무게는 5이기 때문에 같이 다리에 올라갈 수 없습니다.

따라서 위의 그림과 같이 됩니다.

그리고 1시간이 지나면 2번 인덱스가 다리에서 벗어나고 3번 인덱스가 다리에 올라가게 됩니다.

그리고 truck 큐가 비게 되면 더 이상 다리에 올라갈 트럭이 없기 때문에 다리의 길이만큼의 시간이 지나면 모든 트럭이
다리를 지났다는 것을 의미합니다.

이것을 그림으로 나타내면 아래와 같습니다.

---

---

이제 이것을 코드로 구현해보도록 하겠습니다.

---

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

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

        int N = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());

        Queue<Node> truck = new LinkedList<>();
        int[] location = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N; i++) {
            int weight = Integer.parseInt(st.nextToken());
            truck.offer(new Node(i, weight));
        }

        Queue<Node> bridge = new LinkedList<>();
        int count = 0;
        int sum = 0;

        while(!truck.isEmpty()){
            Node a = truck.peek();
            int idx = a.index;
            int weight = a.weight;

            if(!bridge.isEmpty()){
                int start = bridge.peek().index;

                for(int i = start; i<idx; i++)
                    location[i]--;

                if(location[start] == 0) {
                    sum -= bridge.poll().weight;
                }
            }

            if(sum + weight<=L){
                bridge.offer(truck.poll());

                sum += weight;
                location[idx] = W;
            }

            count++;
        }

        System.out.println(count+W);
    }
}
class Node{
    int index, weight;

    Node(int index, int weight){
        this.index = index;
        this.weight = weight;
    }
}

위에서 설명드린 것과 같이 코드를 구현하였습니다.