Baekjoon #25395

Baekjoon #25395

1개의 풀이 · Java

문제 원문 보기 ↗

SOLUTION INFO

Java · Main.java

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

public class Main {
    public static void main(String[] args) {
        FastReader rd = new FastReader();

        int N = rd.nextInt();
        int S = rd.nextInt();

        Car a[] = new Car[N];
        for (int i = 0; i < N; i++) {
            a[i] = new Car();
            a[i].id = i;
            a[i].pos = rd.nextInt();
        }

        for (int i = 0; i < N; i++) {
            a[i].cost = rd.nextInt();
        }

        Arrays.sort(a);

        Queue<Integer> q = new LinkedList<>();
        boolean visited[] = new boolean[N];

        for (int i = 0; i < N; i++) {
            if (a[i].id == S - 1) {
                q.add(i);
                visited[i] = true;
                break;
            }
        }


        while (!q.isEmpty()) {
            int idx = q.poll();

            for (int i = idx - 1; i >= 0; i--) {
                if (a[idx].pos - a[idx].cost > a[i].pos) {
                    break;
                }

                if (visited[i]) continue;

                visited[i] = true;
                q.add(i);
            }


            for (int i = idx + 1; i < N; i++) {
                if (a[idx].pos + a[idx].cost < a[i].pos) {
                    break;
                }

                if (visited[i]) continue;

                visited[i] = true;
                q.add(i);
            }
        }


        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            if (visited[i]) sb.append(i + 1).append(" ");
        }

        System.out.print(sb.toString());
    }

    static class Car implements Comparable<Car> {
        int id;
        int pos;
        int cost;

        @Override
        public int compareTo(Car o) {
            return this.pos - o.pos;
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

SOLUTION DESCRIPTION

풀이 설명

1. BFS 응용 문제. 주어진 시작 위치에서 연료 값으로 도달할 수 있는 차들을 파악해야한다. 주어진 `N` 의 최댓값은 `1e6` 이며, 단순 `BFS` 의 경우 최악의 시간복잡도를 반영했을 때 `TLE` 가 발생할 것이다. 2. 이를 개선하기 위해, 모든 차의 정보를 시작위치로 정렬하자. 이 때, 사물 인터넷이 연결된 임의의 차의 인덱스를 `idx` 라고 한다면, 해당 차가 연료를 사용하여도 도달하지 못하는 인덱스가 나타났을 때 탐색을 종료하면 된다. 3. 차는 일렬로 배치되었다는 점에 근거하여, 차가 다음방향 `->` 으로 이동하는 경우와 이전방향 `<-` 으로 이동하는 경우를 탐색하자.