[백준/Java] 13335번 : 트럭

✏️ 문제 분석

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

트럭 n개가 다리를 건너감

트럭 순서 변경 불가

 

다리 위에 트럭 w대가 동시에 올라갈 수 있음

다리 길이 w

 

트럭은 1 단위 시간에 1 단위 길이 만큼 이동할 수 있음

다리 최대 하중은 L

 

모든 트럭이 다리를 건너는 최단 시간을 구하는 문제

✏️ 구현 아이디어

4 2 10 //n w L
7 4 5 6 //트럭의 무게

1. 차례로 트럭 보내기

트럭의 순서를 바꿀 수 없으므로

앞에서부터 하나씩 트럭을 다리에 보내야 한다.

 

먼저 무게 7인 트럭을 보낸다. 

2. 다리의 하중(L)을 넘지 않는지 확인

다리에 최대 2개의 트럭을 올릴 수 있으므로

다음 트럭인 무게 4인 트럭을 보낼지 말지 결정해보자.

 

다리의 하중(L)을 넘으면 못 보낸다.

7+4 > 10 -> 넘음

7이 다리에서 벗어나야 4가 진입할 수 있다.

 

(7이 다리에서 벗어난 후 무게 4인 트럭부터 다시 1~2번 과정을 반복한다.)

3. 건너는 시간 구하기

위 예제의 경우 총 8초가 걸린다. 

다리 위에 트럭이 하나라도 있으면 무조건 1단위시간 만큼 시간이 소요된다는 특징이 있고,

첫 번째 트럭이 다리로 진입할 때와 마지막 트럭이 다리에서 벗어날 때도 1단위시간 만큼 소요된다.

✏️ 알고리즘

구현 문제. 트럭이 앞에서부터 차례로 다리로 진입하여 한쪽 방향으로 통과하므로 fifo 성격을 가진 큐를 쓸 수 있다.

✏️ 시간 복잡도

큐는 항상 front, rear에만 접근하므로 삭제, 삽입 시 걸리는 시간 복잡도가 O(1)이다.

트럭 수 n, 다리 길이 w이므로 큐 연산이 최대 n*w번 이루어질 수 있다.

w는 최대 100, n은 최대 1,000이므로 최악의 경우 총 100,000번의 연산이 발생.

따라서 시간 안에 (1초) 연산 가능하다.

✏️ 오답 노트

처음에는 큐라는 생각도 못 했음

그저 구현이라기에 w개의 연속된 트럭을 1개, 2개, 3개, ..., w개씩 묶어보고

각각의 경우 하중이 L을 넘는지 확인, 안 넘는 경우 중 가장 많은 트럭을 넣을 수 있는 경우를 선정하는..

브루트 포스 방식을 떠올렸다.

 

문제 의도 파악도 못 하고 혼자 떠올린 난해한 아이디어에

구현 방법이 생각날 리가 없었다. 😅😰🤯

큐라고 해서 일단 큐를 썼지만 큐의 성질을 제대로 활용하지 못했던..

아이디어를 얻기 위해 큐를 쓴다는 것만 아는 상태에서 다시 구현해봤다.

 

먼저 트럭 순서가 정해져있고 앞에서부터 하나씩 꺼내서 쓰므로 트럭 저장소를 큐로 쓰자.

 

그런데 다리도 큐로 써야 될까?

다리는...굳이 fifo로 트럭을 삽입/삭제할 필요가 있을까..? 하는 애매모호함이 있었다. 

 

다리는 그저 트럭이 저장되는 공간으로서의 기능만 하면 된다고 생각했기 때문이다.

(정답 코드 보면 왜 다리가 큐여야 하는지 이해됨)

 

아무튼 이러한 애매함을 느꼈음에도 일단 정확한 이유 없이 다리를 큐로 쓰기로 했다.

 

그리고 구현하기 어려웠던 부분이 두 가지 있었다.

• 모든 트럭이 지나가는 데 걸린 시간 계산
  • 🧐: 언제 시간을 카운트해야되지???
• 트럭이 w칸 지나갔으면 다리에서 나가게 하기
  • 🧐: 트럭이 다리에 w초 있었는지 검사하고 타임아웃 시키면 되지 않을까???

 

