[BOJ] 백준 25395 : 커넥티드 카 실험 (java)

🧪 25395 커넥티드 카 실험

---

난이도 : 🌟 골드 3
유형 : 투포인터

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

 

📝 문제

---

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

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

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

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

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

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

 

입력

 

 

출력

 

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

 

🧐 핵심 로직

---

1) 연결점의 위치와 연료량을 입력받아 초기화합니다.

 

2) 시작점에서부터 BFS 방식으로 이동 가능한 연결점들을 탐색합니다.

 

3) 이동할 수 있는 범위 내에서 왼쪽과 오른쪽으로 각각 탐색하며, 방문 가능한 연결점을 큐에 넣고, 그 범위 내에서 계속해서 탐색을 이어갑니다.

 

4) 최종적으로 방문할 수 있는 모든 연결점의 번호를 출력합니다.

 

💻 최종 코드 (1136 ms)

---

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

public class Main {

    static class Connector {

        int pos, fuel;

        Connector (int pos, int fuel) {
            this.pos = pos;
            this.fuel = fuel;
        }
    }

    static int n, s;
    static boolean[] visited;
    static List<Connector> connectors;
    public static void main(String[] args) throws Exception {

//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken()) - 1;
        visited = new boolean[n];

        StringTokenizer st1 = new StringTokenizer(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        connectors = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int pos = Integer.parseInt(st1.nextToken());
            int fuel = Integer.parseInt(st2.nextToken());

            connectors.add(new Connector(pos, fuel));
        }

        twoPointer();

        br.close();
    }

    private static void twoPointer() {

        Queue<Integer> q = new LinkedList<>();
        int mlPos = connectors.get(s).pos;
        int mxPos = connectors.get(s).pos;
        int mlIdx = s;
        int mxIdx = s;

        visited[s] = true;
        q.add(s);
        while (!q.isEmpty()) {

            int curConnect = q.poll();
            mlPos = Math.min(mlPos, connectors.get(curConnect).pos - connectors.get(curConnect).fuel);
            mxPos = Math.max(mxPos, connectors.get(curConnect).pos + connectors.get(curConnect).fuel);

            for (int left = mlIdx - 1; left >= 0; left--) {
                if (connectors.get(left).pos < mlPos) break;
                if (visited[left]) continue;

                mlIdx = Math.min(mlIdx, left);
                visited[left] = true;
                q.add(left);
            }

            for (int right = mxIdx + 1; right < n; right++) {
                if (connectors.get(right).pos > mxPos) break;
                if (visited[right]) continue;                                       

                mxIdx = Math.max(mxIdx, right);
                visited[right] = true;
                q.add(right);
            }
        }

        for (int i = mlIdx; i <= mxIdx; i++) {
            System.out.print(i + 1 + " ");
        }
    }
}