[goormlevel/Java] Goorm Party 2

-Code

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

class Main {
	static class Pos {
        int num, dist;
        
        public Pos (int num, int dist) {
            this.num = num;
            this.dist = dist;
        }
    }
    static boolean[] visited;
    static List<ArrayList<Integer>> bridge;
    static int[] islandPeopleCnt;

    public static void main(String[] args) throws Exception {
        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());
        // 각 섬에 있는 사람 수 저장
        st = new StringTokenizer(br.readLine());
        islandPeopleCnt = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            islandPeopleCnt[i] = Integer.parseInt(st.nextToken());
        }
        // 왕복 다리 받아서 저장할 리스트 셋팅
        bridge = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            bridge.add(new ArrayList<>());
        }
        // 왕복 다리 셋팅
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            // 양방향 셋팅
            bridge.get(start).add(end);
            bridge.get(end).add(start);
        }
        // bfs로 최단거리 탐색
        visited = new boolean[n + 1];
        int cost = calcCost(1);
        System.out.println(cost);
    }

    private static int calcCost(int start) {
        int answer = 0;
        // 시작 지점 셋팅 및 덱 저장
        visited[start] = true;
        Deque<Pos> deq = new ArrayDeque<>();
        Pos convStart = new Pos(start, 0);
        deq.addLast(convStart);
        // BFS 탐색
        while (!deq.isEmpty()) {
            Pos now = deq.pollFirst();
            // 다음 위치 탐색
            for (int next : bridge.get(now.num)) {
                // 방문하지 않은 경우 검사
                if (!visited[next]) {
                    visited[next] = true;
                    Pos nextPos = new Pos(next, now.dist + 1);
                    answer += islandPeopleCnt[next] * nextPos.dist;
                    deq.addLast(nextPos);
                }
            }
        }
        return answer;
    }
}

최소 비용이라 BFS로 방향을 잡고 풀었습니다. 추가로 거리를 따로 관리해야 하는 부분을 실수로 구현을 안해서 한번 틀렸었습니다.