[Java | 투포인터 | 25395번 | 골3] 커넥티드 카 실험

☑️ 문제

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

정보통신기술(ICT)의 발달에 힘입어, 미래형 자동차로 여겨졌던 인터넷 연결을 통해 운전자에게 다양한 서비스를 제공하는 커넥티드 카(connected car)가 현실로 다가왔다. 현대오토에버는 이에 발맞춰 클라우드와 사물 인터넷을 비롯한 최신 ICT를 적용한 차세대 커넥티드 카 서비스 플랫폼을 구축하고, 최고의 커넥티드 카를 완성하기 위한 핵심 소프트웨어 기술을 축적하고 있다.

현대오토에버의 엔지니어 현오는 새로운 서비스를 생각하던 중, 커넥티드 카의 핵심 기술인 사물 인터넷과 위치 기반 기술을 접목한 실험을 해 보기로 했다. 현오가 개발한 실험용 프로그램은 다음과 같은 기능을 가지고 있다.

• 현오는 사물 인터넷에 연결된 커넥티드 카를 원격 조종할 수 있다.
• 사물 인터넷에 연결된 커넥티드 카가 그렇지 않은 커넥티드 카와 같은 위치에 있게 되면, 그 커넥티드 카를 사물 인터넷에 연결시킬 수 있다. 이후 두 커넥티드 카가 다시 서로 멀어지더라도 연결은 그대로 유지된다.

현오는 실험을 위해 1부터 N까지 번호가 매겨진 N대의 커넥티드 카를 일렬로 배치했다. i번 커넥티드 카의 초기 위치는 x_i이고, 연료량은 h_i이다. 모든 커넥티드 카는 1만큼의 연료를 소비해서 1의 거리만큼 이동할 수 있으며, 연료를 모두 소비하면 더 이상 움직일 수 없다.

처음에 커넥티드 카들은 모두 사물 인터넷에 연결되지 않은 상태이다. 현오는 먼저 S번 커넥티드 카를 사물 인터넷에 연결시키고, 프로그램의 기능을 적절히 사용해 다른 커넥티드 카들에 사물 인터넷을 전파하려고 한다.

현오가 커넥티드 카들을 어떻게 다루느냐에 따라 실험에서 사물 인터넷에 연결되는 커넥티드 카들의 조합은 달라질 수 있다. 현오가 다양한 방법으로 여러 번 실험을 진행할 때, 사물 인터넷에 연결될 가능성이 있는 커넥티드 카를 전부 구해 보자.

 

입력

첫 번째 줄에 N과 S가 주어진다. (1≤N≤1,000,000; 1≤S≤N) 

두 번째 줄에 각 커넥티드 카의 초기 위치 x1,x2,⋯,xN이 공백으로 구분되어 차례로 주어진다. (0≤xi≤10^9; xi≤x(i+1))

세 번째 줄에 각 커넥티드 카의 연료량 h1,h2,⋯,hN이 공백으로 구분되어 차례로 주어진다. (1≤hi≤10^9)

 

출력

첫 번째 줄에 사물 인터넷에 연결될 가능성이 있는 모든 커넥티드 카의 번호를 오름차순으로 정렬하여 출력한다.

 

예제 입력1

5 3
1 2 4 5 8
2 1 2 2 3

 

예제 출력1

1 2 3 4

☄️ 정답코드

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

public class Main {
    static int N, S;
    static long[] x, h;
    static boolean[] visited;
    static List<Car> cars;

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

        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken()) - 1;

        x = new long[N];
        h = new long[N];
        visited = new boolean[N];
        cars = new ArrayList<>();

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            x[i] = Long.parseLong(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            h[i] = Long.parseLong(st.nextToken());
        }

        for (int i = 0; i < N; i++) {
            cars.add(new Car(i, x[i], h[i]));
        }

        bfs(S);

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

    static void bfs(int start) {
        Queue<Car> q = new LinkedList<>();
        q.add(cars.get(start));
        visited[start] = true;

        int left = start, right = start;

        while (true) {
            if (q.isEmpty()) break;
            Car now = q.poll();

            while (true) {
                if (left == 0 || visited[cars.get(left - 1).num]) break;
                if (cars.get(left - 1).x < now.x - now.h) break;
                left--;
                q.add(cars.get(left));
                visited[cars.get(left).num] = true;
            }

            while (true) {
                if (right == N - 1 || visited[cars.get(right + 1).num]) break;
                if (cars.get(right + 1).x > now.x + now.h) break;
                right++;
                q.add(cars.get(right));
                visited[cars.get(right).num] = true;
            }
        }
    }

    static class Car implements Comparable<Car> {
        int num;
        long x, h;

        public Car(int num, long x, long h) {
            this.num = num;
            this.x = x;
            this.h = h;
        }

        public int compareTo(Car c) {
            return Long.compare(this.x, c.x);
        }
    }
}

 

🪐 풀이

투포인터 + BFS

S번 차량부터 BFS를 시작해, 현재 차량의 이동 범위 내(좌우)에 있는 인접 차량들을 투포인터로 탐색하는 방법으로 풀 수 있다!

 

시간복잡도

차를 한 번씩 방문하므로 O(N)