[백준] 18352번 : 특정 거리의 도시 찾기

특정 거리의 도시 찾기

---

풀이 방법

BFS 를 이용한 최단 경로 찾기 문제 중 가장 기본 문제인 것 같았다.
최단 경로 찾기에서 딱히 추가 옵션이 없어서 간단하게 구현 가능했다.

최단 경로 찾기 문제에서는 이전 거리에서 경로의 비용을 더해준다고 생각하는게 중요하다.

물론 이 문제는 다익스트라 알고리즘을 통해 해결할 수 있지만, 모든 간선의 비용이 1이기 때문에 굳이 사용하지 않아도 괜찮다. (가중치 그래프에서 최단 경로를 구하는 문제가 나오면 풀어봐야겠다!)

자세한건 소스 코드를 참고하자

소스 코드

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

public class Main {
    static List<List<Integer>> graph;
    static boolean[] visited;
    static int k;
    static int[] dis;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(st.nextToken()); //정점 수
        int m = Integer.parseInt(st.nextToken()); //간선 수
        k = Integer.parseInt(st.nextToken()); //최단거리
        int x = Integer.parseInt(st.nextToken()); //출발 도시 번호

		//초기화
        graph = new ArrayList<>();
        for(int i=0;i<n+1;i++){
            graph.add(new ArrayList<>());
        }
        visited = new boolean[n+1];
        dis = new int[n+1];

		//정점 연결
        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine()," ");
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            graph.get(from).add(to);
        }

        bfs(x);

        for(int i=1;i<dis.length;i++){
            if(dis[i] == k){
                sb.append(i).append("\n");
            }
        }
        if(sb.length()==0){ //맞는 게 없다면 -1 출력
            System.out.println(-1);
        }
        System.out.println(sb);
    }
    
    //최단 거리 찾는 함수 - BFS
    private static void bfs(int start) {
        visited[start] = true;
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(start);

        dis[start] = 0; //자기 자신은 거리가 0

        while(!queue.isEmpty()){
            int c = queue.remove();
            for(int i : graph.get(c)){
                if(!visited[i]){
                    visited[i] = true;
                    queue.add(i);
                    
                    //이전 거리에서 1 더한 값
                    dis[i] = dis[c] + 1;
                }
            }
        }
    }
}