백준 1967 트리의 지름

대혁이가 함께 풀어보자고 해서 '트리의 지름' 이라는 문제를 풀어보았다. 대혁이가 dfs 틀을 다 만들어주어서 고치기만 하면 되었기 때문에 다행히 고칠 수 있었다. 불행히 고친 내 코드는 계속 메모리 초과를 뱉어 내었고, dfs 에서 전역변수를 이용해 MAX값을 설정하면 위함하다는 것을 알 수 있었다.

 ChatGPT가 하도 난리여서 설마 이러한 메모리 초과 이슈도 고쳐낼 수 있는지 궁금해져 지금 메모리 초과를 발생시키는 코드를 주고 최적화를 부탁하였다. ChatGPT 가 그 결과를 리턴해 주었고, 그걸로 제출을 하니 믿기지 않게도 통과 했다.

 

이전의 코드와 고쳐준 코드를 비교해 보려 한다.

 

public class Boj_1967 {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static List<List<Edge>> adjList;
    static boolean[] isUsed;
    static int max = Integer.MIN_VALUE;
    static int dia = 0;

    static class Edge {
        int to;
        int weight;

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

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

        //가중치를 둔 인접 리스트
        adjList = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            adjList.add(new ArrayList<>());
        }
        for (int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int G = Integer.parseInt(st.nextToken());

            adjList.get(v1).add(new Edge(v2, G));
            adjList.get(v2).add(new Edge(v1, G));
        }
        isUsed = new boolean[N + 1];
        for (int i = 1; i <= N; i++){
            Arrays.fill(isUsed, false);
            dia = 0;
            dfs(i);
        }
        System.out.println(max);
    }

    private static void dfs(int x) {

        isUsed[x] = true;
        for (Edge e : adjList.get(x)) {
            int to = e.to;
            int weight = e.weight;
            if (!isUsed[to]) { // 연결되어있으면

                dia += weight;
                max = Math.max(max, dia);
                dfs(to);
                dia -= weight;
            }
        }
    }

이게 내 기존 코드이고, 

 

static class Edge {
        int to;
        int weight;

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        if (N == 1)
        {
            System.out.println(0);
            return ;
        }
        //가중치를 둔 인접 리스트
        adjList = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            adjList.add(new ArrayList<>());
        }
        for (int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int G = Integer.parseInt(st.nextToken());

            adjList.get(v1).add(new Edge(v2, G));
            adjList.get(v2).add(new Edge(v1, G));
        }
        isUsed = new boolean[N + 1];
        for (int i = 1; i <= N; i++){
            Arrays.fill(isUsed, false);
            dia = 0;
            dfs(i);
        }
        System.out.println(max);
    }

    private static void dfs(int x) {

        isUsed[x] = true;
        for (Edge e : adjList.get(x)) {
            int to = e.to;
            int weight = e.weight;
            if (!isUsed[to]) { // 연결되어있으면

                dia += weight;
                max = Math.max(max, dia);
                dfs(to);
                dia -= weight;
            }
        }
    }

이것이  chatgpt의 수정본이다.

지금 내 코드는 인접 행렬을 통해 그래프를 표현하고 있는데, 챗지피티는 그 인접행렬을 인접 리스트로 변경하였다.

다음은 챗지피티의 이에 대한 설명이다. 

"인접 리스트를 인접 행렬 대신 사용하는 것은 메모리를 절약하는데, 사용되지 않는 간선들을 저장하지 않기 때문입니다."

내가 작성한 코드에는 서로 간선이 없는 접점들에 해당해서도 다 배열 공간이 생성되었는데, 이를 하지 않는다는 의미이다.

 

챗지피티가 내가 못한걸 너무 쉽게 해결하는걸 보고 좀 많이 무섭다. 코테 준비하고 개발공부를 하고 이런 행동들이 곧 의미없어질 수 도 있겠다는 생각이든다..!

얘네가 못하는걸 공부하고 준비해야 살아남을 수 있을거다. 

인공지능한테 맞아가면서 일하게 될까봐 너무 무서어..