📙[Algo] 24.05.29 알고리즘

알고리즘 문제) BOJ 2350. 대운하

• 링크 : https://www.acmicpc.net/problem/2350

문제 요약

• N개의 도시 존재, M개의 운하 건설
• K개의 노선 준비
  • 각 노선의 도시 i와 j간을 운행하는 배는 도시 i와 j간 경로에 포함된 운하를 통과할 수 있어야 함
  • 배는 배의 크기 이상 폭의 운하만 통과가 가능하다
• K개의 줄에 각 노선을 운행할 수 있는 최대 배의 폭을 출력

시간 제한

• 1초

입력

• 도시의 수 N, 운하의 수 M, 노선의 수 K
  • N ≤ 1000,
  • M ≤ 100000,
  • K ≤ 10000
• M개의 줄에는 세 정수 i, j, w
  • 도시 i와 j 사이에 폭이 w인 운하를 건설할 것임을 의미
    • 1 ≤ i, j ≤ N, w ≤ 200
• K개의 줄에는 각 노선이 연결하는 도시 i, j
  • 1 ≤ i, j ≤N

출력

• K개의 줄에 각 노선을 운행할 수 있는 최대 배의 폭을 출력

접근법

• 도시간 경로에 포함된 운하를 배는 모두 통과할 수 있어야한다.
• 이때, 배의 크기를 가장 큰 경우를 찾아야 하므로,
  • 우선 모든 도시를 있는 경로를 찾되, 최대한 운하 폭이 큰 경로 위주로 찾았다 ⇒ 즉, MST를 만듬(운하 폭이 큰 경로 부터 선택하도록)
  • 그 다음 주어진 두 도시 간 경로를 dfs로 탐색하면서, 만나는 경로 중 가장 최소 크기의 경로를 출력하도록 했다.

코드

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

public class Main {
    static int N, M, K;
    static int[][] arr;
    static int[] parent;
    static ArrayList<Node>[] lst;
    static int start, end, ans;

    static class Node{
        int to;
        int cost;

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

    static int find(int x) {
        if (parent[x] == x) return x;

        parent[x] = find(parent[x]);
        return parent[x];
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b) return;

        parent[b] = a;
    }

    static void dfs(int cur, int prv, int minC) {

        if (cur == end) ans = minC;

        int nxt, nc;
        for (Node node : lst[cur]) {
            nxt = node.to;
            nc = node.cost;

            if (prv == nxt) continue;

            dfs(nxt, cur, Math.min(minC, nc));
        }
    }

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        arr = new int[M][3];

        int v1, v2, c;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            v1 = Integer.parseInt(st.nextToken());
            v2 = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            arr[i][0] = v1;
            arr[i][1] = v2;
            arr[i][2] = c;
        }

        Arrays.sort(arr, (o1,o2)->{
            return o2[2] - o1[2];});

        parent = new int[N + 1];
        for (int i = 0; i < N + 1; i++) {
            parent[i] = i;
        }

        lst = new ArrayList[N + 1];
        for (int i = 0; i < N + 1; i++) {
            lst[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            v1 = arr[i][0];
            v2 = arr[i][1];
            c = arr[i][2];

            if (find(v1) == find(v2)) continue;

            union(v1, v2);
            lst[v1].add(new Node(v2, c));
            lst[v2].add(new Node(v1, c));
        }

        StringBuilder sb = new StringBuilder();
        while (K-- > 0) {
            st = new StringTokenizer(br.readLine());
            start = Integer.parseInt(st.nextToken());
            end = Integer.parseInt(st.nextToken());

            ans = 210;
            dfs(start, 0, 210);
            sb.append(ans).append("\n");
        }

        System.out.println(sb);

        br.close();
    }
}

 

알고리즘 문제) BOJ 31804. Chance!

• 링크 : https://www.acmicpc.net/problem/31804

문제 요약

• a에서 b로 갈 때 다음 3가지 마법을 쓸 수 있다.
  • 더하기 1
  • 곱하기 2
  • 곱하기 10 → 그러나 이것은 딱 한 번만 사용 가능
• a에서 b로 가기까지 최소한으로 사용한 마법 수 출력

시간 제한

• 1초

입력

• a b
  • 1 ≤ a < b ≤ 1000000

출력

• a를 b로 만들기 위해 필요한 최소 마법 사용 횟수를 출력

접근법

• 순간이동 문제랑 거의 똑같았다 → bfs
• chance 사용 여부에 따른 2차원 방문 체크 배열 필요

코드

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

public class Main {
    static int a, b;
    static boolean[][] visited = new boolean[1000010][2];
    static int[] mul = {1, 2, 10};
    static int[] plus = {1, 0, 0};

    static int bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{a, 1});
        visited[a][1] = true;

        int cur, chance, nxt, size, cnt = 0;
        while (!q.isEmpty()) {
            size = q.size();

            for (int s = 0; s < size; s++) {
                cur = q.peek()[0];
                chance = q.poll()[1];

                if (cur == b) {
                    return cnt;
                }

                for (int i = 0; i < 2 + chance; i++) {
                    nxt = mul[i] * cur + plus[i];

                    if (nxt > b) continue;

                    if (i == 2) {
                        if (!visited[nxt][chance - 1]) {
                            visited[nxt][chance - 1] = true;
                            q.offer(new int[]{nxt, chance - 1});
                        }
                    } else {
                        if (!visited[nxt][chance]) {
                            visited[nxt][chance] = true;
                            q.offer(new int[]{nxt, chance});
                        }
                    }
                }
            }

            cnt++;
        }

        return -1;
    }

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

        st = new StringTokenizer(br.readLine());
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());

        System.out.println(bfs());

        br.close();
    }
}