์šฐ๊ทœ์ด์ธ์šฐ์œค
Eager To Learn ๐ŸŒŒ
์šฐ๊ทœ์ด์ธ์šฐ์œค
์ „์ฒด ๋ฐฉ๋ฌธ์ž
์˜ค๋Š˜
์–ด์ œ

๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

  • ๐Ÿก ํ™ˆ
  • ๐Ÿš€ ๊นƒํ—ˆ๋ธŒ
  • โ›… ํƒœ๊ทธ ํด๋ผ์šฐ๋“œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (217)
    • ๐Ÿ‘จ๐Ÿป‍๐Ÿ’ป PS (170)
      • JAVA (82)
      • MYSQL (1)
      • Docker (2)
      • PYTHON (24)
      • LeetCode 150 (39)
      • Algorithm ๊ธฐ๋ฒ• (1)
      • ๋ฐ”ํ‚น๋… (21)
    • ๋ธ”๋กœ๊ทธ ์ด์‚ฌ (0)
    • Error (1)
    • CS (15)
      • DataBase (2)
      • OS (7)
      • Network (1)
      • Spring (1)
      • ์ž๋ฃŒ๊ตฌ์กฐ (3)
      • Java (1)
    • Learned (7)
      • Spring (7)
    • ๊ฐœ๋ฐœ์„œ์  (15)
      • ๊ฐ€์ƒ ๋ฉด์ ‘ ์‚ฌ๋ก€๋กœ ๋ฐฐ์šฐ๋Š” ๋Œ€๊ทœ๋ชจ ์‹œ์Šคํ…œ ์„ค๊ณ„ ๊ธฐ์ดˆ (1)
      • ์˜ค๋ธŒ์ ํŠธ - ์กฐ์˜ํ˜ธ (7)
      • ์นœ์ ˆํ•œ SQL ํŠœ๋‹ (7)
    • ํšŒ๊ณ  (2)
hELLO ยท Designed By ์ •์ƒ์šฐ.
์šฐ๊ทœ์ด์ธ์šฐ์œค

Eager To Learn ๐ŸŒŒ

๐Ÿ‘จ๐Ÿป‍๐Ÿ’ป PS/๋ฐ”ํ‚น๋…

[JAVA] ๋ฐฑ์ค€ 1967๋ฒˆ ใ€G4.ํŠธ๋ฆฌ์˜ ์ง€๋ฆ„ใ€‘

2023. 10. 5. 09:21

๋ฌธ์ œ

 

1967๋ฒˆ: ํŠธ๋ฆฌ์˜ ์ง€๋ฆ„

ํŒŒ์ผ์˜ ์ฒซ ๋ฒˆ์งธ ์ค„์€ ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜ n(1 ≤ n ≤ 10,000)์ด๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ n-1๊ฐœ์˜ ์ค„์— ๊ฐ ๊ฐ„์„ ์— ๋Œ€ํ•œ ์ •๋ณด๊ฐ€ ๋“ค์–ด์˜จ๋‹ค. ๊ฐ„์„ ์— ๋Œ€ํ•œ ์ •๋ณด๋Š” ์„ธ ๊ฐœ์˜ ์ •์ˆ˜๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ์ฒซ ๋ฒˆ์งธ ์ •์ˆ˜๋Š” ๊ฐ„์„ ์ด ์—ฐ

www.acmicpc.net

 

ํ’€์ด

1๏ธโƒฃ dfs๋ฅผ ์ด์šฉํ•œ ํ’€์ด

๐Ÿ’ก ๋– ์˜ค๋ฅธ Idea

์ฒ˜์Œ์—๋Š” ๋ฌธ์ œ์—์„œ ์นœ์ ˆํ•˜๊ฒŒ ๋ถ€๋ชจ ๋…ธ๋“œ๋ฅผ ๋ช…์‹œํ•ด์„œ ์•Œ๋ ค์ค˜์„œ ๋‹ค๋ฅธ ๋ฐฉํ–ฅ์œผ๋กœ ๋งŽ์ด ์ƒ๊ฐํ–ˆ๋˜ ๊ฒƒ ๊ฐ™๋‹ค.

๊ทผ๋ฐ, ์ด ๋ฌธ์ œ๋Š” ๋ถ€๋ชจ ๋…ธ๋“œ๋ฅผ ํŠน์ •ํ•ด์„œ ๋ฌธ์ œ๋ฅผ ํ’€๊ธฐ๋ณด๋‹ค๋Š” ๋ชจ๋“  ๋…ธ๋“œ๊ฐ€ ๋ฃจํŠธ ๋…ธ๋“œ๊ฐ€ ๋  ์ˆ˜ ์žˆ์Œ์„ ๊ฐ€์ •ํ•ด์„œ ํ‘ธ๋Š” ๊ฒƒ์ด ํŽธ๋ฆฌํ•˜๋‹ค.


์˜ˆ์‹œ์—์„œ ๋‚˜์˜จ ๊ทธ๋ฆผ์€ ์œ„์™€ ๊ฐ™์€๋ฐ ์‚ฌ์‹ค ์œ„ ๊ทธ๋ฆผ์€


