[BOJ] 18232 텔레포트 정거장

텔레포트 정거장

풀이

• 주예의 위치 : S, 방주의 위치 : E
• 점 X에서 이동가능 : X+1, X-1, X와 연결된 점
• S에서 E까지 가는 최소 시간을 구하는 문제이므로 BFS를 이용했다.
• List[] 배열로 각 점과 연결된 점들을 배열에 담았고, BFS 할 때, List[x]에 갈 수 있는 점들이 있으면 이동하게 했다.Queue에서 방문한 곳들을 빼면서, E에 도착하게 되면 종료했다.
• 따로 visit 배열을 쓰지 않고, map[next] = map[cur]+1 로 이동 시간을 저장했다.

코드

import java.util.*;
import java.io.*;
public class Main {
    static int answer = 0;
    static int[] dx = {-1,1};
    static int[] map;
    static int N,M,S,E;
    static List[] list;
    public static void main(String[] args)throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N+1];
        list = new List[N+1];
        for(int i=0;i<N+1;i++){
            list[i] = new LinkedList<Integer>();
        }
        st = new StringTokenizer(br.readLine());
        S = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            list[x].add(y);
            list[y].add(x);
        }

        bfs(S);
        System.out.println(map[E]);
    }

    private static void bfs(int x) {

        Queue<Integer> queue = new LinkedList<>();
        queue.add(x);

        while(!queue.isEmpty()){
            int cur = queue.poll();
            if(cur==E) break;
            for(int i=0;i<2;i++){
                int nx = cur+dx[i];
                if(nx>=0 && nx<=N && map[nx]==0){
                    map[nx] = map[cur]+1;
                    queue.add(nx);
                }
            }
            for(int i=0;i<list[cur].size();i++){
                int next = (int) list[cur].get(i);
                if(map[next]==0){
                    map[next] = map[cur]+1;
                    queue.add(next);
                }
            }

        }


    }
}