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

🌵 문제 분석

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

도시가 N개, 도로가 M개(단방향) 주어지고 도시 간의 거리는 모두 1이다.

X에서 X로 가는 최단 거리는 항상 0이라고 가정한다.

 

도시 X에서 도달 가능한 모든 도시 중 거리가 K인 곳을 모두 출력하라.

아래의 경우 1에서 출발하여 최단 거리가 2인 곳은 4밖에 없다.

입력 :

N(도시의 개수), M(도로의 개수), K(출발 도시의 번호)

(M쌍의 인접한 도시)

A1 B1

A2 B2

... 

🌵 구현 아이디어

1️⃣ 인접 리스트 만들기

이중 연결 리스트를 만들어서 간선 정보를 저장한다. 

4 4 2 1
1 2
1 3
2 3
2 4

1	2, 3
2	3, 4
3
4

간선 정보를 단방향으로 저장함

2️⃣ 시작점을 X로 두고 BFS 탐색

X에서 시작해서 나머지 도시들로 BFS(너비 우선 탐색)을 하며 X로부터 도달할 수 있는 가장 짧은 거리를 업데이트한다.

3️⃣ 가장 짧은 거리가 K인 도시를 출력

가장 짧은 거리가 K인 도시를 오름차순으로 출력한다.

🌵 시간 복잡도

인접 리스트 만드는 시간 복잡도 : O(M)

BFS 탐색하는 시간 복잡도 : 모든 도시를 한 번씩만 방문하므로 O(N)

가장 짧은 거리가 K인 도시를 찾는 시간 복잡도 : N-1개의 도시를 탐색하므로 O(N-1)

 

N<=300,000

M<1,000,000

K<=300,000

 

전체 시간 복잡도는 O(M)+O(N)=1,300,000

따라서 제한 시간 (2초) 안에 탐색 가능하다.

🌵 알고리즘

그래프 탐색

❌ 오답 노트

1️⃣ 단방향 그래프인데 양방향으로 인접 리스트를 생성해서 틀렸다.

재빨리 단방향으로 바꿔줌

2️⃣ 최단거리 문제인데 DFS로 풀어서 틀렸다.

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

public class Main {
    static int N, M, K, X;
    static int[] ans;
    static List<List<Integer>> list;
    static boolean[] check;

    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())-1;

        list = new ArrayList<>();
        for(int i=0; i<N; i++){
            list.add(new ArrayList<>());
        }
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            list.get(a).add(b);
            //list.get(b).add(a);
        }
        check = new boolean[N];
        ans = new int[N];
        Arrays.fill(ans, Integer.MAX_VALUE);
        ans[X] = 0;

        dfs(X, 0);

        int cnt = 0;
        for(int i=0; i<N; i++){
            if(ans[i]==Integer.MAX_VALUE) cnt++;
            else if(ans[i]==K) System.out.println(i+1);
        }
        if(cnt==N) System.out.println(-1);

    }
    static void dfs(int now, int len){ //now(현재 도시 번호), len(X로부터의 최단 거리) 
        List<Integer> cities = list.get(now); //now와 인접한 도시들을 모두 구함
        for(int next : cities){ 
            if(!check[next]){ //한 번 방문한 곳은 다시 방문하지 않고 있음
                ans[next] = Math.min(ans[next], len+1);
                check[next] = true;
                dfs(next, len+1);
            }
        }
    }
}

 

😥 이 함수가 왜 잘못됐는지 설명 :

DFS로 X로부터의 거리를 찾으면 최단 거리가 아니라서 값을 나중에 업데이트해야 하는데 다시 방문할 수 없게 만들었음

 

dfs로 예제 입력 3을 실행해보자

(인덱스가 0부터 시작해서 도시 번호를 저장할 때 -1한 값을 저장함)

4 4 1 1
1 2
1 3
2 3
2 4

 

단방향 그래프는 이렇게 생겼고

dfs(0, 0)을 시작하면 이 루트를 먼저 실행한다.

그러면 (0은 출발한 도시니까 빼고) 도시 1, 2를 방문했으므로 check배열이 true가 된다.

check배열:

0	1	2	3
F	T	T	F

 

그리고 0으로부터의 최단 거리가 각각 저장될 것이다.

ans배열:

0	1	2	3
0	1	2	Integer.Max_Value

그런데 사실 이 루트로 탐색하면 0에서 2까지의 최단 거리는 1이다.

하지만 이미 도시2는 방문처리가 되었기 때문에 또 방문할 수 없어서 최단거리를 영원히 못 찾는다.

 

그렇다고 방문 처리를 없애고 모든 루트를 탐색하게 한다면 간선 수가 매우 많은 경우 or 순환이 생기는 경우가 생기기 때문에 시간 복잡도가 높아지거나 무한 루프에 빠질 수 있다.

 

따라서 BFS로 너비 우선 탐색을 하면서 방문 체크를 해서 모든 노드를 한 번씩만 방문하게 해야 한다.

3️⃣ ???

🌵 코드 설계

1. 입력 받기
   1. N, M, K, X 차례로 입력받기
   2. 이중 연결 리스트 list 생성해 양방향 인접 리스트 저장
2. 필요한 자료구조 선언
   
   1. X로부터의 최단 거리를 저장할 배열 ans 선언하고
   2. 모든 원소를 Integer.MAX_VALUE로 초기화
   3. 큐 선언
   4. 도시 번호 num, X로부터의 길이 len을 변수로 가지는 클래스 city 선언
3. 시작 점을 X로 두고 BFS 탐색
   1. 큐에 도시 X 넣기
      q.add(new City(0, 0))
   2. 큐가 빌 때까지 아래 과정 실행
      1. 큐에서 하나 꺼내기
         City now = q.poll();
      2. now와 인접한 도시들 구하기
         List<Integer> cities = list.get(now);
      3. 인접한 도시들의 최단거리 저장하기, 방문 체크, 큐에 넣기
         for(0<i<cities.size())
             int next = cities.get(i);
             if(!check[next]) ans[next] = now.len+1; check[next] = true; q.add(new City(next, now.len+1));
4. ans에 저장된 X로부터의 최단 거리가 K이면 그 도시의 번호 출력
   만약 최단 거리가 K인 도시를 하나도 못 찾으면 -1 출력

🌵 정답 코드

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

public class Main {
    static int N, M, K, X;
    static int[] ans;
    static List<List<Integer>> list;
    static boolean[] check;

    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())-1;

        list = new ArrayList<>();
        for(int i=0; i<N; i++){
            list.add(new ArrayList<>());
        }

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            list.get(a).add(b);
            //list.get(b).add(a);
        }

        check = new boolean[N];
        check[X] = true;

        ans = new int[N];
        Arrays.fill(ans, Integer.MAX_VALUE);
        ans[X] = 0;

        bfs(X);

        boolean found = false;
        for(int i=0; i<N; i++){
            if(ans[i]==K) {
                System.out.println(i+1);
                found=true;
            }
        }
        if(!found) System.out.println(-1);

    }
    static void bfs(int x){
        Queue<City> q = new LinkedList<>();
        q.add(new City(x, 0));

        while(!q.isEmpty()){
            City now = q.poll();
            List<Integer> cities = list.get(now.num);
            for(int i=0; i<cities.size(); i++){
                int next = cities.get(i);
                if(!check[next]){
                    ans[next] = now.len+1;
                    check[next] = true;
                    q.add(new City(next, now.len+1));
                }
            }
        }
    }
}
class City{
    int num, len;
    City(int num, int len){
        this.num = num;
        this.len = len;
    }

}