[백준] (1167) 트리의 지름

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

사용 언어 : JAVA

문제 설명

---

 

---

짧은 하소연 🥲

이 문제도 정말..^^ 어이없는 실수로 근 이틀을 고민했었다.

정석대로 짠 것 같은데 왜 안되지? 다른 사람의 소스코드를 참고해봐도 내 코드랑 다른 게 없었다. 심지어 그 사람은 Scanner 쓰고 통과했는데 난 BufferedReader 썼는데도 안됐다ㅋㅋㅋ

그래서 뭐가 다른거지... 하고 코드 한줄씩 바꾸면서 계속 돌려봄 ㅋㅋㅋ 내가 이 문제 골2에서 골1로 올려버리겠단 마음으로 함.

근데 나중에서야 내 문제를 알게 되었고 내가 멍청이라는 걸 깨달았다.

 

내 생각

초기 생각

플로이드 와샬

처음에는 든 생각은 플로이드 와샬(Floyd Warshall)이었다. 골드 2라 안될 것 같았지만 짜는데 시간도 별로 안걸리니까 한 번 해보자, 하고 제출했다.

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

        int N = Integer.parseInt(br.readLine());
        int[][] dist = new int[N][N];

        for(int i=0; i<N; i++)
            Arrays.fill(dist[i], 10001);

        StringTokenizer st;
        int v1, v2, distance;
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            v1 = Integer.parseInt(st.nextToken()) - 1;
            while(st.countTokens()>2){
                v2 = Integer.parseInt(st.nextToken()) - 1;
                distance = Integer.parseInt(st.nextToken());
                dist[v1][v2] = dist[v2][v1] = distance;
            }
        }

        for(int bridge=0; bridge<N; bridge++){
            for(v1=0; v1<N; v1++){
                for(v2=0; v2<v1; v2++){
                    if(v1==bridge|| v2==bridge) continue;
                    if(dist[v1][v2] > dist[v1][bridge] + dist[bridge][v2]){
                        dist[v1][v2] = dist[v2][v1] = dist[v1][bridge] + dist[bridge][v2];
                    }
                }
            }
        }

        int max = Integer.MIN_VALUE;
        for(v1=0; v1<N; v1++){
            for(v2=0; v2<v1; v2++){
                max = Math.max(max, dist[v1][v2]);
            }
        }

        System.out.println(max);
    }
}

결과는 메모리 부족! 정점 최대 개수가 100,000개이기 때문에, 100,000*100,000 = 10,000,000,000(==10,000M). 여기에 4byte를 곱하면 당연히 256M가 넘는다..

BFS

첫번째 시도의 실패로, 1. 메모리를 더 적게 사용하기 위해 인접 배열 대신 인접 리스트를 사용했고, 2. 3중 for문도 줄여보기로 했다. 그래서 BFS를 생각했는데, 각 정점에서부터 bfs를 돌려서 int[] max에 가장 먼 거리를 갱신하는 거였다.

public class Main {
    static int N;
    static int[] max;
    static ArrayList<ArrayList<int[]>> list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        max = new int[N];
        list = new ArrayList<>(N);
        for (int i = 0; i < N; i++) {
            list.add(new ArrayList<>());
        }

        // list 구성
        StringTokenizer st;
        int v1, v2, dist;
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            v1 = Integer.parseInt(st.nextToken()) - 1;
            while(st.countTokens()>2){
                v2 = Integer.parseInt(st.nextToken()) - 1;
                dist = Integer.parseInt(st.nextToken());
                list.get(v1).add(new int[]{v2, dist});
            }
        }

        // bfs
        int max = bfs();
        System.out.println(max);
    }

    static boolean[] visited;
    private static int bfs() {
        int ret = -1;
        for(int i=0; i<N; i++){
            visited = new boolean[N];
            max[i] = Math.max(max[i], bfs(i));
            ret = Math.max(ret, max[i]);
        }
        return ret;
    }

    private static int bfs(int i) {
        Queue<int[]> queue = new LinkedList<>();
        // vertex, dist_sum
        queue.add(new int[]{i, 0});
        visited[i] = true;

        int ret = 0;
        int[] cur;

        while(!queue.isEmpty()) {
            cur = queue.poll();
            ret = Math.max(ret, cur[1]);
            // cur[0]에서 갈 수 있는 정점들
            for (int[] vertex : list.get(cur[0])) {
                if (visited[vertex[0]] || max[vertex[0]]!=0) continue;
                visited[vertex[0]] = true;
                // 이동할 수 있는 정점 번호, 이동했을 때 총 거리 queue에 삽입
                queue.add(new int[]{vertex[0], cur[1]+vertex[1]});
            }
        }
        return ret;
    }
}

