[JAVA] 다익스트라 알고리즘 뿌수기2

 

이전 글

https://fladi.tistory.com/399

[JAVA] 다익스트라 알고리즘 뿌수기

 

 

 

13424 비밀 모임 - 골드4

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

13424번: 비밀 모임

• 글 굉장히 많다
• 하지만 잘 읽어보면 다익스트라를 여러 번 쓰면 된다는 걸 알 수 있다 
• (플루이드 워샬까지는 투머치 같다)

 

class Node implements Comparable<Node> {
    int value;
    int end;

    public Node(int value, int end) {
        this.value = value;
        this.end = end;
    }

    @Override
    public int compareTo(Node o) {
        return value - o.value;
    }
}

public class Main {
    static int[] total;
    static ArrayList<Node>[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tcCnt = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int tc = 0; tc<tcCnt; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int roomCnt = Integer.parseInt(st.nextToken());
            int aisleCnt = Integer.parseInt(st.nextToken());

            arr = new ArrayList[roomCnt];

            for (int i = 0; i<arr.length; i++) {
                arr[i] = new ArrayList<>();
            }

            for (int i =0; i<aisleCnt; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken())-1;
                int b = Integer.parseInt(st.nextToken())-1;
                int c = Integer.parseInt(st.nextToken());

                arr[a].add(new Node(c, b));
                arr[b].add(new Node(c, a));
            }

            int friendCnt = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            int[] friends = new int[friendCnt];
            for (int i =0; i<friendCnt; i++) {
                friends[i] = Integer.parseInt(st.nextToken())-1;
            }

            total = new int[roomCnt];

            for (int i =0; i<friendCnt; i++) {
                dijkstra(friends[i]);
            }

            int roomNum = 1;
            int min = Integer.MAX_VALUE;
            for (int i =0; i<roomCnt; i++) {
                if (min >total[i]) {
                    roomNum = i+1;
                    min = total[i];
                }
            }

            sb.append(roomNum + "\n");
        }
        System.out.print(sb);
    }

    private static void dijkstra(int num) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(0, num));

        boolean[] visited = new boolean[arr.length];

        int[] values = new int[arr.length];
        Arrays.fill(values, Integer.MAX_VALUE);
        values[num] = 0;

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            int curr = currentNode.end;

            if (!visited[curr]) {
                visited[curr] = true;
                total[curr] += values[curr];

                for (Node adj: arr[curr]) {
                    if (!visited[adj.end] && values[adj.end] > values[curr] + adj.value) {
                        values[adj.end] = values[curr] + adj.value;

                        pq.add(new Node(values[adj.end], adj.end));
                    }
                }
            }
        }
    }
}

• 친구가 있는 방에 대해 모든 방까지 거리를 total에 저장하고
• 가장 작은 값을 가진 방을 출력

 

 

 

14497 주난의 난 - 골드4

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

14497번: 주난의 난(難)

• 문제가 너무 웃겨서 재밌게 풀었다! 쿵.. 쿵..

class Location {
    int row;
    int col;

    public Location(int row, int col) {
        this.row = row;
        this.col = col;
    }
}

class Node implements Comparable<Node>{
    Location end;
    int value;

    public Node(Location end, int value) {
        this.end = end;
        this.value = value;
    }

    @Override
    public int compareTo(Node o) {
        return value - o.value;
    }
}

public class Main {
    static char[][] arr;
    static int[] rowStep = {0,0,-1,1};
    static int[] colStep = {-1,1,0,0};

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

