📙[Algo] 24.08.12 알고리즘

알고리즘 문제) BOJ 1595. 북쪽나라의 도로

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

문제 요약

• 두 도시 사이마다 유일한 도로가 설계되어 있다
• 모든 도시는 다른 모든 도시로 이동이 가능 할 때, 거리가 가장 먼 두 도시 사이의 거리를 출력해라
• 최대 10,000개의 도시가 있을 수 있고, 도시는 1 부터 숫자로 이름이 매겨져 있다

시간 제한

• 1초

입력

• 각 줄은 세 개의 양의 정수로 구성되며, 각각은 서로 다른 두 도시 번호와 두 도시를 연결하는 도로의 길이를 의미한다

출력

• 가장 리가 먼 두 도시간의 거리를 나타내는 정수 하나를 출력해라

접근법

• 입력이 언제까지 주어지는지 문제에 안 나와 있어서, 최대 10000개의 도시로 가정하고 풀었다.
  • 입력을 받는 입력이 더이상 주어지지 않아 Error가 발생할 경우를 대비해 while문을 try~catch로 감쌌다.
• 문제에서 모든 도시는 다른 도시로 이동할 수 있으며, 도시간 경로가 단 하나 존재한다고 한 점을 보아 트리라는 것을 확인할 수 있었다.
• 또한, 두 도시중 가장 거리가 먼 경로의 거리를 찾는 문제였기 때문에 트리의 지름 문제라고 판단했다.
  • 따라서, DFS를 진행하면서, 매개변수로 현재 가리키는 노드, 부모 노드(이전 노드), 깊이를 넘겨주었다.
  • 처음에 1을 루트노르라 가정하고 시작해서, max 전역 변수에는 1에서 가장 먼 노드의 깊이(거리)와 maxNode에는 해당 노드의 번호를 저장하도록 했다.
  • 이후, max를 0으로 갱신후에, 다시 dfs로 돌때는, 가장 거리가 멀었던 너드인 maxNode를 루트노드로 가정 후, 해당 노드로부터 가장 거리가 먼 노드와의 거리를 찾았다.

코드

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

public class Main {
    static ArrayList<Node>[] lst = new ArrayList[10001];
    static int max, maxNode;

    static class Node {
        int to;
        int cost;

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

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

        if (max < dist) {
            max = dist;
            maxNode = cur;
        }

        for (Node nxt : lst[cur]) {
            if (nxt.to == prv) continue;

            dfs(nxt.to, cur, dist + nxt.cost);
        }
    }

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

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

        try {
            int a, b, c;
            while (true) {
                st = new StringTokenizer(br.readLine());

                if (st.hasMoreTokens()) {
                    a = Integer.parseInt(st.nextToken());
                    b = Integer.parseInt(st.nextToken());
                    c = Integer.parseInt(st.nextToken());

                    lst[a].add(new Node(b, c));
                    lst[b].add(new Node(a, c));
                } else {
                    break;
                }
            }
        } catch (Exception e) {}

        dfs(1, 0, 0);
        max = 0;
        dfs(maxNode, 0, 0);

        System.out.println(max);


    }
}

 

알고리즘 문제) BOJ 4803. 트리

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

문제 요약

• 그래프가 주어졌을 때, 트리의 개수를 세라!

시간 제한

• 1초

입력

• 각 테스트케이스의 첫째줄에는 정점 개수 n과 간선 개수 m이 주어진다
  • n ≤ 500, m ≤ n*(n-1)
• 다음 m개의 줄에는 간선을 나타내는 두 개의 정수가 주어진다
  • 같은 간선은 여러 번 주어지지 않는다
  • 정점은 1번부터 n번까지 번호가 매겨져 있다
• 입력의 마지막 줄에는 0이 두 개 주어진다

출력

• 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다.

접근법

• 트리 존재 여부와 트리 개수를 출력하는 문제였다
• 트리 조건은 아래와 같다
  • 정점 개수 = 간선 개수 - 1 & 각 정점마다 유일한 간선이 존재(단 하나의 간선)
  • 하나의 연결요소로 이루어질 것
  • 무 사이틀
• 이 문제에서는 입력에서 같은 간선이 여러 번 주어지지 않는다 했으므로, 입력에서는 유일한 간선만이 주어질 것임을 판단할 수 있다.
• 따라서, 사이클 여부를 판단하여, 사이클이 존재하면 트리가 아닌 것, 존재하지 않을 경우 트리로 판단했다.
• 또한, 트리의 개수를 구하는 문제이므로, 사이클이 없는 연결요소의 개수를 구하면 된다.
• 사이클 여부를 판단하기위해 DFS를 돌면서, 매개변수로 현재 노드 cur과 이전 노드(부모노드) prv를 넘겨주었다.
  • 이때, 방문한 노드마다 방문체크를 해주었고,
  • 연결된 다음 노드 nxt를 확인할 때, 이전노드(부모노드)가 아니면서 이미 방문한 노드를 또 방문할 경우 사이클이 있는 것이라 판단하여 false를 return 했다.
  • 그다은 재귀 호출을 진행하는데, 재귀호출 반환값을 if 조건문에 넣어서 return 값이 false일 경우 계속해서 false를 반환하도록 했다.
• 이후 for문에서 1번 노드부터 N번노드 까지 탐색하며
  • 방문하지 않은 노드만 위의 DFS 함수를 호출하면서 반환값 ans가 true일 경우만 카운트 + 1 해주었다.

코드

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

public class Main {
    static int N, M;
    static ArrayList<Integer>[] lst;
    static boolean[] visited;

    static boolean isCycle(int cur, int prv) {
        visited[cur] = true;

        for (Integer nxt : lst[cur]) {
            if (nxt == prv) continue;

            if (visited[nxt]) return false;

            if (!isCycle(nxt, cur)) return false;

        }
        return true;
    }

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

        StringBuilder sb = new StringBuilder();
        int a, b, tnum = 1;
        while (true) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            if (N == 0) break;

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

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

                lst[a].add(b);
                lst[b].add(a);
            }


            // 트리 판단하기
            // 1. 무 사이클
            // 2. 정점 개수 - 1 = 간선 개수
            visited = new boolean[N + 1];
            boolean ans; int cnt = 0;
            for (int i = 1; i <= N; i++) {
                if (visited[i]) continue;
                ans = isCycle(i, 0);
                if (ans) cnt++;
            }

            if (cnt == 0) {
                sb.append("Case ").append(tnum++).append(": No trees.\n");
            } else if (cnt == 1) {
                sb.append("Case ").append(tnum++).append(": There is one tree.\n");
            } else {
                sb.append("Case ").append(tnum++).append(": A forest of ").append(cnt).append(" trees.\n");
            }
        }

        System.out.println(sb);
    }
}