[분류]

  • 탐색



[문제링크]

[요구사항]

image


문제는 정해진 도시로부터 최단거리가 K인 도시를 구하기를 요구하고 있다.
  • 최단 거리가 K인 것이 중요하다.



[풀이]

  1. “최단 거리”라는 말이 나오면 가장 먼저 떠올려야 하는 것은 bfs 탐색기법이다

  2. 이를 적용하여 시작 도시 X를 기준으로 bfs를 수행하여 최단거리를 저장하였다.

  3. 탐색이 모두 끝나면 최단거리가 K인 도시들만 골라서 출력해준다.



[코드]

//baekjoon_18352_특정 거리의 도시 찾기

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

public class Main {
    static int n, m, k, x;
    static LinkedList<Integer> graph[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        k = Integer.parseInt(s[2]);
        x = Integer.parseInt(s[3]);

        graph = new LinkedList[n+1];
        for(int i=0;i<n+1;i++){
            graph[i] = new LinkedList<>();
        }

        for(int i=0;i<m;i++){
            s = br.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);

            graph[a].add(b);
        }//graph 생성

        ArrayList<Integer> answer = bfs();

        if(answer.size()==0) {
            System.out.println(-1);
            return;
        }
        for(int i=0;i<answer.size();i++){
            System.out.println(answer.get(i));
        }
    }

    public static ArrayList<Integer> bfs(){
        int list[] = new int[n+1];
        ArrayList<Integer> answer = new ArrayList<>();
        Queue<Integer> q = new LinkedList<>();
        boolean visited[] = new boolean[n+1];
        for(int i=0;i<n+1;i++)
            visited[i]=false;

        q.add(x);
        visited[x]=true;
        while(!q.isEmpty()){
            int idx = q.poll();
            int cnt = list[idx];
            for(int i=0;i<graph[idx].size();i++){
                int j = graph[idx].get(i);
                if(!visited[j]){
                    visited[j]=true;
                    q.add(j);
                    list[j] = cnt+1;
                }
            }
        }

        for(int i=0;i<list.length;i++){
            if(list[i]==k)
                answer.add(i);
        }
        return answer;
    }
}



[통과여부]

image



[느낀점]

탐색을 오랜만에 풀어서 그런지 dfs로 처음에 했었는데 ‘최단거리’하면 다익스트라와 같은 알고리즘을 적용해야 겠다는 생각이 바로 들게 연습하는 것이 중요한 것 같다. 그리고 자바는 내용이 간단함에도 불구하고 코드량이 너무 길다..