📙[Algo] 24.04.15 알고리즘

알고리즘 문제) BOJ 20040. 사이클 게임

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

문제 요약

• 0부터 n-1의 번호가 부여된 고유한 점들이 N개 주어지며, 매 차례마다
• 두 점을 선택 해 선분을 이음
• 이 때 사이클이 만들어지는 순간을 찾아서 해당 몇 번째 차례에서 처음으로 만들어졌는지 출력(없다면 0 출력)

시간 제한

• 1초

입력

• 첫 번째 줄에는 점의 개수를 나타내는 정수 3 ≤ n ≤ 500,000 과 진행된 차례의 수를 나타내는 정수 3 ≤ m ≤ 1,000,000 이 주어진다
• 이어지는 m 개의 입력 줄에는 각각 i번째 차례에 해당 플레이어가 선택한 두 점의 번호가 주어진다

출력

• 사이클이 처음으로 만들어진 차례의 번호를 양의 정수로 출력
  • m 번의 차례를 모두 처리한 이후에도 종료되지 않았다면 0을 출력

코드

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

public class Main {
    static int N, M;
    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());

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

        int a, b;
        int answer = 1;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());

            if (find(a) == find(b)) {
                bw.write(String.valueOf(answer));
                break;
            }

            union(a, b);
            answer++;
        }

        if (answer > M) bw.write("0");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 1504. 특정한 최단 경로

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

문제 요약

• 무방향 그래프가 주어짐
• 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 함
• 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다
• 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성

시간 제한

• 1초

입력

• 정점의 개수 N과 간선의 개수 E
  • (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000)
• 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻
  • (1 ≤ c ≤ 1,000)
• 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1)
• 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재

출력

• 첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력
• 그러한 경로가 없을 때에는 -1을 출력

접근법

• 아래 두 가지 케이스가 존재
  • 1에서 v1으로 갈 수 있는 최단 경로 + v1에서 v2로 갈 수 있는 최단 경로 + v2에서 N으로 갈 수 있는 최단 경로
  • 1에서 v2으로 갈 수 있는 최단 경로 + v2에서 v1로 갈 수 있는 최단 경로 + v1에서 N으로 갈 수 있는 최단 경로

코드

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

public class Main {
    static int N, E;
    static ArrayList<Node>[] list;
    static int u, v;
    static int[] dist;
    static boolean[] visited;

    static class Node implements Comparable<Node> {
        int no;
        int cost;

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

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

    static void dijks(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        dist[start] = 0;
        pq.offer(new Node(start, 0));

        int cur, nxt, nc;
        while (!pq.isEmpty()) {
            cur = pq.poll().no;

            if (visited[cur]) continue;

            visited[cur] = true;

            for (Node node : list[cur]) {
                nxt = node.no;
                nc = dist[cur] + node.cost;

                dist[nxt] = Math.min(dist[nxt], nc);
                pq.offer(new Node(nxt, dist[nxt]));
            }
        }
    }

    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());
        E = Integer.parseInt(st.nextToken());

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

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

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

        st = new StringTokenizer(br.readLine());
        u = Integer.parseInt(st.nextToken());
        v = Integer.parseInt(st.nextToken());

        int stou, stov, utov, vtou, vtoe, utoe;

        dist = new int[N + 1];
        Arrays.fill(dist, 1 << 30);
        visited = new boolean[N + 1];
        dijks(1);
        stou = dist[u];
        stov = dist[v];

        Arrays.fill(visited, false);
        Arrays.fill(dist, 1 << 30);
        dijks(u);
        utov = dist[v];
        utoe = dist[N];

        Arrays.fill(visited, false);
        Arrays.fill(dist, 1 << 30);
        dijks(v);
        vtou = dist[u];
        vtoe = dist[N];

        int dist1 = stou + utov + vtoe;
        int dist2 = stov + vtou + utoe;

        boolean check1 = true;
        boolean check2 = true;

        if (stou == 1 << 30 || utov == 1 << 30 || vtoe == 1 << 30) {
            check1 = false;
        }

        if (stov == 1 << 30 || vtou == 1 << 30 || utoe == 1 << 30) {
            check2 = false;
        }

        if (!check1 && check2) {
            bw.write(String.valueOf(dist2));
        } else if (check1 && !check2) {
            bw.write(String.valueOf(dist1));
        } else if (check1 && check2) {
            bw.write(String.valueOf(Math.min(dist1, dist2)));
        } else {
            bw.write("-1");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}