        int rowLen = Integer.parseInt(st.nextToken());
        int colLen = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        Location junan = new Location(Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken())-1);
        Location suspect = new Location(Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken())-1);

        arr = new char[rowLen][colLen];

        for (int i =0; i<rowLen; i++) {
            String input = br.readLine();
            for (int j =0; j<colLen; j++) {
                arr[i][j] = input.charAt(j);
            }
        }

        System.out.print(dijkstra(junan, suspect));
    }

    private static int dijkstra(Location junan, Location suspect) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(junan, 0));

        boolean[][] visited = new boolean[arr.length][arr[0].length];
        int[][] values = new int[arr.length][arr[0].length];

        for (int i =0; i<values.length; i++) {
            Arrays.fill(values[i], Integer.MAX_VALUE);
        }

        values[junan.row][junan.col] = 0;

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            Location curr = currentNode.end;

            if (!visited[curr.row][curr.col]) {
                visited[curr.row][curr.col] = true;

                if (curr.row == suspect.row && curr.col == suspect.col) {
                    break;
                }

                for (int i =0; i<4; i++) {
                    int tmpRow = curr.row + rowStep[i];
                    int tmpCol = curr.col + colStep[i];

                    if (tmpRow < 0 || tmpRow >= arr.length || tmpCol < 0 || tmpCol >=arr[0].length) {
                        continue;
                    }

                    int plus = 0;
                    if (arr[tmpRow][tmpCol] != '0') {
                        plus = 1;
                    }

                    if (!visited[tmpRow][tmpCol] && values[tmpRow][tmpCol] > values[curr.row][curr.col] + plus) {
                        values[tmpRow][tmpCol] = values[curr.row][curr.col] + plus;
                        pq.add(new Node(new Location(tmpRow, tmpCol), values[tmpRow][tmpCol]));
                    }
                }
            }
        }

        return values[suspect.row][suspect.col];
    }
}

 

• 사람이 없을 땐 value를 그대로 유지
• 사람이 있으면 value를 1 증가
• 그 외에는 그냥 다익스트라다

 

 

 

 

14938 서강그라운드 - 골드4

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

14938번: 서강그라운드

• 골드 4쯤 오니 플루이드 워샬 냄새가 나기 시작한다
• 한 알고리즘을 집중적으로 파다보면 느껴지는게, 골드4를 기준으로 새로운, 딥한 알고리즘이 등장하는듯
  • ex) 유니온 파인드, LIS, 등등..
• 일단 각각 다익스트라로 풀어봤고, 플루이드 워샬로두 풀어보려고 함

 

다익스트라 풀이

class Node implements Comparable<Node> {
    int length;
    int end;

    public Node(int length, int end) {
        this.length = length;
        this.end = end;
    }

    @Override
    public int compareTo(Node o) {
        return length - o.length;
    }
}

public class Main {
    static ArrayList<Node>[] arr;
    static int[] items;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=  new StringTokenizer(br.readLine());
        int countryCnt = Integer.parseInt(st.nextToken());
        int scope = Integer.parseInt(st.nextToken());
        int roadCnt = Integer.parseInt(st.nextToken());

        items = new int[countryCnt];
        st = new StringTokenizer(br.readLine());
        for (int i =0; i<items.length; i++) 
            items[i] = Integer.parseInt(st.nextToken());

        arr = new ArrayList[countryCnt];
        for (int i =0; i<arr.length; i++) 
            arr[i] = new ArrayList<>();

        for (int i =0; i<roadCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            int l = Integer.parseInt(st.nextToken());

            arr[a].add(new Node(l, b));
            arr[b].add(new Node(l, a));
        }

        int max = 0;
        for (int i =0; i<arr.length; i++) {
            int tmpMax = dijkstra(i, scope);
            if (tmpMax > max) {
                max = tmpMax;
            }
        }

        System.out.println(max);
    }

    private static int dijkstra(int start, int scope) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(0, start));

        boolean[] visited = new boolean[arr.length];
        int sum = 0;

        int[] scopes = new int[arr.length];
        Arrays.fill(scopes, Integer.MAX_VALUE);
        scopes[start] = 0;

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            int curr = currentNode.end;

            if (!visited[curr]) {
                visited[curr] = true;
                sum += items[curr];

                for (Node node: arr[curr]) {
                    if (!visited[node.end] && scopes[node.end] > scopes[curr] + node.length) {
                        scopes[node.end] = scopes[curr] + node.length;
                        if (scopes[node.end] <= scope) {
                            pq.add(new Node(scopes[node.end], node.end));
                        }
                    }
                }
            }
        }

        return sum;
    }
}

 

 

플루이드 워샬 풀이

class Node {
    int length;
    int end;

