[알고리즘/Goorm] LV2. 대체 경로 (Java)

 

오늘의 학습 키워드

• BFS 최단거리탐색

오늘의 회고

1. 문제

문제 URL

구름LEVEL

2. 해결 방안

import java.io.*;
import java.util.*;
import java.util.stream.Stream;

/**
 * [구름] LV3. 대체 경로(BFS)
 */
public class AlternativeRoute {

    static List<List<Integer>> list;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = input[0]; // 도시 수
        int m = input[1]; // 도로 수
        int start = input[2]; // 출발 도시
        int end = input[3]; // 도착 도시

        list = new ArrayList<>();
        for(int i=0; i<=n; i++) {
            list.add(new ArrayList<>());
        }
        for(int i=1; i<=m; i++) { // 그래프 리스트
            int[] line = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            list.get(line[1]).add(line[0]);
            list.get(line[0]).add(line[1]);
        }

        for(int i=1; i<=n; i++) {
            System.out.println(bfs(start, end, i, n));
        }

    }

    public static int bfs(int start, int end, int remove, int n) { // n: 도시 수
        Queue<int[]> q = new LinkedList<>(); // 수, 카운트 기록
        visited = new boolean[n+1]; // 방문 기록

        // -1 제약 사항
        int cnt = -1; // 두 도시 이동 불가한 경우
        if(start == remove || end == remove) return -1; // 출발 or 도착 도시 공사 중인 경우

        // 제거 도시 방문 처리
        visited[remove] = true;

        // 처음 값 큐 넣고 방문 처리
        q.add(new int[]{start, 1});
        visited[start] = true;

        while(!q.isEmpty()) {
            int[] node = q.poll();
            List nodeList = list.get(node[0]);

            if(node[0] == end) { // 도착점
                cnt = node[1];
                break;
            }

            for(int i=0; i<nodeList.size(); i++) {
                int now = (int)nodeList.get(i);
                if(!visited[now]) {
                    q.add(new int[]{now, node[1]+1});
                    visited[now] = true;
                }
            }
        }

        return cnt;
    }
}

• 최단거리를 탐색하는 것이니 bfs 알고리즘 사용! bfs 기반으로 코드를 짜고 요구사항에 맞게 조건을 추가한다.
• 큐에 {도시넘버, 누적방문수} 를 넣어 가장 빨리 도달한 거리를 누적 방문수로 뽑을 수 있다.
• 초반에 로직을 두어 두 도시 이동 불가한 경우 or 시작/종료 도시인 경우 -1을 리턴하도록 한다. while문이 끝날때 cnt에 도착점 시점의 카운팅이 저장되어있지 않으면 초기값 -1 으로 리턴된다.
• dfs를 도시 수 만큼 돌릴 때 마다 i번째 도시를 제거했을 때의 최단거리를 구해야 한다. i번째 도시를 제거하기 위한 포인트는 visited[i] = true 처리 하는 것! 초장에 이미 방문 처리 해버리면 방문하지 못할거니, 인접 리스트 제거 같은 귀찮은 작업 없이 도시를 방문하지 않을 수 있다.

3. 피드백

• 처음엔 생각보다 잘 안풀려서 머리가 아팠지만 찬찬히 뜯어보니 dfs에 몇가지 요구사항만 만족시키도록 코드를 짜면 됐다. (드디어 스스로 풀었다 흡흡ㅠ)