[백준 7576 JAVA] 토마토

BFS문제

 

단순하게 BFS만 할것이 아니라 언제 토마토가 다 익는지까지 구해야된다.

 

내가 생각해낸 방법은 탐색을하면서 몇번째로 익는지 따로 기록하는 것이다.

그렇게 되면 마지막으로 익는 (마지막에 탐색되는) 토마토에 기록된 숫자를 보여주기만 하면 끝이다.

처음에 입력을 받으며 안익은 토마토의 개수를 구해놓고, 탐색을 하며 감소시킨다.

큐가 비었을때, 남은 토마토가 있다면 -1을 출력한다. (이부분은 visit을 활용하여 구할 수도 있을것이다.)

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        int N;
        StringTokenizer st;
        int[] arr;
        while (T-- > 0) {
            N = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            arr = new int[N];
            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
            long answer = 0;
            int max = Integer.MIN_VALUE;
            for (int i = N - 1; i >= 0; i--) {
                if (max < arr[i]) {
                    max = arr[i];
                }
                answer += max - arr[i];
            }
            System.out.println(answer);
        }
    }
}