[백준OJ] 18232번 텔레포트 경기장 (Java)

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

18232번: 텔레포트 정거장

---

풀이

먼저 입력을 받으면서 텔레포트 정거장을 그래프를 이용해서 연결해주었습니다.

그런 뒤, S부터 시작하며 BFS를 실행하여 E까지의 최단거리를 구했습니다.

1. 해당 정거장이 텔레포트 정거장이면, 연결된 정거장들을 통해 최단거리를 비교하며 진행합니다.

2. 다음정거장이 범위안에 있으면, 최단거리를 비교하며 진행합니다.

3. 이전 정거장이 범위안에 있으면, 최단거리를 비교하며 진행합니다.

 

시간복잡도

 모든 노드를 방문하며 모든 정거장을 탐색한다고 하면 O(NM)이 됩니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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

        int n = Integer.valueOf(st.nextToken());
        int m =Integer.valueOf(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int s = Integer.valueOf(st.nextToken());
        int e = Integer.valueOf(st.nextToken());

        ArrayList<ArrayList<Integer>> tel = new ArrayList<>();
        for(int i=0;i<=n;i++){
            tel.add(new ArrayList<>());
        }
        for(int i=0;i<m;i++){
            st= new StringTokenizer(br.readLine());
            int from = Integer.valueOf(st.nextToken());
            int to = Integer.valueOf(st.nextToken());
            tel.get(from).add(to);
            tel.get(to).add(from);
        }

        Queue<Integer> q = new LinkedList<>();
        int[] visited = new int[n+1];
        Arrays.fill(visited,Integer.MAX_VALUE);
        visited[s] = 0;
        q.offer(s);

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

            if(now == e) break;

            for(int next : tel.get(now)){
                if(visited[next]>visited[now]+1){
                    visited[next]=visited[now]+1;
                    q.offer(next);
                }
            }

            if(now+1<=n &&visited[now+1] > visited[now]+1){
                visited[now+1] = visited[now]+1;
                q.offer(now+1);
            }
            if(now-1>=1 && visited[now-1] > visited[now]+1){
                visited[now-1] = visited[now]+1;
                q.offer(now-1);
            }
        }
        System.out.println(visited[e]);
    }
}