(알고리즘) 백준25395 java 자바

문제

백준 25395 커넥티드 카: https://www.acmicpc.net/problem/25395

정보통신기술(ICT)의 발달에 힘입어, 미래형 자동차로 여겨졌던 인터넷 연결을 통해 운전자에게 다양한 서비스를 제공하는 커넥티드 카(connected car)가 현실로 다가왔다. 현대오토에버는 이에 발맞춰 클라우드와 사물 인터넷을 비롯한 최신 ICT를 적용한 차세대 커넥티드 카 서비스 플랫폼을 구축하고, 최고의 커넥티드 카를 완성하기 위한 핵심 소프트웨어 기술을 축적하고 있다.
현대오토에버의 엔지니어 현오는 새로운 서비스를 생각하던 중, 커넥티드 카의 핵심 기술인 사물 인터넷과 위치 기반 기술을 접목한 실험을 해 보기로 했다. 현오가 개발한 실험용 프로그램은 다음과 같은 기능을 가지고 있다.
현오는 사물 인터넷에 연결된 커넥티드 카를 원격 조종할 수 있다.
사물 인터넷에 연결된 커넥티드 카가 그렇지 않은 커넥티드 카와 같은 위치에 있게 되면, 그 커넥티드 카를 사물 인터넷에 연결시킬 수 있다. 이후 두 커넥티드 카가 다시 서로 멀어지더라도 연결은 그대로 유지된다.
현오는 실험을 위해 $1$부터 $N$까지 번호가 매겨진 $N$대의 커넥티드 카를 일렬로 배치했다. $i$번 커넥티드 카의 초기 위치는 $x_i$이고, 연료량은 $h_i$이다. 모든 커넥티드 카는 $1$만큼의 연료를 소비해서 $1$의 거리만큼 이동할 수 있으며, 연료를 모두 소비하면 더 이상 움직일 수 없다.
처음에 커넥티드 카들은 모두 사물 인터넷에 연결되지 않은 상태이다. 현오는 먼저 $S$번 커넥티드 카를 사물 인터넷에 연결시키고, 프로그램의 기능을 적절히 사용해 다른 커넥티드 카들에 사물 인터넷을 전파하려고 한다.
현오가 커넥티드 카들을 어떻게 다루느냐에 따라 실험에서 사물 인터넷에 연결되는 커넥티드 카들의 조합은 달라질 수 있다. 현오가 다양한 방법으로 여러 번 실험을 진행할 때, 사물 인터넷에 연결될 가능성이 있는 커넥티드 카를 전부 구해 보자.

입력

첫 번째 줄에 $N$과 $S$가 주어진다. $(1\leq N\leq 1\, 000\, 000;$ $1\leq S\leq N)$ 
두 번째 줄에 각 커넥티드 카의 초기 위치 $x_1,x_2,\cdots ,x_N$이 공백으로 구분되어 차례로 주어진다. $(0\leq x_i\leq 10^9;$ $x_i\leq x_{i+1})$ 
세 번째 줄에 각 커넥티드 카의 연료량 $h_1,h_2,\cdots ,h_N$이 공백으로 구분되어 차례로 주어진다. $(1\leq h_i\leq 10^9)$ 

출력

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

예제 입력 1

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

예제 출력 1

1 2 3 4

실험 결과로 나올 수 있는 사물 인터넷에 연결된 커넥티드 카들의 조합은 $\{1,2,3\}$, $\{2,3\}$, $\{3\}$, $\{3,4\}$가 있다.

문제풀이

해당 문제는 bfs를 활용해서 풀었다. 먼저 이 문제를 풀기 위해서는 index와 시작지점 연료정보를 각 노드로 저장하고 있어야 한다. 이때 노드에서 연료를 가지고 움직일 수 있는 범위까지가 연결 될 수 있는 다음 노드가 된다.
이를 위해 info클래스를 통해 정보를 저장해두었다.
이후 info들을 위치 기준으로 정렬해주고 시작지점을 que에 넣어서 bfs를 돌린다.
bfs를 돌리면서 현재 노드에 위치에서 연료를 각각 더하고 빼면 다음 방문 가능한 범위 나온다. 초기 위치로 정렬된 노드들에서 각 인덱스를 1씩 빼고 더하면서 해당 노드가 방문 가능하면 큐에 넣어주는 식으로 bfs를 탐색했다

코드

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

public class Boj25395 {

    static class info implements Comparable{
        public int index;
        public int pos;
        public int fuel;

        @Override
        public int compareTo(Object o) {//Arrays.sort를 위해
            info temp=(info)o;
            return pos-temp.pos;
        }
    }

    public static void main(String args[]) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());
        info[] arr = new info[N];
        st = new StringTokenizer(bf.readLine());

        for (int i = 0; i < N; i++) {
            arr[i] = new info();
            arr[i].pos = Integer.parseInt(st.nextToken());
            arr[i].index = i + 1;
        }
        st = new StringTokenizer(bf.readLine());
        for (int i = 0; i < N; i++) {
            arr[i].fuel = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        int start = 0;
        for (int i = 0; i < N; i++) {
            if (arr[i].index == S) {
                start = i;
            }
        }
        int[] visit = new int[N+1];//1부터 N까지 인덱스 범위로 방문 체크
        Deque<Integer> que = new ArrayDeque<>();
        que.addLast(start);
        visit[arr[start].index]=1;
        while(que.size()!=0){
            int now=que.pollFirst();
            for(int i=now;i>=0;i--){
                if(arr[i].pos<arr[now].pos-arr[now].fuel)//정렬되어 있기 때문에 i가 값을 벗어나면 이후의 값은 당연히 벗어남{
                    break;
                }
                if(visit[arr[i].index]==0){
                    que.addLast(i);
                    visit[arr[i].index]=1;
                }
            }
            for(int i=now;i<N;i++){
                if(arr[i].pos>arr[now].pos+arr[now].fuel){
                    break;
                }
                if(visit[arr[i].index]==0){
                    que.addLast(i);
                    visit[arr[i].index]=1;
                }
            }
        }
        StringBuilder ans=new StringBuilder();
        for(int i=1;i<N+1;i++){
            if(visit[i]==1){
                ans.append(i).append(" ");
            }
        }
        System.out.println(ans);
    }
}

후기

문제가 어렵지는 않았다. 다만 또 출력을 하나하나 해주니 바로 시초가 난다. StringBuilder 애용하자.
그리고 참 바보 같은 날이였다. SSAFY월말 평가를 보는데 문제는 다 맞아두고 제출을 이상한 압축파일을 올렸다. 아마 0점 과락 처리 되겠지... 슬픈 하루다... 멍청했다 나...