📙[Algo] 24.04.19 알고리즘

알고리즘 문제) BOJ 14950. 정복자

14950번: 정복자

문제 요약

• N개의 도시(1~N)와 M개의 도로(양방향)로 구성
• 모든 도시 쌍에는 도로로 이어져 있음
• 각 도로는 비용이 존재
• 모든 도시를 정복하려고 함
• 처음 점거 중인 도시는 1번 도시
• 만약 B도시를 점거하고 싶다면, B와 연결된 도시 중 최소 하나 정복해야 함
  • 만약 A선택하면 B정복과정에서 A와 B를 연결하는 도로 비용도 소모
• 한 번 도시가 정복 되면 모든 도로의 비용이 t만큼 증가
• 이미 정복한 도시는 또 정복 X
• 모든 도시 정복하는 데 드는 최소 비용은?

시간 제한

• 2초

입력

• 도시 개수 N, 도로 개수 M, 한 번 정복시 증가하는 도로 비용 t
  • N은 1만이하 자연수
  • M은 3만이하 자연수
  • t는 10이하 자연수
• M개의 줄에 A B C가 주어짐
  • A와 B사이 비용이 C인 도로
    • A≠B
    • C는 1만 이하 자연수

출력

• 모든 도시 정복하는데 드는 최소 비용

접근법

• 관찰하기
  • 정복 할 때마다 전체 간선이 비용이 t씩 증가한다
  • 즉, 처음부터 간선 비용이 작은 것 부터 선택해야 한다.
  • 또한, 정복할 수 있는 도시는 이미 정복한 노드들과 연결된 도시만 가능한다.
• 사용 알고리즘 : 크루스칼 알고리즘 & 분리집합
• 팁
  • 선택할 때마다 간선 비용이 t씩 증가하는데 mul변수를 만들어서 비용에 더할 때 t*mul을 더해주었다. 이후 mul 1씩 증가.

코드

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

public class Main {
    static int N, M, t;
    static int[][] graph;
    static int[] parent;

    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;
    }

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

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

        graph = new int[M][3];

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

        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());

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

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

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

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

            union(v1, v2);
            answer += (c + t * mul++);
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 11437. LCA

11437번: LCA

문제 요약

• N개의 정점으로 이루어진 트리가 주어지며, 각 정점은 1번부터 N번까지 번호가 매겨짐
  • 루트노드는 1번
• 두 노드의 쌍 M개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상 찾기

시간 제한

• 3초

입력

• 노드 개수 N
  • 2 ≤ N ≤ 5만
• N-1개 줄에 트리 상에서 연결된 두 정점이 주어짐
• 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M
• 다음 M개 줄에 정점 쌍이 주어짐

출력

• M개의 줄에 각 쌍의 가장 가까운 공통 조상 노드 출력

접근법

• 먼저 트리 구조를 만들고(연결요소)
• 루트노드가 1이니 1부터 dfs함수를 돌리면서 각 노드의 부모노드를 저장한다.
• 입력 받은 노드 쌍마다,
  • 각 노드 별로 부모 노드를 타고 올라가면서 리스트에 저장한다.
    • 그럼 가장 가까운 부모노드부터 리스트에 순차적으로 저장된다.
  • 그 중 한 노드의 부모리스트를 돌면서 count배열에 count[부모노드]++를 해준다
  • 그 다음 다른 노드의 부모리스트를 돌면서 만약 count[부모노드]가 0이 아닌 지점을 만나면 해당 노드는 LCA이므로 출력

고민

• 이 방법 말고 직접 리스트 뒤에서 순차적으로 비교하면서 최초로 달라지는 지점을 찾아서 그 뒤에 있는 노드를 반환하려고 하니까 틀린다.. 이 방법으로 다시 풀어보자

코드

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

public class Main {
    static int N, M;
    static ArrayList<Integer>[] graph;
    static int[] parent;
    static ArrayList<Integer> list1 = new ArrayList<>();
    static ArrayList<Integer> list2 = new ArrayList<>();
    static int[] count;


    static void dfs(int cur, int prv) {
        for (Integer nxt : graph[cur]) {
            if (nxt == prv) continue;

            parent[nxt] = cur;
            dfs(nxt, cur);
        }
    }

    static void findParent(int cur, ArrayList<Integer> list) {
        list.add(cur);
        if(parent[cur] == cur) return;

        findParent(parent[cur], list);
    }

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

        N = Integer.parseInt(br.readLine());

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

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

        count = new int[N + 1];

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

            graph[v1].add(v2);
            graph[v2].add(v1);
        }

        dfs(1, 0);

        M = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            v1 = Integer.parseInt(st.nextToken());
            v2 = Integer.parseInt(st.nextToken());

            findParent(v1, list1);
            findParent(v2, list2);

            for (int i = 0, size = list1.size(); i < size; i++) {
                count[list1.get(i)]++;
            }

            for (int i = 0, size = list2.size(); i < size; i++) {
                if (count[list2.get(i)] != 0) {
                    sb.append(list2.get(i)).append("\n");
                    break;
                }
            }

            list1.clear();
            list2.clear();
            Arrays.fill(count, 0);

        }

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}