[BOJ] 18352 특정 거리의 도시 찾기 - Java

✨ 그래프 탐색

✨ BFS, 다익스트라 ➔ 최단 경로 찾기 

 

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

18352번: 특정 거리의 도시 찾기

---

📍 고려해야할 점

 

• 출발 도시에 대한 정보가 존재한다.
• 최단 거리에 대한 정보가 존재한다. ➔ 해당하는 최단 거리인 도시를 찾으면 된다.
• 하나의 도시에서 다른 모든 도시까지의 최단거리를 구해야하기 때문에 다익스트라 알고리즘을 사용한다. 
• 도시간의 거리가 모두 1이기 때문에 BFS를 사용해서 간선을 지날 때마다 1씩 거리를 증가시켜 구할 수도 있다. 

 

🕹️ 풀이과정 

🕹️ 다익스트라 알고리즘

1️⃣ 노드에 대한 정보(이동해야하는 노드, 해당하는 노드까지 도달하는데 소요되는 거리 = 1)를 저장할 수 있는 클래스가 필요하다.

2️⃣ 출발노드가 정해져있기 때문에 일차원 dist 배열을 생성한다. 

3️⃣ 다익스트라 알고리즘을 수행해 dist 배열을 채운다. 

4️⃣ 채워진 dist 배열에서 문제에서 요구한 최단거리를 갖고 있는 도시번호를 오름차순으로 출력한다. 

---

🕹️ BFS

1️⃣ 거리에 대한 정보를 저장하지 않아도 되기 때문에 노드에 대한 정보를 따로 생성하지 않는다.

2️⃣ 방문여부 표시와 거리정보 저장을 동시에 처리할 수 있도록 int형의 visited 배열을 생성한다. 

3️⃣ 방문한 도시에서 visited 배열을 1 증가시켜 거리 정보를 저장한다. 

 

 

👩‍💻  전체 코드 

 

1️⃣ 다익스트라 알고리즘 

public class BOJ_18352_특정거리의도시찾기 {

    static int N, M, K, X;
    static ArrayList<Node>[] city;
    static int[] dist;
    static boolean[] visit;
    static int INF = Integer.MAX_VALUE;

    static class Node implements Comparable<Node>{
        int y, w;

        public Node(int y, int w) {
            this.y=y;
            this.w=w;
        }

        @Override
        public int compareTo(Node o) {
            return this.w-o.w;
        }
    }

    static void dijkstra(int start){
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        dist[start] = 0;

        while (!pq.isEmpty()) {
            Node now = pq.poll();

            if (!visit[now.y]) visit[now.y]=true;

            for (int i = 0; i < city[now.y].size(); i++) {
                Node next = city[now.y].get(i);

                if (!visit[next.y] && dist[next.y] > next.w + now.w) {
                    dist[next.y] = next.w + now.w;
                    pq.add(new Node(next.y, dist[next.y]));
                }
            }
        }
    }
    
    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());
        K = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());

        city = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++) {
            city[i] = new ArrayList<>();
        }

        dist = new int[N + 1];
        visit = new boolean[N + 1];

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

            city[A].add(new Node(B,1)); // 거리가 모두 1
        }

        Arrays.fill(dist, INF);
        dijkstra(X);

        boolean flag=false;

        for (int i = 1; i <= N; i++) {
            if (dist[i] == K) {
                System.out.println(i);
                flag= true;
            }
        }

        if (!flag) {
            System.out.println(-1);
        }
    }
}

 

---

2️⃣ BFS

public class 특정거리의도시찾기 {
 
    static int n,m,k,x;
    static int visited[];
    static ArrayList<Integer>[] graph;
    static List<Integer> ans;
 
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
 
        n = sc.nextInt(); // 노드 수
        m = sc.nextInt(); // 간선 수
        k = sc.nextInt(); // 목표 거리
        x = sc.nextInt(); // 시작점
        graph = new ArrayList[n+1]; // 그래프 데이터 저장
        ans = new ArrayList<>(); // 정답
 
        for (int i=1; i<=n; i++){
            graph[i] = new ArrayList<Integer>(); // 그래프 리스트의 ArrayList 초기화
        }
 
        for (int i=1; i<=m; i++){
            int s = sc.nextInt();
            int e = sc.nextInt();
            graph[s].add(e);
        }
 
        visited = new int[n+1]; // 방문 배열 초기화
 
        for(int i=0; i<=n; i++) visited[i] = -1; // 방문 표시 + 거리정보 저장 ➔ 동시처리 가능
        
        bfs(x);
 
        for (int i=0; i<=n; i++){
            if(visited[i]==k){
                ans.add(i);
            }
        }
 
        if (ans.isEmpty()) {
            System.out.println("-1");
        } else{
            Collections.sort(ans);
            for (int temp : ans){
                System.out.println(temp);
            }
        }
    }
 
    private static void bfs(int node){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(node);
        visited[node]++; // visited 배열에 현재 노드 방문 기록하기
        while (!queue.isEmpty()) {
            int now = queue.poll();
 
            for (int destination : graph[now]){
                // 큐에 데이터 삽입하고 visited 배열에 방문거리 저장
                if (visited[destination]==-1){ 
                    visited[destination] = visited[now] + 1;
                    queue.add(destination);
                }
            }
        }
    }
}