[java 백준] 골드 3/ 1167번 트리의 지름

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

1167번: 트리의 지름

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Main {
    public static int n;
    public static int max = 0;
    public static int realNode;
    public static boolean[] visit;
    public static List<Node> list[];
 
    public static class Node {
        int len;
        int node;
 
        public Node(int node, int len) {
            this.len = len;
            this.node = node;
        }
 
    }
 
    public static void DFS(int x, int len) {
 
        if (len > max) {
            max = len;
            realNode = x;
        }
 
        visit[x] = true;
        for (Node nodes : list[x]) {
            if (!visit[nodes.node]) {
                visit[nodes.node] = true;
                DFS(nodes.node, nodes.len + len);
            }
        }
 
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
 
        list = new ArrayList[n + 1];
        int maxLen = 0;
 
        for (int i = 1; i < n + 1; i++) {
            list[i] = new ArrayList<Node>();
        }
 
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            while (true) { 
                int node = sc.nextInt();
                if (node == -1) {
                    break;
                }
                int len = sc.nextInt();
 
                list[num].add(new Node(node, len)); 
 
                list[node].add(new Node(num, len));
 
            }
 
        }
 
        visit = new boolean[n + 1];
        DFS(1, 0);
 
        visit = new boolean[n + 1];
        DFS(realNode, 0);
 
        System.out.println(max);
    }
 
}
 

헛발질 (처음했던 생각)

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
 
public class Main{
    public static int n;
    public static boolean[] visit;
    public static List<Node> list[];
 
    public static class Node {
        int len;
        int node;
 
        public Node(int node, int len) {
            this.len = len;
            this.node = node;
        }
 
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        visit = new boolean[n + 1];
        list = new ArrayList[n + 1];
        int maxLen = 0;
 
        for (int i = 1; i < n + 1; i++) {
            list[i] = new ArrayList<Node>();
        }
 
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            while (true) { // continue를 쓰면 안됐어 --> 그러면 연속해서 여러번 못 받아줌
                int node = sc.nextInt();
                if (node == -1) {
                    break;
                }
                int len = sc.nextInt();
 
                list[num].add(new Node(node, len)); // ArrayList에 배열을 하나 더 넣지 말고, 그냥 객체를 넣어주기 (변수 여러개 담을 수 있도록)
                // 애초에 변수 여러개 담는게 목적이기도 했고
 
                list[node].add(new Node(num, len));
 
            }
 
        }
 
        int ans[] = new int[n + 1];
        Queue<Integer> queue = new LinkedList<Integer>();
 
        for (int i = 1; i < n + 1; i++) {
            queue.add(i);
 
            visit[i] = true;
 
            while (!queue.isEmpty()) {
                int num = queue.poll();
                int checkBool = 0;
                // false개수 세주기
                for (Node nodes : list[num]) {
                    if (!visit[nodes.node]) {
                        checkBool++;
                    }
 
                }
                // 만약에 false 개수가 0이면 바로 종료 시켜줄 것
                if (checkBool == 0) {
                    break;
                } else {
                    for (Node nodes : list[num]) {
                        if (!visit[nodes.node]) {
                            visit[nodes.node] = true;
                            ans[i] += nodes.len;
                            queue.add(nodes.node);
 
                        }
                    }
                }
 
            }
 
            System.out.println(i + "열의 길이는 " + ans[i]);
 
        }
    }
 
}

 

처음엔 BFS로 풀려 했다. 해당 행의 원소중 더이상 visit[i]==false인 원소가 없으면 break를 걸어주려 했는데, 그게 맘처럼 쉽지 않았고, (저렇게 개수까지 세줬는데 왜 안되는 것일까..ㅜㅜ) 탐색하다 도중에 중단하는 것은 BFS나 DFS의 접근방법과 맞지 않다 생각했다. 그래서 새로운 풀이를 찾아보기 시작했다.
그리고 무엇보다 for문을 돌려줘서 1부터 시작 ~ 5부터 시작 중 어떤게 가장 길이가 길지 생각해주려했는데 이것도 시간초과가 난다는 글을 봤다.

그래서 해결방법은? 

DFS를 쓰기로 했다. (BFS보다 DFS 풀이가 많아섴ㅋㅋ)
해결방법은 임의의 정점을 정하고 거기서 DFS로 가장 먼 노드를 구한다.(가장 멀수록 지름의 길이도 길어짐)
그리고 DFS를 한번 더 해줘서 가장 먼 노드부터 임의의 정점까지 길이를 구한다.

 

중요 코드 설명

특히 DFS에서 x에 4가 들어올때 경우의 수가 두가지로 나뉘는게 중요하다.(이 앞까진 그냥 코드대로 생각하면 된다)

 

x가 4일때 DFS(4,5)가 호출될것이다. 그리고 list[4]배열의 원소 중 visit[nodes.node]가 false인 경우는 nodes.node가 2와 5일때이다.

2를 먼저 입력받아왔기 때문에 컴파일러는 우선 visit[2]=true;를 하고 DFS(2,5(원래누적된길이) +4(노드 2를 지났을때 추가되는 길이)) 를 호출하고 max=9 realNode는 2가 될거다. 근데 list[2]에는 visitit[nodes.node]가 false인 애가 없다. 이미 다 한번씩 방문했다.

 

그래서 위로 올라가서 list[4] 배열 원소의 nodes.node중 그 값이 5일때로 간다. visit[5]는 당연히 true이고

DFS(5,5(원래 누적된 길이 x값이 4일때의 길이로 생각해줘도 됨) + 6(노드 5를 지날때 추가되는 길이)) 를 호출해준다.

이때 조건문 if(len>max)를 만나는데 이때의 len은 11이고 max는 9이다. (아까 x가 2일때 max=9로 설정됨) 그러니까 if문 안으로 들어가서 max=11 realNode는 5로 변경된다. list[5]의 원소의 nodes.node 중에 false인애는 없기에 x가 5일때 max와 realNode가 fix되게 된다. 

이 문제에서 배워갈 것 

1) 배열의 원소 안에 두개 이상의 변수를 저장해야하는 경우 -> 그 안에 배열을 또 만들지 말고, 클래스를 만들어줘서 생성자에 변수를 포함시켜주고 객체를 생성할 것

 

2) 입력받아줄 때 continue가 아니라 while문 + break 로 써야함 (그래야 한 노드에 두개 이상의 노드가 연결되어있을 때 값을 저장해줄 수 있음) -> 이건 오랫동안 문제를 안풀어서 감이 떨어진거라 생각함

 

3) 시간초과를 방지하기 위해 전체를 다 돌려보는게 아니라 가장 긴 지름을 가질 수 있는 유력한 노드 하나를 지정한 후 걔를 중심으로 문제를 풀어낼 것 

 

참고자료

 

https://moonsbeen.tistory.com/101

[백준]1167: 트리의 지름 - JAVA

가장 긴 트리의 지름을 구하는 것 같은 경로의 특정을 지정해주는 문제는 DFS가 더 적합하다는 것을 이 글을 보고 확신할 수 있게 되었다.
https://devuna.tistory.com/32

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)

경로의 특징을 저장해둬야 하는 문제에는 BFS보단 DFS가 어울린다는 거였다.
이 글의 한부분을 발췌하면
예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)