백준 18232번 텔레포트 정거장 (java)

[Silver II] 텔레포트 정거장 - 18232

문제 링크

성능 요약

메모리: 129632 KB, 시간: 1392 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 8월 13일 18:56:17

문제 설명

꽉꽉나라에 사는 주예와 방주는 점 S에서 만나 저녁을 먹기로 했다. 주예는 점 S에 도착했지만 길치인 방주가 약속시간이 30분이 지나도 나타나지 않자 방주에게 연락을 하여 방주가 점 E에 있다는 사실을 알아냈다. 주예는 방주에게 그 위치에 가만히 있으라고 했고, 직접 점 E로 가려고 한다.

꽉꽉나라에는 1부터 N까지의 각 점에 하나의 텔레포트 정거장이 위치해 있고 텔레포트를 통하여 연결되어 있는 다른 텔레포트의 정거장으로 이동할 수 있다. 주예는 현재 위치가 점 X라면 X+1이나 X-1로 이동하거나 X에 위치한 텔레포트와 연결된 지점으로 이동할 수 있으며 각 행동에는 1초가 소요된다. 배가 고픈 주예는 최대한 빨리 방주와 만나고 싶어 한다.

N과 텔레포트 연결 정보가 주어질 때 점 S에 있는 주예가 점 E까지 가는 최소 시간을 구해보자.

입력

첫 번째 줄에 정수 N, M이 공백으로 구분되어 주어진다. (2 ≤ N ≤ 300,000, 0 ≤ M ≤ min(N×(N-1)/2, 300,000))

두 번째 줄에 정수 S, E가 공백으로 구분되어 주어진다. (1 ≤ S, E ≤ N, S ≠ E)

그 다음 줄부터 M개의 줄에 걸쳐 텔레포트 연결 정보를 의미하는 정수 x, y가 주어진다. (1 ≤ x, y ≤ N, x ≠ y)

x y는 점 x의 텔레포트와 점 y의 텔레포트가 연결되어 있다는 뜻이다. M개의 연결정보는 중복되는 x y쌍이 없도록 주어진다.

출력

첫 번째 줄에 주예와 방주가 만날 수 있는 최소 시간을 출력한다.

풀이

시간제한 조건 맞추기 굉장히 까다로운 문제다.

 

맨 처음에 dfs로 풀었다가 도저히 시간 제한을 통과할 수 없어서 bfs 로 바꾸었다.

 

간선에 텔레포트 정거장과 각 노드 별 (+1, -1)을 담아준 후 bfs 로 탐색하면 된다.

 

전체 코드

 

public class Main {

    static int N, M,S,E;
    static boolean visited[];
    static List<ArrayList<Integer>> edge = new ArrayList<>();
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


    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());
        M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        S = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());


        visited = new boolean[N+1];

        for(int i = 0 ;i<=N;i++){
            edge.add(new ArrayList<Integer>());
        }

        for(int i = 0 ;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            edge.get(a).add(b);
            edge.get(b).add(a);
        }

        for(int i = 1 ;i<=N;i++){
            if(i-1 > 0){
                edge.get(i).add(i-1);
            }
            if(i+1 <= N){
                edge.get(i).add(i+1);
            }
        }

        visited[S] = true;
        ArrayList<Integer> ed = new ArrayList<Integer>();
        ed.add(S);
        bfs(0,ed);

    }

    public static void bfs(int depth, ArrayList<Integer> ed) throws IOException {
        ArrayList<Integer> edd = new ArrayList<Integer>();

        while(!ed.isEmpty()){
            Integer i = ed.get(0);

            int size = edge.get(i).size();

            for(int j = 0 ;j<size;j++) {
                Integer k = edge.get(i).get(j);

                if(k == E){
                    bw.write(String.valueOf(depth+1));
                    bw.flush();
                    System.exit(0);
                }

                if (!visited[k]) {
                    visited[k] = true;
                    edd.add(k);
                }

            }
            ed.remove(0);
        }
        bfs(depth+1, edd);
    }



}