[백준] 파티 / 자바

문제         

레벨: G3
알고리즘: BFS
풀이시간: 1시간
힌트 참조 유무: 유

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

 

1 번째 시도: 실패   

• 가중치가 있기 때문에 인접리스트 대신 인접행렬 선택
• 갈 때 최단 거리를 구하는 dfs와 돌아올 때 최단 거리를 구하는 dfs2
  • 왜 굳이 dfs를 두개로 나누었나? 
  • 현 코드 dfs 리턴 값은 void로 답을 전역변수에 할당했다.
  • 효율적인건 리턴 값을 int로 하여 전역변수를 사용하지 않는 거다
  • 그러나 구현에 어려움이 있어 답을 전역변수에 할당하고 dfs를 2개로 나뉘었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {

    static int N;
    static int M;
    static int X;
    static boolean[] visited;
    static int[][] arr;
    static int cnt;
    static int cnt2;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");

        N = Integer.parseInt(s1[0]);
        M = Integer.parseInt(s1[1]);
        X = Integer.parseInt(s1[2]);

        visited = new boolean[N + 1];
        arr = new int[N + 1][N + 1];

        //인접행렬 입력
        for(int i=1; i <= N; i++)
            Arrays.fill(arr[i], 0);

        for (int i = 0; i < M; i++) {
            String[] s2 = br.readLine().split(" ");
            for (int j = 0; j < M; j++) {
                arr[Integer.parseInt(s2[0])][Integer.parseInt(s2[1])] = Integer.parseInt(s2[2]);
            }
        }
        int ans = -1;

        for (int i = 1; i <= N; i++) {
            cnt = Integer.MAX_VALUE;
            cnt2 = Integer.MAX_VALUE;
//            System.out.println("i: " + i);
            dfs1(i, 0);
//            System.out.println();
            Arrays.fill(visited, false);
            dfs2(X, 0, i);
            Arrays.fill(visited, false);
            ans = Math.max(cnt+cnt2, ans);
//            System.out.println("ans:" + ans + " cnt: "+ cnt + " cnt2: " + cnt2 +" i: "+ i );

        }

        System.out.println(ans);
    }

    public static void dfs1(int now, int n ) {
        visited[now] = true;
        if (now == X) {
            cnt = Math.min(n,cnt);
            return;
        }

        for (int i = 1; i <= N; i++) {
            if(visited[i] || arr[now][i] == 0)
                continue;
//            System.out.println("now: " + now+ " 다음: " + i);
            dfs1(i, n + arr[now][i]);
        }
    }

    public static void dfs2(int now, int n, int target) {
        visited[now] = true;
        if (now == target) {
            cnt2 = Math.min(n,cnt2);
        }

        for (int i = 1; i <= N; i++) {
            if(visited[i] || arr[now][i] == 0)
                continue;
            dfs2(i, n + arr[now][i], target);
        }
    }
}

• 결과는 실패
• 가중치가 있는 간선 조회는 다익스트라 알고리즘이 맞다

2 번째 시도: 성공  

• 현재 노드에서 목적지 노드에 갈 때 걸리는 최소 거리: 다익스트라 알고리즘
  
  • 만약 모든 노드에서 목적지 노드까지 다익스트라 알고리즘을 이용해 최소거리를 구한다면 n번의 다익스트라 알고리즘을 사용해야 한다.
  • 그러나 방향을 뒤집어 목적지에서 각 노드에 대한 다익스트라 알고리즘을 사용한다면 단 한 번의 다익스트라 알고리즘으로 최소거리를 구할 수 있다.
• 목적지 노드에서 현재 노드로 갈 때 걸리는 최소 거리: 다익스트라 알고리즘
  • 요거는 방향을 뒤집지 않고 주어진 방향대로 탐색하면 된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
class Town implements Comparable<Town> {
    int end;
    int weight;
 
    Town(int end, int weight) {
        this.end = end;
        this.weight = weight;
    }
 
    @Override
    public int compareTo(Town arg0) {
        return weight - arg0.weight;
    }
}
 
public class Main {
    static final int INF = 987654321;
    static ArrayList<ArrayList<Town>> arrList, reverse_arrList;
    static int N, X;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
 
        arrList = new ArrayList<>(); // 문제의 입력을 그대로 받은 배열
        reverse_arrList = new ArrayList<>(); // 문제의 입력을 반대로 받은 배열
 
        for (int i = 0; i <= N; i++) {
            arrList.add(new ArrayList<>());
            reverse_arrList.add(new ArrayList<>());
        }
 
        // arrList와 reverse_arrList를 각각 단방향 인접리스트로 구현
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
 
            arrList.get(start).add(new Town(end, weight));
            reverse_arrList.get(end).add(new Town(start, weight));
        }
 
        int[] dist1 = dijkstra(arrList); // X에서 시작점들 사이의 최단거리
        int[] dist2 = dijkstra(reverse_arrList); // 시작점들에서 X 사이의 최단거리
 
        int ans = 0;
        for (int i = 1; i <= N; i++) {
            ans = Math.max(ans, dist1[i] + dist2[i]);
        }
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
    
    // 다익스트라 알고리즘
    public static int[] dijkstra(ArrayList<ArrayList<Town>> a) {
        PriorityQueue<Town> pq = new PriorityQueue<>();
        pq.offer(new Town(X, 0));
        
        boolean[] check = new boolean[N + 1];
        int[] dist = new int[N + 1];
        Arrays.fill(dist, INF);
        dist[X] = 0;
 
        while (!pq.isEmpty()) {
            Town curTown = pq.poll();
            int cur = curTown.end;
 
            if (!check[cur]) {
                check[cur] = true;
 
                for (Town town : a.get(cur)) {
                    if (!check[town.end] && dist[town.end] > dist[cur] + town.weight) {
                        dist[town.end] = dist[cur] + town.weight;
                        pq.add(new Town(town.end, dist[town.end]));
                    }
                }
            }
        }
        return dist;
    }
 
}