[백준, Java] 16211번, 백채원(그래프 탐색, 다익스트라)

문제 링크

16211번: 백채원

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. N개의 지점과 M개의 도로가 존재하며, 각 지점에는 집이 존재합니다.(1번 지점에는 집이 존재하지 않습니다.)

2. K명의 추종자는 각자의 지점에 존재합니다.

3. 백채원은 1번 지점을 시작으로 각 지점을 목적지로 정할 수 있으며, 추종자와 백채원은 속도가 똑같아졌습니다.

4. 백채원은 추종자에게 잡히지 않고, 집에 갈 수 있는 지점을 오름차순으로 정렬해서 결과로 출력해야 합니다.

5. 각 도로를 이동할 때 속도는 1이며, 만족하는 지점이 없다면 0을 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 각 추종자 위치에서 N개의 지점까지 도달하는 최단 거리를 구한 뒤 1번 지점에서 N개의 지점에 붙잡히지 않고 갈 수 있는 집을 탐색합니다.

 

3. 탐색을 통해 붙잡히지 않고 갈 수 있는 집의 번호를 오름차순 정렬해서 결과로 출력합니다.

 

최단 거리 구하기(그래프 탐색, 다익스트라)

 

먼저, 각 추종자 위치에서 최단 거리를 구해야하는 이유를 알아보겠습니다.

 

각 추종자는 항상 이동하는 것이 아니라 그 자리에 머무를 수 있습니다.

→ 즉, 추종자는 백채원을 만나기 위해서 최적의 행동을 하기 때문에 만약 N번 지점을 지나는 경로에 추종자가 먼저 갈 수 있으면 해당 경로에 먼저 도착해서 기다리면 백채원은 추종자를 만날 수 밖에 없습니다.

 

결과적으로 추종자가 각 지점에 먼저 도착한다면 백채원이 그 지점에 늦게 도달하였을 때 추종자를 항상 만난다는 것입니다.

 

추종자들에 대해서 각 지점에 최단 거리를 구한 뒤 백채원이 이동할 때 해당 지점에 최단 거리가 추종자에 최단거리보다 크면 추종자를 만나기 때문에 해당 경로로 이동할 수 없습니다.

 

정리하면,

 

백채원이 각 집에 최단 거리가 추종자들 기준의 최단거리보다 크면 해당 지점은 도착할 수 없는 집이 됩니다.

 

→ 각 추종자 기준으로 지점들의 최단 거리를 구한 뒤 백채원을 기준으로 최단 거리를 비교하여 도착할 수 있는 집들을 탐색합니다.

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N	M	K
6	8	2

 

지점과 도로

 

추종자 위치 : { 2, 4 }

 

 

 

2. 각 추종자 위치에서 N개의 지점까지 도달하는 최단 거리를 구한 뒤 1번 지점에서 N개의 지점에 붙잡히지 않고 갈 수 있는 집을 탐색합니다.

 

 

 

각 추종자 위치를 기준으로 N개의 지점에 대해서 최단 거리를 구합니다.

 

지점	1	2	3	4	5	6
최단 거리	2	0	2	0	3	6

백채원 위치를 기준으로 N개의 지점에 대해서 최단 거리를 구합니다.

지점	1	2	3	4	5	6
최단 거리	0	2	3	7	3	4

백채원 위치를 기준으로 N개의 지점에 대해서 최단 거리를 구합니다.

 

최단 거리를 비교하면

지점	1	2	3	4	5	6
추종자	2	0	2	0	3	6
백채원	0	2	3	7	3	4
도착 여부	O	X	X	X	X	O

백채원이 도착할 수 있는 지점 : 1, 6 

 

 

3. 탐색을 통해 붙잡히지 않고 갈 수 있는 집의 번호를 오름차순 정렬해서 결과로 출력합니다.

 

백채원이 도착할 수 있는 지점 : 1, 6

 

※ 1번 지점은 집이 존재하지 않기 때문에 제외합니다.

 

실질적으로 도착할 수 있는 집 : 6

 