9 ๋ฅผ ์ตœ์ƒ๋‹จ ๋…ธ๋“œ๋ผ๊ณ  ์ƒ๊ฐํ•˜๊ณ  ๊ทธ๋ฆฌ๋ฉด ์œ„์™€ ๊ฐ™์ด ๊ทธ๋ ค์งˆ ์ˆ˜ ์žˆ๋‹ค.

๊ทธ๋ฆฌ๊ณ  9 → 5 → 3 → 6 → 12 ๋…ธ๋“œ ์ˆœ์œผ๋กœ ๊ฐ€๋ฉด ์˜ˆ์ œ์˜ ๋‹ต์ด ๋‚˜์˜จ๋‹ค๋Š” ์‚ฌ์‹ค์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค.

์ฆ‰, ๋ชจ๋“  ๋…ธ๋“œ๋ฅผ ์ตœ์ƒ๋‹จ ๋ฃจํŠธ๋กœ ๊ฐ€์ •ํ•ด๋ณด๊ณ 

๊ฐ ๋ฃจํŠธ์—์„œ dfs ๋กœ ๊นŠ์ด ํƒ์ƒ‰์„ ํ–ˆ์„ ๋•Œ, ๊ฐ€์ค‘์น˜๋ฅผ ์ตœ๋Œ“๊ฐ’์œผ๋กœ ๊ฐฑ์‹ ํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ์‚ฌ์šฉํ•˜๋ฉด ์ตœ๋Œ€ ์ง€๋ฆ„์„ ๊ตฌํ•  ์ˆ˜ ์žˆ๊ฒŒ ๋œ๋‹ค.

 

public class Main {
    static int sum = 0;
    static int ans = 0;
    static boolean[] checked;
    static Node[] nodes;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        checked = new boolean[N + 1];
        nodes = new Node[N + 1];

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

        for (int i = 0; i < N - 1; i++) {
            String[] input = br.readLine().split(" ");
            int u = Integer.parseInt(input[0]);
            int v = Integer.parseInt(input[1]);
            int cost = Integer.parseInt(input[2]);

            Node U = new Node(u, cost);
            Node V = new Node(v, cost);

            nodes[u].connects.add(V);
            nodes[v].connects.add(U);

        }