    public Node(int length, int end) {
        this.length = length;
        this.end = end;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=  new StringTokenizer(br.readLine());
        int countryCnt = Integer.parseInt(st.nextToken());
        int scope = Integer.parseInt(st.nextToken());
        int roadCnt = Integer.parseInt(st.nextToken());

        int[] items = new int[countryCnt];
        st = new StringTokenizer(br.readLine());
        for (int i =0; i<items.length; i++)
            items[i] = Integer.parseInt(st.nextToken());

        int[][] floyd = new int[countryCnt][countryCnt];
        for (int i =0; i<floyd.length; i++) {
            Arrays.fill(floyd[i], Integer.MAX_VALUE);
            floyd[i][i] = 0;
        }

        for (int i =0; i<roadCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            int l = Integer.parseInt(st.nextToken());

            floyd[a][b] = l;
            floyd[b][a] = l;
        }

        for (int k =0; k<countryCnt; k++) {
            for (int i =0; i<countryCnt; i++) {
                if (i == k)
                    continue;

                for (int j = 0; j<countryCnt; j++) {
                    if (j == k || j == i)
                        continue;

                    if (floyd[i][k] != Integer.MAX_VALUE && floyd[k][j] != Integer.MAX_VALUE)
                        floyd[i][j] = Math.min(floyd[i][j], floyd[i][k] + floyd[k][j]);
                }
            }
        }

        int max = 0;
        for (int i =0; i<floyd.length; i++) {
            int sum = items[i];
            for (int j =0; j<floyd.length; j++) {
                if (i == j)
                    continue;

                if (floyd[i][j] <= scope) {
                    sum += items[j];
                }
            }

            if (sum > max)
                max = sum;
        }

        System.out.println(max);
    }
}

• 플루이드 워샬로 거리를 구한 후, 거리가 scope 미만인 것들의 item을 더하는 방식 사용
• 그냥 플루이드 워샬인 것 빼곤 뭐가 없다

 

• 다익스트라가 시간도 더 빠르고 메모리도 덜 잡아먹는다 흠
• 하지만 코드 자체는 플루이드가 훨씬 간결하다

 

 

 

18223 민준이와 마산 그리고 건우 - 골드4

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

18223번: 민준이와 마산 그리고 건우

• 민준 -> 마산 최단경로가 민준 -> 건우 -> 마산 최단경로와 같다면 SAVE HIM, 다르다면 GOOD BYE 출력하면 될듯
• 다익스트라 잘 돌리면 될 것 같다

 

class Node implements Comparable<Node> {
    int cost;
    int end;

    public Node(int cost, int end) {
        this.cost = cost;
        this.end = end;
    }

    @Override
    public int compareTo(Node o) {
        return cost - o.cost;
    }
}

public class Main {
    static ArrayList<Node>[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=  new StringTokenizer(br.readLine());
        int nodeCnt = Integer.parseInt(st.nextToken());
        int relationCnt = Integer.parseInt(st.nextToken());
        int gunwoo = Integer.parseInt(st.nextToken())-1;

        arr = new ArrayList[nodeCnt];
        for (int i =0; i<arr.length; i++) {
            arr[i] = new ArrayList();
        }

        for (int i =0; i<relationCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            int distance = Integer.parseInt(st.nextToken());
            arr[a].add(new Node(distance, b));
            arr[b].add(new Node(distance, a));
        }

        int globalMin = dijkstra(0, nodeCnt-1);
        int saveMin = dijkstra(0, gunwoo) + dijkstra(gunwoo, nodeCnt-1);

        if (globalMin == saveMin) {
            System.out.println("SAVE HIM");
        } else{
            System.out.println("GOOD BYE");
        }
    }

    private static int dijkstra(int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(0, start));

        boolean[] visited = new boolean[arr.length];
        int[] values = new int[arr.length];
        Arrays.fill(values, Integer.MAX_VALUE);

        values[start] = 0;

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            int current = currentNode.end;

            if (!visited[current]) {
                visited[current] = true;

                if (current == end) {
                    break;
                }

                for (Node adj: arr[current]) {
                    if (!visited[adj.end] && values[adj.end] > values[current] + adj.cost) {
                        values[adj.end] = values[current] + adj.cost;
                        pq.add(new Node(values[adj.end], adj.end));
                    }
                }
            }
        }

        return values[end];
    }
}