6 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 이용해서 지점과 추종자 및 도로의 정보를 띄어쓰기 기준 나누었습니다.
• dijkstra를 통해서 추종자 및 백채원이 각 지점에 도달하는 최단 거리를 구합니다.
• 최단 거리에 따른 도착할 수 있는 집의 번호를 오름차순 정렬해서 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• searchEnableHouse함수는 다익스트라를 통해서 백채원이 각 지점에 최단 거리를 탐색하여 집에 도달할 수 있는 번호를 구합니다.
• calFollowersDistance함수는 다익스트라를 통해서 각 추종자 위치 기반으로 각 지점에 최단 거리를 구하는 함수입니다.

결과코드

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

public class Main {
    //도로 정보를 정의하는 클래스
    static class Road implements Comparable<Road>{
        int to;
        int distance;

        public Road(int to, int distance) {
            this.to = to;
            this.distance = distance;
        }

        //거리 기준 오름차순 정렬
        @Override
        public int compareTo(Road r) {
            return this.distance- r.distance;
        }
    }
    static List<List<Road>> graph = new ArrayList<>();
    static int[] dist;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //지점, 도로, 추종자 정보 저장
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        //도로 정보 저장
        for(int i=0;i<=N;i++){
            graph.add(new ArrayList<>());
        }
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine()," ");
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int T = Integer.parseInt(st.nextToken());
            graph.get(A).add(new Road(B,T));
            graph.get(B).add(new Road(A, T));
        }
        //최단 거리 정보 배열 초기화
        dist = new int[N+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        //초기 백채원 위치는 최단 거리 0
        dist[1] = 0;
        int[] followers = new int[K];
        st = new StringTokenizer(br.readLine()," ");
        //추종자 위치 정의
        for(int i=0;i<K;i++){
            followers[i] = Integer.parseInt(st.nextToken());
            dist[followers[i]] = 0;
        }
        //각 추종자 최단 거리 탐색 진행
        for(int i=0;i<K;i++){
            calFollowersDistance(followers[i]);
        }
        //백채원 기준 최단 거리 탐색 및 도달하는 집의 정보 저장
        List<Integer> result = searchEnableHouse();

        //도달할 수 있는 집이 없을 때
        if(result.size()==1){
            bw.write("0");
        }else{
            //집의 번호 오름차순 정렬
            Collections.sort(result);
            //집의 번호 BufferedWriter 저장
            for(int i= 1;i<result.size();i++){
                bw.write(String.valueOf(result.get(i)));
                bw.write(" ");
            }
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //백채원 위치 기준 최단 거리를 통해 도달할 수 있는 집을 탐색하는 함수
    static List<Integer> searchEnableHouse(){
        PriorityQueue<Road> pq = new PriorityQueue<>();
        List<Integer> houseList = new ArrayList<>();
        //백채원 초기 위치 저장
        pq.add(new Road(1, 0));
        while(!pq.isEmpty()){
            Road cur = pq.poll();
            //추종자가 먼저 도착한 경우 해당 경로 취소
            if(cur.distance > dist[cur.to]){
                continue;
            }
            //백채원이 도달한 경우
            houseList.add(cur.to);
            //현재 위치에서 인접한 도로 탐색
            for(Road nxt : graph.get(cur.to)){
                int nxtCost = cur.distance + nxt.distance;
                if(nxtCost < dist[nxt.to]){
                    dist[nxt.to] = nxtCost;
                    pq.add(new Road(nxt.to, nxtCost));
                }
            }
        }
        return houseList;	//도착한 집 번호 반환
    }
    //추종자 위치 기준 각 지점 최단 거리 구하는 함수
    static void calFollowersDistance(int followers){
        PriorityQueue<Road> pq = new PriorityQueue<>();
        pq.add(new Road(followers, 0));
        //최단 거리 탐색 진행
        while(!pq.isEmpty()){
            Road cur = pq.poll();
            //최단 거리가 아닐 때
            if(cur.distance > dist[cur.to]){
                continue;
            }
            //인접한 도로를 통한 지점 탐색
            for(Road nxt : graph.get(cur.to)){
                int nxtCost = cur.distance + nxt.distance;
                if(nxtCost < dist[nxt.to]){
                    dist[nxt.to] = nxtCost;
                    pq.add(new Road(nxt.to, nxtCost));
                }
            }
        }
    }
}