        for (int i = 1; i <= N; i++) {
            Node root = nodes[i];
            checked[root.idx] = true;
            dfs(root);
            checked[root.idx] = false;
        }
        System.out.println(ans);

    }

    private static void dfs(Node node) {
        ans = Math.max(ans, sum);

        for (Node connect : node.connects) {
            if (!checked[connect.idx]) {
                sum += connect.cost;
                checked[connect.idx] = true;
                dfs(nodes[connect.idx]);
                sum -= connect.cost;
                checked[connect.idx] = false;
            }
        }

    }


    static class Node {
        int idx;
        List<Node> connects = new ArrayList<>();
        int cost;

        public Node(int idx) {
            this.idx = idx;
        }

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

 

๊ฒฐ๊ณผ

 

2๏ธโƒฃ ํŠธ๋ฆฌ์˜ ํŠน์ง•์„ ์ด์šฉํ•œ ํ’€์ด

๐Ÿ’ก

์ด ๋ฐฉ๋ฒ•์€ ์ด ๋ฌธ์ œ์™€ ์œ ์‚ฌํ•œ ๋ฌธ์ œ์ธ

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

๋ฅผ ํ’€์–ด๋ณด๊ณ  ๊นจ๋‹ฌ์€ ๋ฐฉ๋ฒ•์ด๋‹ค.

๊ฐ€์žฅ ๊ฑฐ๋ฆฌ๊ฐ€ ๋จผ ๋‘ ๋…ธ๋“œ, node1 ๊ณผ node2 ๊ฐ€ ์žˆ๋‹ค๊ณ  ๊ฐ€์ •ํ–ˆ์„ ๋•Œ,

์ž„์˜์˜ ๋…ธ๋“œ x์—์„œ ์ถœ๋ฐœํ•ด์„œ ์–ป์€ ์ตœ๋Œ€ ๋น„์šฉ์˜ ๊ฒฝ๋กœ์˜ ์ตœ์ข… ๋„์ฐฉ์ ์€ node 1 ํ˜น์€ node 2๋ผ๋Š” ๊ฒƒ์ด๋‹ค.

๊ทธ๋ฆฌ๊ณ  node 1 ์—์„œ ์ถœ๋ฐœํ•œ ์ตœ๋Œ€ ๋น„์šฉ์˜ ๊ฒฝ๋กœ ์ตœ์ข… ๋„์ฐฉ์ ์€ node2๊ฐ€ ๋œ๋‹ค.


์˜ˆ์ œ ๊ทธ๋ฆผ์—์„œ๋„, ํŠน์ • ๋…ธ๋“œ๋ฅผ ์ตœ์ƒ์œ„ ๋…ธ๋“œ๋กœ ๋‘๊ณ  ๊ฒฝ๋กœ๋ฅผ ๊ตฌํ•ด๋ณด๋ฉด ๊ฐ€์žฅ ๊ธด ๊ฒฝ๋กœ์˜ ๋์€ ํ•ญ์ƒ 9 ํ˜น์€ 12์ž„์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค.

์ด๋Ÿฌํ•œ ํŠน์ง•์„ ์ด์šฉํ•ด์„œ, ์ž„์˜์˜ ๋…ธ๋“œ 1๋ฒˆ์—์„œ ์ถœ๋ฐœํ•˜์—ฌ ๊ฐ€์žฅ ํฐ ๋น„์šฉ์˜ ๊ฒฝ๋กœ๋ฅผ ๊ตฌํ•˜๊ณ , ๊ทธ ๊ฒฝ๋กœ ๋ ๋…ธ๋“œ ์ •๋ณด๋ฅผ ์ €์žฅํ•œ ๋‹ค์Œ

๊ฒฝ๋กœ ๋ ๋…ธ๋“œ ์ •๋ณด์—์„œ ๊ฐ€์žฅ ๊ธด ๊ฒฝ๋กœ๋ฅผ ์ฐพ์œผ๋ฉด, ๊ทธ ๊ฒฝ๋กœ๊ฐ€ ํŠธ๋ฆฌ์—์„œ ๊ฐ€์žฅ ํฐ ๋น„์šฉ์˜ ๊ฒฝ๋กœ๊ฐ€ ๋จ์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค.

 

public class Main {
    static int sum = 0;
    static int ans = 0;
    static int maxIdx = 0;
    static boolean[] checked;
    static Node[] nodes;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        checked = new boolean[N + 1];
        nodes = new Node[N + 1];

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

        for (int i = 0; i < N - 1; i++) {
            String[] input = br.readLine().split(" ");
            int u = Integer.parseInt(input[0]);
            int v = Integer.parseInt(input[1]);
            int cost = Integer.parseInt(input[2]);

            Node U = new Node(u, cost);
            Node V = new Node(v, cost);

            nodes[u].connects.add(V);
            nodes[v].connects.add(U);

        }

        dfs(1);
        dfs(maxIdx);

        System.out.println(ans);

    }

    private static void dfs(int i) {
        Node root = nodes[i];
        checked[root.idx] = true;
        dfs(root);
        checked[root.idx] = false;
    }

    private static void dfs(Node node) {
        if (ans < sum) {
            ans = sum;
            maxIdx = node.idx;
        }

        for (Node connect : node.connects) {
            if (!checked[connect.idx]) {
                sum += connect.cost;
                checked[connect.idx] = true;
                dfs(nodes[connect.idx]);
                sum -= connect.cost;
                checked[connect.idx] = false;
            }
        }

    }


    static class Node {
        int idx;
        List<Node> connects = new ArrayList<>();
        int cost;

        public Node(int idx) {
            this.idx = idx;
        }

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

๊ฒฐ๊ณผ

์ด์ „ ๋ฐฉ์‹์€ ๋ชจ๋“  ๋…ธ๋“œ์—์„œ ํƒ์ƒ‰์ด ํ•„์š”ํ–ˆ์ง€๋งŒ, ๋‘๋ฒˆ์งธ ํ’€์ด๋Š” 2๋ฒˆ์˜ ํƒ์ƒ‰๋งŒ ์ˆ˜ํ–‰ํ•˜๋ฉด ๋˜๊ธฐ ๋•Œ๋ฌธ์— ์‹คํ–‰์†๋„๊ฐ€ ๋น„์•ฝ์ ์œผ๋กœ ๊ฐœ์„ ๋จ์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค.

    '๐Ÿ‘จ๐Ÿป‍๐Ÿ’ป PS/๋ฐ”ํ‚น๋…' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
    • [JAVA] ๋ฐฑ์ค€ 2637๋ฒˆ ใ€G2.์žฅ๋‚œ๊ฐ ์กฐ๋ฆฝใ€‘
    • [JAVA] ๋ฐฑ์ค€ 21276๋ฒˆ ใ€G2.๊ณ„๋ณด ๋ณต์›๊ฐ€ ํ˜ธ์„ใ€‘
    • [JAVA] ๋ฐฑ์ค€ 2250๋ฒˆ ใ€G2.ํŠธ๋ฆฌ์˜ ๋†’์ด์™€ ๋„ˆ๋น„ใ€‘
    • [JAVA] ๋ฐฑ์ค€ 20955๋ฒˆ ใ€G4.๋ฏผ์„œ์˜ ์‘๊ธ‰ ์ˆ˜์ˆ ใ€‘
    ์šฐ๊ทœ์ด์ธ์šฐ์œค
    ์šฐ๊ทœ์ด์ธ์šฐ์œค
    ๊ฐœ๋ฐœ์ž ๊ฟˆ๋‚˜๋ฌด

    ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”