[이코테][Java] 특정 거리의 도시 찾기

문제 설명

어떤 나라에 1 ~ N번까지의 도시와 M개의 단방향 도로가 존재하고, 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중, 최단 거리가 정확히 K인 모든 도시의 번호를 출력하는 프로그램을 작성하세요.

 

입력조건

• 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X
• 둘째 줄부터 M개의 줄에 걸쳐서 두개의 자연수 A, B

출력조건

• X로부터 출발하여 도달할 수 있는 도시 중 최단거리가 K인 모든 도시의 번호 출력
• 하나도 존재하지 않으면 -1 출력

입출력 예시

입력예시	출력예시
4 4 2 1 1 2 1 3 2 3 2 4	4

 

 

 

 

문제 풀이

• BFS 알고리즘 사용
• BFS 알고리즘을 사용해서 특정한 도시 X로부터 모든 도시까지의 최단 거리를 구하고, 그 값이 K인 도시의 번호를 찾아 출력한다.

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

public class Main {

    public static int n, m, k, x;
    public static Queue<Integer> q = new LinkedList<>();
    public static ArrayList<ArrayList<Integer>> cities = new ArrayList<>(); //도로 정보
    public static int[] distance;   //각 도로의 최단거리

    public static void bfs(int start) {
        q.offer(start);     //출발 도시 큐에 삽입

        while (!q.isEmpty()) {
            int now = q.poll();   //현재 도시번호를 큐에서 꺼낸다.

            //현재 도시에서 이동할 수 있는 모든 도시를 확인한다.
            for (int i = 0; i < cities.get(now).size(); i++) {
                int next_city = cities.get(now).get(i);
                if (distance[next_city] == -1) {    //이동하지 않은 도시라면 큐에 삽입하고 거리계산
                    distance[next_city] = distance[now] + 1;    //출발도시에서 해당 도시까지의 거리 계산
                    q.offer(next_city);     //큐에 삽입
                }
            }
        }
    }

    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());   //도로의 개수
        k = Integer.parseInt(st.nextToken());   //거리 정보
        x = Integer.parseInt(st.nextToken());   //출발 도시의 번호

        distance = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            cities.add(new ArrayList<>());
            distance[i] = -1;   //-1로 두는 것은 해당 도시를 방문하지 않았음을 나타내기 위함
        }

        distance[x] = 0;    //출발 도시는 0

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            cities.get(a).add(b);
        }


        bfs(x);

        boolean check = false;
        //모든 도시까지의 최단 거리 중 최단거리가 k인 도시를 찾는다.
        for (int i = 0; i <= n; i++) {
            if (distance[i] == k) {
                System.out.println(i);
                check = true;
            }
        }

        //최단거리가 k인 도시가 없다면 -1 출력
        if (check == false) {
            System.out.println(-1);
        }

    }
}

 

---

 

[참고서적]

이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