• 정말 별거없는 다익스트라 문제

 

 

 

1238 파티 - 골드3

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

1238번: 파티

• 드디어 단방향이 나왔다
• 각 학생들에 대해 마을 X로 가는 거리를 구한 후, 최댓값을 가지는 학생을 구하면 될 것 같다
• 그냥 다익스트라인듯

 

class Node implements Comparable<Node> {
    int time;
    int end;

    public Node(int time, int end) {
        this.time = time;
        this.end = end;
    }

    @Override
    public int compareTo(Node o) {
        return time - o.time;
    }
}

public class Main {
    static ArrayList<Node>[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int studentCnt = Integer.parseInt(st.nextToken());
        int roadCnt = Integer.parseInt(st.nextToken());
        int partyHall = Integer.parseInt(st.nextToken())-1;

        arr =  new ArrayList[studentCnt];
        for (int i =0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i =0; i<roadCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken())-1;
            int end = Integer.parseInt(st.nextToken())-1;
            int time = Integer.parseInt(st.nextToken());

            arr[start].add(new Node(time, end));
        }

        int max = 0;
        for (int i =0; i<studentCnt; i++) {
            int sum = 0;
            sum += dijkstra(i, partyHall);
            sum += dijkstra(partyHall, i);

            if (sum > max) {
                max = sum;
            }
        }

        System.out.println(max);
    }

    private static int dijkstra(int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(0, start));

        boolean[] visited = new boolean[arr.length];
        int[] values = new int[arr.length];
        Arrays.fill(values, Integer.MAX_VALUE);
        values[start] = 0;

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            int current = currentNode.end;

            if (!visited[current]) {
                visited[current] = true;

                if (current == end) {
                    break;
                }

                for (Node adj: arr[current]) {
                    if (!visited[adj.end] && values[adj.end] > values[current] + adj.time) {
                        values[adj.end] = values[current] + adj.time;
                        pq.add(new Node(values[adj.end], adj.end));
                    }
                }
            }
        }

        return values[end];
    }
}

• 별 거 없는 다익스트라 문제

 

 

 

1719 택배 - 골드3

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

1719번: 택배

• 마지막 뿌수기 문제다
• 플로이드 워샬로 풀어달라고 속삭이는게 들린다
• 플로이드 워샬로 풀되, 경로도 저장하면 될듯

 

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int buildingCnt = Integer.parseInt(st.nextToken());
        int roadCnt = Integer.parseInt(st.nextToken());

        int[][] floyd = new int[buildingCnt][buildingCnt];
        int[][] next = new int[buildingCnt][buildingCnt];
        for (int i =0; i<floyd.length; i++) {
            Arrays.fill(floyd[i], Integer.MAX_VALUE);
            floyd[i][i] = 0;
            next[i][i] = 0;
        }

        for (int i =0; i<roadCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            int time = Integer.parseInt(st.nextToken());

            floyd[a][b] = time;
            floyd[b][a] = time;
            next[a][b] = b;
            next[b][a] = a;
        }

        for (int k =0; k<buildingCnt; k++) {
            for (int i=0; i<buildingCnt; i++) {
                if (i == k)
                    continue;

                for (int j=0; j<buildingCnt; j++) {
                    if (j == k || j == i)
                        continue;

                    if (floyd[i][k] != Integer.MAX_VALUE && floyd[k][j] != Integer.MAX_VALUE) {
                        if (floyd[i][k] + floyd[k][j] < floyd[i][j]) {
                            floyd[i][j] = floyd[i][k] + floyd[k][j];
                            next[i][j] = next[i][k];
                        }
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i =0; i<buildingCnt; i++) {
            for (int j =0; j<buildingCnt; j++) {
                if (i == j) {
                    sb.append("- ");
                } else {
                    sb.append(next[i][j]+1 + " ");
                }
            }
            sb.append("\n");
        }

        System.out.print(sb);
    }
}

• 그냥 다음 경로만 잘 지정해주면 된다
• i에서 j로 갈 때 거쳐가야하는 다음노드는 i에서 k로갈 때 거쳐가야하는 다음노드로 지정해주면 그냥 끝난다
• 운좋게 맞았지만 아직 조금 헷갈려서 더 공부해야할듯