내가 처음 생각해낸 방법은

트럭이 다리 위에 w초만큼 있었다면 큐에서 아웃되도록

time[트럭무게] <- 이렇게 배열을 두고 

다리(큐) 에 트럭이 offer됐다면 time[트럭무게]++; 해줬고

이 값이 w라면 다리에서 remove했다.

 

그런데 트럭 무게로 같은 숫자가 여러 개 나올 수 있다는 부분을 간과해서 틀렸다.

해결책으로 다리에서 트럭을 remove할 때 time[트럭무게]=0으로 초기화해줬는데도 틀렸다.

 

그리고 시간을 카운트하는 방법도

다리에 트럭을 offer할 때마다 time++;

그리고 마지막 트럭이 remove될 때 한 번 time++;

이렇게 구현했는데 이것도 틀렸다.

 

어디가 잘못됐는지도 모른 채 디버깅에 의해 덕지덕지 고쳐진 내 코드를 더 고치기 보다

새로운 다른 방법을 시도해서 풀기로 했다.

큐의 활용

큐의 first-in first-out 특징을 잘 활용하니 쉽게 풀리는 문제였다.

 

👀 트럭이 w칸 지나갔으면 다리에서 나가게 하는 법 :

다리(큐)에 트럭이 몇 개 들어가있든 무조건 w개의 요소가 존재하도록 하면

단위시간 당 하나씩 inqueue, dequeue되면서 자연스럽게 트럭이 w단위시간동안만 다리에 존재하게 된다.

 

그냥 여러 트럭이 다리에 동시에 올라갈 수 있으면 연속으로 트럭을 넣어주고,

동시에 올라갈 수 없으면 트럭 대신 0을 넣어서 w개의 요소를 채워준다.

 

👀 모든 트럭이 지나가는 데 걸리는 시간 계산하는 법 :

이 방법으로 구현하면,

결국 다리(큐)에 트럭 또는 0이 inqueue, dequeue될 때마다

단위시간을 하나씩 카운트해주면 된다는 것을 알 수 있다.

✏️ 코드 설계

1. 입력 받기
2. 모든 트럭을 저장할 trucks, 다리 위에 진입할 트럭을 저장할 bridge를 큐로 선언
3. 총 경과 시간을 저장할 time, 현재 다리에 올라간 트럭의 하중을 저장할 nowWeight 선언
4. 첫 트럭이 다리 위에 w 단위 길이 만큼 앞으로 이동했다면 bridge에서 제거되도록 초기 작업
   1. 맨 처음에 bridge를 모두 0으로 초기화
5. bridge가 빌 때까지 다음을 수행
   1. bridge에 요소가 있다면 time++
   2. bridge에서 첫 요소를 제거
   3. bridge에 올릴 다음 트럭이 있다면, 최대 하중보다 가벼운지 확인
      1. 가볍다 : 다음 트럭 넣기 + nowWeight에 넣은 트럭 하중 더해주기
      2. 아니다 : 0 넣기
6. time 출력

✏️ 정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
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());

        //trucks를 큐로 생성하고 모든 트럭을 넣음
        Queue<Integer> trucks = new LinkedList<>();
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            trucks.offer(Integer.parseInt(st.nextToken()));
        }

        int time = 0;
        int nowWeight = 0;
        Queue<Integer> bridge = new LinkedList<>();

        //다리를 0으로 채워서 초기화
        for(int i=0; i<w; i++){
            bridge.offer(0);
        }
        while(!bridge.isEmpty()){
            time++;
            //다리에서 맨 앞에 있는 것 하나 빼기
            nowWeight -= bridge.poll();
            //다음 트럭이 있다면
            if(!trucks.isEmpty()){
                //하중을 견딜 수 있는지 확인
                //견딜 수 있다면 다음 트럭을 넣음
                if(nowWeight+trucks.peek() <= L){
                    nowWeight += trucks.peek();
                    bridge.offer(trucks.poll());
                }else bridge.offer(0);
            }
        }
        System.out.println(time);
    }
}