[구름톤 챌린지, Java] 19일차, 대체 경로(다익스트라)

문제 링크

 

구름LEVEL

---

접근 방법

이 문제에 핵심

1. N개의 도시가 존재하며, 각 도시롤 연결하는 M개의 양방향 도로가 존재합니다.

2. i일에는 i번째 도시가 공사로 인하여 폐쇄되면서, 해당 도시 관련 도로를 사용할 수 없습니다.

3. 플레이어가 S도시에서 E도시에 도착하지 못하거나 공사 중일 때에는 -1을 결과로 출력합니다.

4. 플레이어가 S도시에서 E도시에 도착할 때 방문하는 최소 도시 개수를 결과로 출력합니다.

5. 결과를 출력할 때에는 각 도시가 공사중일 때 최소 도시 개수를 출력합니다.

 

알고리즘 진행 순서.

 

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

 

2. 1 ~ N번 도시가 공사 중일 때 S도시에서 E도시로 가는 다익스트라 탐색을 진행합니다.

 

3. 모든 탐색으로 얻은 최소 도시 개수를 결과로 출력합니다.

 

 

구현

 

각 도시의 도로를 그래프 형태로 표현합니다.

 

이후 각 도시가 공사중일 때를 기준으로 S도시를 시작으로 다익스트라 탐색을 진행합니다.

 

만약, S, E도시가 공사중이거나, 공사중인 도시로 E도시에 방문하지 못하면 -1을 결과로 출력합니다.

 

다익스트라란??

데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전

 

 

BFS을 진행할 때 특정 조건을 우선적으로 탐색하는 그래프 탐색입니다.

 

 

예제입력을 살펴보시면 이해하시기 편하실 것입니다.

 

 

예제입력 1.

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

 

N : 5

M : 5

S : 1

E : 4

 

 

 

2. 1 ~ N번 도시가 공사 중일 때 S도시에서 E도시로 가는 다익스트라 탐색을 진행합니다.

 

1번 도시 공사중일 때

 

1번 도시는 S(1번) 시작 도시이기 때문에 -1이 결과가 됩니다.

 

2번 도시 공사중일 때

 

 

방문 도시 개수 : 3개

 

3번 도시 공사중일 때

 

방문 도시 개수 : 4개

 

4번 도시 공사중일 때

 

4번 도시는 E(4번) 도착 도시이기 때문에 -1이 결과가 됩니다.

 

5번 도시 공사중일 때

방문 도시 개수 : 3개

 

3. 모든 탐색으로 얻은 최소 도시 개수를 결과로 출력합니다.

 

1	2	3	4	5
-1	3	4	-1	3

 

 

-1

3

4

-1

3

을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 통해 띄어쓰기 기준 입력값을 나누었습니다.
• 각 도시가 공사중일 때 search함수를 통해 최소 방문 도시 개수를 구합니다.
• 공사중인 도시가 시작, 도착 도시일 때 -1을 BufferedWriter 저장합니다.
• 최소 방문 도시의 개수들을 결과로 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 다익스트라를 통해서 지난 도로 개수를 기준으로 우선순위 탐색을 진행합니다.
• search함수는 시작 도시에서 도착 도시에 도달하지 못하면 -1을 결과로 반환합니다.

 

결과코드

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

class Main {
    //다익스트라 탐색을 위한 노드 정보 클래스
    static class Info implements Comparable<Info>{
        /*
        node : 현재 노드
        val : 이동한 도로 개수
        */
        int node, val;
        Info(int node, int val){
            this.node = node;
            this.val = val;
        }
        //이동한 도로 개수 기준 오름차순 정렬
        @Override
        public int compareTo(Info o){
            return this.val - o.val;
        }
    }
    //도로 정보 저장 리스트
    static List<List<Integer>> list  = new ArrayList<>();
    public static void main(String[] args) throws Exception {
        //입력값 처리하는 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 S = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        //도로 리스트 초기화
        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());
            int b = Integer.parseInt(st.nextToken());
            list.get(a).add(b);
            list.get(b).add(a);
        }
        boolean[] visited;
        //각 도시 공사일 때 방문 도시 다익스트라 탐색
        for(int i=1;i<=N;i++){
            //공사중인 도시가 시작, 도착 도시일 때
            if(i == S || i == E){
                bw.write("-1\n");
                continue;
            }
            //방문 도시 여부 배열 초기화
            visited = new boolean[N+1];
            //공사중인 도시 방문 확인
            visited[i] = true;
            //다익스트라 탐색 진행
            int result = search(S, E, visited);
            //방문 도시 개수 BufferedWriter 저장
            bw.write(String.valueOf(result));
            bw.newLine();
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //다익스트라 탐색을 통해 최소 도시 방문 개수 구하는 함수
    static int search(int S, int E, boolean[] visited){
        //다익스트라에 조건 우선순위를 위한 PriorityQueue
        PriorityQueue<Info> pq = new PriorityQueue<>();
        //시작 도시 저장
        pq.add(new Info(S, 1));
        //시작 도시 방문 확인
        visited[S] = true;
        //다익스트라 탐색 진행
        while(!pq.isEmpty()){
            Info cur = pq.poll();
            //가장 먼저 도착 도시에 도착한 경우
            if(cur.node == E){
                return cur.val;	//최소 방문 도시 개수 반환
            }
            //도로로 연결된 인접 도시 탐색
            for(int nxt : list.get(cur.node)){
                //방문하지 않았던 도시 우선 탐색
                if(!visited[nxt]){
                    visited[nxt] = true;
                    pq.add(new Info(nxt, cur.val + 1));
                }
            }
        }
        //도착 도시에 방문하지 못한 경우
        return -1;
    }
}

 

---

느낀 점

 

문제를 처음 접근할 때 i일 동안 도시를 공사한다고 표시되어서, 플레이어가 각 일마다 1번씩 이동하는 것으로 판단하고 문제에 접근해서 생각보다 난이도 있는 문제라고 생각하였습니다.

 

하지만 예제입력에 대한 결과를 관찰하다보니, 제가 잘못 판단한 것을 깨닫게 되었습니다.

 

아직도 문제를 제대로 읽지 않는 제 모습을 보고 자책하면서도 이제부터는 정말 문제에 대해서 자세히 읽으려고 노력해야 겠다는 마음가짐을 갖게 되었습니다.