결과는 시간초과! O(N^2)이라 당연했다.

그래서 어쩔 수 없이 구글 찬스를 썼고, 새로운 그래프 이론을 배웠다.

 

DFS 두 번으로 트리의 최대 지름 구하기

트리의 최대 지름을 DFS 두 번만으로 구할 수 있다. 그 어떤 그래프이든, 노드가 몇개든 상관 없이 구할 수 있다.

1. 임의의 노드를 중심으로 가장 거리가 먼 노드를 찾는다.
2. 그 노드에서 다시 DFS를 돌려 가장 긴 트리의 지름을 구한다.

그렇게 나온 코드가 접은 글과 같았다.

public class Main {
    static ArrayList<int[]>[] list;
    static boolean[] visited;
    static int N, MAX=0, far;

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

        N = Integer.parseInt(br.readLine());
        list = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            list[i] = new ArrayList<>();
        }

        // list 구성
        StringTokenizer st;
        int v1, v2, dist;
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            v1 = Integer.parseInt(st.nextToken()) - 1;
            while(st.countTokens()>2){
                v2 = Integer.parseInt(st.nextToken()) - 1;
                dist = Integer.parseInt(st.nextToken());
                list[v1].add(new int[]{v2, dist});
            }
        }

        visited = new boolean[N];
        dfs(0, 0);

        visited = new boolean[N];
        dfs(far, 0);

        System.out.println(MAX);
    }

    private static void dfs(int n, int dist) {
        if(MAX < dist){
            MAX = dist;
            far = n;
        }
        visited[n] = true;
        for(int[] node: list[n]){
            if(visited[node[0]]) continue;
            dfs(node[0], dist + node[1]);
        }
    }

}

근데 이게 74%에서 계속 통과가 안됐다. 뭐가 문제지? 했는데 알고보니 입력을 잘못 받은 거였다(...)

// list 구성
StringTokenizer st;
int v1, v2, dist;
for(int i=0; i<N; i++){
    st = new StringTokenizer(br.readLine());
    v1 = Integer.parseInt(st.nextToken()) - 1;
    
    // 문제가 된 부분
    while(st.countTokens()>2){
        v2 = Integer.parseInt(st.nextToken()) - 1;
        dist = Integer.parseInt(st.nextToken());
        list[v1].add(new int[]{v2, dist});
    }
}

사실 어디가 문제인지 정확히는 모르겠는데, 아마 어쩌다 StringTokenizer의 남은 토큰이 -1 하나가 되어서 dist 부분의 st.nextToken()이 무한 대기 상태에 걸린게 아닐까 하는 추측...?? 더 알아봐야 겠다.

여하튼 입력 부분의 오류까지 제대로 수정한 결과가 아래와 같다.

 

최종 코드

public class Main_BJ_1167_트리의_지름 {
    static ArrayList<int[]>[] list;
    static boolean[] visited;
    static int N, MAX=0, far;

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

        N = Integer.parseInt(br.readLine());
        list = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            list[i] = new ArrayList<>();
        }

        // list 구성
        StringTokenizer st;
        int v1, v2, dist;
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            v1 = Integer.parseInt(st.nextToken()) - 1;
            while(true){
                v2 = Integer.parseInt(st.nextToken()) - 1;
                if(v2 == -2) break;
                dist = Integer.parseInt(st.nextToken());
                list[v1].add(new int[]{v2, dist});
            }
        }

        visited = new boolean[N];
        dfs(0, 0);

        visited = new boolean[N];
        dfs(far, 0);

        System.out.println(MAX);
    }

    private static void dfs(int n, int dist) {
        if(MAX < dist){
            MAX = dist;
            far = n;
        }
        visited[n] = true;
        for(int[] node: list[n]){
            if(visited[node[0]]) continue;
            dfs(node[0], dist + node[1]);
        }
    }

}

---

느낀점

• 입력 부분 오류는 진짜 생각도 못했는데, 좀 더 꼼꼼히 짜야겠다.