[이코테] Q15 특정 거리의 도시 찾기 - 자바

저작권상 문제를 올릴 수 없으므로 이코테 서적을 통해 확인 바람

문제 풀이

최단 거리라고 해서 바로 다익스트라, 플로이드 워셜 알고리즘을 생각하기 쉽지만 훨씬 더 효율적으로 풀 수 있는 방법이 존재한다. 바로 bfs를 이용하는 것이다. bfs를 이용할 수 있는 조건이 존재한다. 바로 모든 도로의 거리가 일정한 경우에만 사용할 수 있다.

그렇다면 왜 bfs일까?

물론 dfs를 통해서도 최단 거리를 구할 수 있다. 하지만 비효율적이다.

예시를 들어보자

 

  A
 / \
B---C

다음과 같은 그래프가 존재하고 A를 시작으로 dfs를 진행해보자.

먼저 dfs 과정을 살펴보자

1.  우선 A -> B -> C 순서로 진행이 되며 이때 B에 대해서는 비용1로 최단경로가 성립되지만 C은 2로 최단 경로가 아니다. 우리는 C의 최단경로가 1이라는 것을 알고 있다.
2. 다음은 A -> C 가 진행될 것이다. 이때 C의 최단경로가 1이 된다.
   
   • 방문했던 노드에 대한 처리가 필요

즉, 방문했던 C에 대해 다시 재방문하여 최소비용인지 체크를 하는 로직이 필요하다.

하지만 bfs()를 이용하면 처음 방문한 노드가 최소 비용이 되므로 방문했던 노드에 대해서는 처리해줄 필요가 없다

다음 예시로 bfs와 dfs를 진행해보면 더욱 명확히 이해가 갈 것이다.

A -- B
| /  |
C    D

 

따라서 bfs를 통해 해당 문제를 해결할 수 있다.

코드

package 이코테.기출.dfs_bfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class C15 {
    static ArrayList<ArrayList<Integer>> g = new ArrayList<>();
    static int[] d;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());
        // 초기화
        d = new int[N + 1];
        for (int i = 0; i <= N; i++) {
            g.add(new ArrayList<>());
        }
        // 간선 입력
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            g.get(Integer.parseInt(st.nextToken())).add(Integer.parseInt(st.nextToken()));
        }

        bfs(start);
        // d에 저장된 최단 경로가 k인 노드 출력
        boolean flag = false;
        for (int i = 1; i <= N; i++) {
            if (d[i] == K) {
                System.out.println(i);
                flag = true;
            }
        }
        // k인 경로가 없다면 -1 출력
        if (!flag) {
            System.out.println(-1);
        }

    }

    static void bfs(int idx) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(idx);
        while (!q.isEmpty()) {
            Integer curIdx = q.poll();
            for (int i = 0; i < g.get(curIdx).size(); i++) {
                Integer adjNodeIdx = g.get(curIdx).get(i);
                if (d[adjNodeIdx] == 0) {
                    q.offer(adjNodeIdx);
                    d[adjNodeIdx] = d[curIdx] + 1;
                }
            }
        }
    }
}