[코드트리] 2 - 트리 공부 및 1일 1문제 습관 형성하기

2주차 전체 후기

 

 이번 주차의 학습 계획의 목표를 완료했고 총 5일 걸렸다. 이번 주차의 경우 트리 순회 + 복원이나 트리의 성질 + 사이클 정도는 원래 알고 있었지만 Rerooting Technique나 내부 연산의 O(1) 최적화 처리에 대한 부분을 매끄럽게 하지 못했었는데 그걸 다듬는 연습이 되었다.

 

 문제 풀고, 복기하고 정리하고 다 하는데도 일반적으로 하위 챕터당 1.5~2일 정도 나오는 거 같다. 전체적인 문제 방향성이 좋은 게 유클리드 원론 읽듯이 a 개념 + b 개념을 학습시켜서 그걸 바탕으로 하면 이런게 나오고 그걸 약간 꼬아서 한번 더 풀게 하지만 그 전 내용이 자동으로 복습되는 구조를 가지고 있다. 완벽히 이해하고 학습자 본인이 해당 내용에 대해 계속 생각한다면 정확히 그 방향으로 문제가 출제되는 걸 보아 단계적 학습에 유리한 커리큘럼을 갖고 있다.

 

문제 풀이의 습관화

대부분이 ps때문일 것이다

 

 코드트리는 루틴한 학습을 위한 리마인더용 알림이 카카오톡으로 와서 꾸준하게 학습할 수 있도록 격려 + 일상화에 많은 도움이 되었다. 또한 xp 시스템으로 스스로 공부량을 정해서 오늘 얼마나 더 해야하고 얼마나 기준을 더 넘겨서 학습하고 있는지를 한 눈에 알아보게끔 함으로써 성취감을 느끼게 한다. 그리고 깃허브 연동을 레포지토리뿐만 아니라 디렉토리 단위까지 지원하기 때문에 잔디 관리로 동기부여에 도움이 된다. 이와 별개로 본인은 PS를 시작한 이래로 문제 회고를 작성해 왔었다.

 

문제 회고

 나의 경우엔 모든 문제에 대해 태그를 매기고 AC가 되는 풀이, 제한 안에서 추가 최적화 풀이, 관련 개념 정리 + 템플릿 추출 및 일반화, 문제 패턴 인식, 관련된 CS 지식 등등을 작성한다. 이는 심심풀이로 읽을거리를 제공하며 아무리 많은 문제를 풀어도 당시에 상상도 못한 기상천외한 접근법이 정답이었거나 개인적인 이유가 있어서 기억나는 문제가 아니라면 복기하기가 쉽지 않으므로 해당 블로그에 매일 문제를 풀며 작성한 회고를 읽곤 한다.

 

회고는 사고의 흐름 (어떻게 접근했고, 조건을 어떻게 해석하고, 문제를 재정의하는 모든 전처리 과정) + 풀이 + etc의 구조로 이루어진다. 특히 사고의 흐름은 정확히 시간 순서로 기억해내서 쓰는 방식으로 쓰고 풀이는 구현에서의 주의점이나 잡기술 등이 주를 이룬다. etc의 경우 extra들이다. 이 문제를 이렇게 꼬면 어떻게 될지라던가 주 언어가 Java이기 때문에 Java의 특징에 따른 시간/ 공간 복잡도 상 최적화나 알고 있으면 좋을 언어나 JVM 자체의 지식 등을 기술한다. 

 

 만약 틀린 풀이를 했다면 이 부분에서 어떻게 사고를 전환해야 하는지를 떠올릴 수 있게 해 주고 맞는 풀이를 했다면 해당 발상과 아이디어를 템플릿화 시켜서 비슷한 문제가 나올 때 훨씬 빨리 접근하고 디버깅과 구현에 시간 분배를 해 줄 수 있는 장점이 존재한다. 가끔 사고의 흐름 파트가 없는 회고들이 있는데 보통 정말 well-known 문제인데 정리하지 않으면 예의가 아닌 느낌이라 reminder로 재작성 한 문제들이다.

 

회고의 목적은 단순히 이 문제를 어떻게 풀었지를 외우는 목적보다는 예를 들어 몇 년전에 내가 한 풀이와 지금 다시 똑같은 문제를 마주했을때 하는 해석이 다르고 거기서 추출할 수 있는 가능성과 재미가 있기 때문이다. n년전에 쓴 변수명이나 함수명, 구현 디테일을 보면 더 열심히 하면 또 그만큼 성장해 있겠다는 과거 사례가 되기 때문에 동기부여에는 그만한 게 없는 거 같다.

---

상세 학습 계획

불안정한 지식이라고 노란색으로 추천받은 챕터기도 하고 그래프가 땡기고,,

트리를 한번 돌아볼 때가 왔다고 생각해서 해당 챕터를 공부하기로 했다.

아직 완전탐색 챕터에서 DP를 들어가진 않았으니 최적화하는데 DP를 쓰긴 해도 트리 DP나 LCA 파트는 트리와 이진트리 파트를 다 풀고 나서 완전 탐색 챕터에서 DP 유형을 좀 더 공부하고 돌아와서 풀 예정이다.

 

가장 좋은 학습은 더 좋은 코드를 찾는 것이라 생각하는데 공식 에디토리얼도 좋지만 역시 OJ는 해당 문제를 자력으로 풀고 난 뒤, 제출현황 중 내 코드보다 성능이 좋은 풀이가 있으면 참고 후 복기하는 것이 효율이 좋다.

---

문제 - 트리 노드 제거

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-remove-tree-node/description

트리 노드 제거 설명 | 코드트리

public class Main {
    static int N;
    static int[] parent;
    static ArrayList<Integer>[] g;
    static boolean[] isDeleted;

    static void dfs(int ci){
        if(isDeleted[ci])
            return;
        isDeleted[ci] = true;
        for(int n : g[ci]){
            dfs(n);
        }
    }

    static int ans = 0;
    static void findLeaf(int si){
        Queue<Integer> q = new ArrayDeque<>();
        q.add(si);

        while(!q.isEmpty()){
            int ci = q.poll();

            boolean found = false;
            for(int n : g[ci]){
                if(isDeleted[n])
                    continue;
                found = true;
                q.add(n);
            }
            if(!found)
                ans++;
        }
    }

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

        for(int i = 0 ;i<N; i++){
            parent[i] = Integer.parseInt(st.nextToken());
        }

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

        int root = -1;
        for(int i = 0; i<N; i++){
            if(parent[i] == -1)
                root = i;
            else
                g[parent[i]].add(i);
        }

        int d = Integer.parseInt(br.readLine());
        isDeleted = new boolean[N];
        if(d == root){
            System.out.print(0);
            return;
        }
        else{
            dfs(d);
            findLeaf(root);
            System.out.print(ans);
        }
    }
}

문제 정리

노드 하나를 지웠을때 삭제 정보 전파 처리와 루트에서 탐색했을때 리프 노드 갯수를 리턴하는 문제

 

풀이

먼저 입력으로 부모 정보 배열이 들어오므로 트리니까 양방향 입력으로 부모 배열을 보고 입력을 받는다. 

-> List 배열 그래프로 나타냄

여기서 root가 0으로 고정된 게 아니므로 parent 값이 -1이면 해당 idx는 root이고 이때는 g에 입력을 하지 않는다.

 

그리고 dfs로 삭제 위치부터 isDeleted로 체킹을 해 주면서 모든 영향을 받는 자식 노드들을 deleted 체크를 해 준다.

만약 삭제 위치가 root라면 전부 삭제됬으므로 리프노드는 존재하지 못하니 0을 출력하고 리턴한다. 

 

그 외에는

1) dfs로 삭제처리 재귀적으로 실행

2) root부터 자식 노드들을 전부 살펴보며 deleted 아닌게 하나라도 남아있으면 타고 내려가고 만약 살아있는 자식 노드를 하나도 찾지 못했다면 ans ++

---

문제 - 트리 판별

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-tree-identification/description

트리 판별 설명 | 코드트리

public class Main {
    static int N;
    static int[][] input;
    static ArrayList<Integer>[] g;
    static int[] indegree;
    static boolean[] visited;

    // 노드 번호가 띄엄띄엄 들어올수도 있을거같음
    static Set<Integer> nodes = new HashSet<>();

    static boolean dfs(int ci){
        if(visited[ci])
            return false;
        
        visited[ci] = true;

        for(int n : g[ci]){
            if(!dfs(n))
                return false;
        }

        return true;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        input = new int[N][2];
        int max = -1;
        for(int i = 0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            max = Math.max(max, Math.max(u,v));
            input[i][0] = u;
            input[i][1] = v;
        }
        g = new ArrayList[max+1];
        for(int i = 1; i<=max; i++)
            g[i] = new ArrayList<>();

        indegree = new int[max+1];

        for(int i = 0; i<N; i++){
            int u = input[i][0];
            int v = input[i][1];
            g[u].add(v);

            nodes.add(u);
            nodes.add(v);
            
            indegree[v]++;
        }

        // 1,2번 조건 처리
        int cnt = 0;
        int root = -1;
        for(int i : nodes){
            if(cnt == 2){
                System.out.print(0);
                return;
            }

            if(indegree[i] == 0){
                root = i;
                cnt++;
            }
                
            if(indegree[i] > 1){
                System.out.print(0);
                return;
            }
        }

        if(cnt != 1){
            System.out.print(0);
            return;
        }


        visited = new boolean[max+1];
        // 위에서 indegree > 1로 걸러서 여기서 재방문하면 사이클임
        if(!dfs(root)){
            System.out.print(0);
            return;
        }

        for(int n : nodes){
            if(!visited[n]){
                System.out.print(0);
                return;
            }
        }
        System.out.print(1);
    }
}

문제 정리

1) 들어오는 간선이 없는 노드는 한개만 있어야 한다.

2) 들어오는 간선이 2개 이상인 노드가 있어서는 안된다.
3) 루트 노드에서 간선을 사용해서 모든 노드에 도달 가능해야 하며, 이 경로는 유일하다.

위 3 조건을 만족하면 1, 아니면 0을 출력하는 문제

 

풀이

일단 문제만 읽어보면 무방향 그래프라고 착각하기 쉽지만 a b 입력은 a에서 b로 가는 간선이라는 뜻이라고 적혀 있으니 이는 DAG이고 indegree 배열로 들어가는 간선 수를 input을 읽으며 체킹한다. 

그리고 노드가 띄엄띄엄 배열되어있을 수 있으니 HashSet으로 sparse한 노드 분포를 대비해주고

graph 자체는 input에서 max 값을 구한걸 바탕으로 정의해준다. 

진입 차수 배열로 1,2는 간단하게 해결되고 

 

조건 3

1) "유일한 경로"

dfs로 한번 방문했던 노드를 다시 재방문하려고 시도하면 false를 뱉게 하는 함수를 만들어서 

사이클을 검출하고 사이클이 존재하면 트리가 아니므로 0을 출력하게 한다. 

 

2) 모든 노드 방문 가능해야

hashSet으로 sparse한 노드 분포를 감안해서 실제 노드들의 visited만 체킹하고 하나라도 미방문 상태라면 

모든 노드를 방문 가능하지 않은게 되므로 0을 출력한다.

 

이걸 모두 뚫고 내려왔다면 문제에서 정의한 트리의 조건에 부합하므로 1을 출력한다. 끝

---

문제 - 트리 파악

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-identifying-the-tree/description

트리 파악 설명 | 코드트리

public class Main {
    static final StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static int N;
    static ArrayList<Integer>[] g;
    static boolean[] visited;

    // depth 파라미터로 넘겨야 리프노드일때 깊이를 반환하고
    // 그걸 부모의 total까지 영향을 끼치게
    static int dfs(int ci, int depth){
        int total = 0;
        boolean hasNext = false;
        for(int n : g[ci]){
            if(visited[n])
                continue;
            hasNext = true;
            visited[n] = true;
            total += dfs(n, depth+1);
        }
        if(!hasNext){
            return depth;
        }
        return total;
    }

    // 트리니까 레벨 bfs로 해도 될듯
    static int bfs(int si){
        Queue<Integer> q = new ArrayDeque<>();
        q.add(si);
        int depth = 0;
        int total = 0;

        while(!q.isEmpty()){
            //이전 노드의 자식들
            int curSize = q.size();
            for(int i = 0; i<curSize; i++){
                int cur = q.poll();

                int cnt = 0;
                for(int n : g[cur]){
                    if(visited[n])
                        continue;
                
                    visited[n] = true;
                    q.add(n);
                    cnt++;
                }
                if(cnt == 0)
                    total += depth;
            }
            //한 레벨 노드들 처리 끝났으니 depth 증가
            depth++;
        }

        return total;
    }

    static int read() throws Exception {
        st.nextToken();
        return (int) st.nval;
    }

    public static void main(String[] args) throws Exception{
        N= read();
        g = new ArrayList[N+1];
        for(int i = 1; i<=N; i++)
            g[i] = new ArrayList<>();
        
        int M = N-1;
        while(M-->0){
            int u = read();
            int v = read();
            // 무방향이라 입력 양방향으로 넣어야함!!
            g[u].add(v);
            g[v].add(u);
        }

        visited = new boolean[N+1];
        visited[1] = true;
        //int tot = dfs(1,0);
        int tot = bfs(1);
        if(tot % 2 == 1)
            System.out.print(1);
        else
            System.out.print(0);
    }
}

정리

차례가 되면 트리 위에 존재하는 아무 말이나 부모 노드로 옮김

한 노드에는 여러 노드가 동시에 존재할 수 있음

루트 노드에 도착하는 말은 바로 제거됨. 루트 노드 1번 고정

더이상 옮길 말이 없을때 차례가 돌아온 사람이 짐.

-> 이러한 룰의 게임이 있을때 트리의 연결 정보와 노드 수가 입력으로 들어올 때 

첫번째로 시작한 플레이어가 이길지 질지 1,0으로 출력

-> 루트부터 모든 리프노드까지의 거리를 합하고 그걸 2로 나눴을때 나머지값이 1이면 이김.

 

풀이 : 재귀 or 레벨링 BFS

처음에는 dfs로 풀었다. 현재 노드와 현재까지의 깊이를 파라미터로 들고 이동하고 만약 다음 자식노드가 하나도 없는 상태일 때 현재의 깊이를 리턴하고 total에는 dfs 리턴값을 누적해서 total을 리턴하는 재귀적 구조인데 재귀 호출 비용때문에 

레벨링 bfs가 더 빠를 거 같아서 bfs로도 풀어봤다.

 

레벨링 BFS

트리에서 현재 큐에 들어가있는건 이전 노드의 자식 노드들이니까 이걸 한 레벨로 보고 묶어서 처리하는 구조이다.

한 레벨의 크기는 현재 큐의 크기이고 큐 처리가 다 끝나면 depth를 하나 증가시킨다.

내부에서 만약 리프 노드이면 total에 누적시켜주고 큐가 비게 되면 누적된 total을 리턴시킨다.

 

Low-Level 입출력

원래 BufferedReader + InputStreamReader를 썼었는데 BufferedReader를 생성값으로 받는

StreamTokenizer라는게 있었다. 

말하자면 입력 스트림 자체를 토큰화해서 read하는건데 

StreamTokenizer st = new StreamTokenizer(br);
return (int) st.nval;

이런식으로 쓴다. 

nval말고 sval도 있는거 보면 이건 string value인듯 싶다. 
제출현황의 익명의 고수님 감사합니다.

---

문제 - 트리 사촌

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-beard-tree/description

트리 사촌 설명 | 코드트리

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static final StreamTokenizer st = new StreamTokenizer(br);

    static int read() throws IOException{
        st.nextToken();
        return (int) st.nval;
    }

    static int N, K;
    static ArrayList[] g;
    static int[] pos;
    // 근데 N이 1000이고 수치는 1_000_000이라 sparse함
    static Map<Integer, Integer> parent = new HashMap<>();

    public static void main(String[] args) throws Exception{
        N = read();
        K = read();
        int max = 0;
        pos = new int[N];
        for(int i = 0; i<N; i++){
            pos[i] = read();
            max = Math.max(max, pos[i]);
        }

        // K가 루트노드면 당연히 0일거임
        if(pos[0] == K){
            System.out.print(0);
            return;
        }

        for(int n : pos){
            parent.put(n, -1);
        }
        // 부모 인덱스를 따로 관리하기
        // 처음엔 값으로 둿는데 이게 마지막꺼만 업데이트돼서 앞에껄 기억못함
        int p = 0;
        for(int i =1 ; i<N;i++){
            parent.put(pos[i], pos[p]);
            if(i < N-1 && pos[i+1] != pos[i] + 1){
                p++;
            }
        }

        int ans = 0;
        for(int n : pos){
            // -1 인덱스 접근 방지
            // 객체로 받아서 nullPointException 방지
            Integer pn = parent.get(n);
            Integer pk = parent.get(K);

            if(pn == -1 || pk == -1)
                continue;

            Integer ppn = parent.get(pn);
            Integer ppk = parent.get(pk);

            if(ppn == null || ppk == null)
                continue;
            // 두 노드의 부모가 달라야 함 && 
            // 두 노드의 부모의 부모가 같음 (형제)
            if(!pn.equals(pk) && ppn.equals(ppk))
                ans++;
        }
        System.out.print(ans);
    }
}

사고의 흐름

일단 딱 보고 parent 배열을 저 입력 배열로 어떻게 직접 복원하거나 그래프를 생성해서 뭔가 해야겠다는 생각을 했다.

근데 그래프를 생성하면 또 dfs로 타고내려가고 어쩌고 해야하고 재귀적으로 parent를 복원하자니 함수 호출 비용이 걸린다..

그리고 문제에서 등차수열로 같은 레벨 노드들을 이룬다고 했으니 뭔가 현재 부모 배열의 index를 추적해야할 거 같았다.

풀이

1) 부모 배열 복원

일단 배열이라고 쓰긴 했지만 내 접근에서는 문제의 노드 수는 최대 1000개지만 수치는 1~백만까지 분포되어있으므로 sparse 그래프라 생각해서 HashMap으로 parent를 구성했다. 

-> 정답 풀이 보니까 그냥 인덱스로 서로 엮여줬던데 그게 더 나았을 거 같다.

 

O(N)으로 입력 배열 따라가면서 일단 현재 추적하는 부모값을 현재 값의 부모로 넣는다.

그리고 현재 값의 인덱스가 N-1보다 작고 그다음거랑 차이가 1이 아니라면 부모 인덱스를 하나 증가시켜준다. 

그러면 다음 채워야할 부모로 자동으로 옮겨가게 된다. 

 

2) 정답 세기

HashMap으로 받았고 문제 조건상 두번 get을 타고 들어가서 nullPointer가 발생할 수 있고 동시에 invalid한 값인 -1이 나온다.

이를 동시에 잡기 위해서는 공간을 좀 더 먹지만 Integer로 받아서 .equals로 비교연산하고 null과 -1을 처리한다.

---

문제 - 트리 간선의 길이(트리의 지름)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-length-of-tree-trunk/description

트리 간선의 길이 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N;
    static ArrayList<int[]>[] g;
    static boolean[] visited;

    static int maxDist = -1;
    static int farNode = -1;

    // si로부터 시작하는 최장경로에서의 끝점 반환
    static void dfs(int ci, int dist){
        if(dist > maxDist){
            maxDist = dist;
            farNode = ci;
        }

        for(int[] n : g[ci]){
            int ni= n[0];
            int nd = n[1];
            if(visited[ni])
                continue;
            visited[ni] = true;
            dfs(ni, dist + nd);
        }
    }

    public static void main(String[] args) throws IOException{
        N = read();
        g = new ArrayList[N+1];
        for(int n = 1; n<=N; n++){
            g[n] = new ArrayList<>();
        }

        int M = N-1;
        int root = 10001;
        while(M-->0){
            int u = read();
            root = Math.min(root, u);
            int v = read();
            int w = read();
            g[u].add(new int[]{v,w});
            g[v].add(new int[]{u,w});
        }

        visited = new boolean[10001];
        visited[root] = true;
        dfs(root, 0);

        visited = new boolean[10001];
        visited[farNode] = true;
        dfs(farNode, 0);

        System.out.print(maxDist);
    }
}

사고의 흐름 및 풀이

그냥 트리의 지름을 구하라는 문제이다.

근데 트리는 두 점간의 경로가 유일한 일종의 그래프이고 이 성질을 활용하면 한 점에서의 최장 경로를 하나 구하고 그때의 끝점을 다음 dfs의 시작점으로 삼고 또 dfs로 최장경로를 구하게 되면 그게 이 트리에서 가능한 최장 경로의 값이 된다.

너무나도 Well-Known이지만 저번에 같은 문제에서는 다르게 풀어놔서 정리했다.

DP식 풀이

public class Main {
    static int N;
    static ArrayList<int[]>[] g;
    static boolean[] visited;
    static int ans = -1;

    static int dfs(int ci){
        int curMax = 0;
        int curSecondMax = 0;

        for(int[] n : g[ci]){
            int ni = n[0];
            int nw = n[1];
            
            if(visited[ni])
                continue;
            visited[ni] = true;
            
            int total = dfs(ni) + nw;
            if(total > curMax){
                curSecondMax = curMax;
                curMax = total;
            }
            else if(total > curSecondMax){
                curSecondMax = total;
            }
        }
        ans = Math.max(ans, curMax + curSecondMax);
        return curMax;
    }


    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int M = N-1;
        g = new ArrayList[N+1];
        for(int i= 1; i<=N; i++){
            g[i] = new ArrayList<>();
        }

        while(M-->0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            g[u].add(new int[]{v,w});
            g[v].add(new int[]{u,w});
        }

        visited = new boolean[N+1];
        visited[1] = true;
        dfs(1);
        System.out.print(ans);
    }
}

사고의 흐름

문제 자체는 더 앞에 있는 트리의 지름 문제지만 결국 같은 문제라 문제 링크는 생략한다.

트리는 경로가 유일하고 한 정점에서 최대 경로 + 2번째 최대 경로의 max 값이면 해당 트리에서 취할 수 있는 최대 값이니까
이걸 최대화하면 트리의 지름이 구해질 것이다.

-> 트리 DP 느낌으로 접근

 

DFS

최대경로는 자식으로 계속 타고 내려가서 -> dfs
dfs(자식) + 현재 weight = total로 갱신하고
total이 현재 최대경로보다 크면 1번 = total, 2번 = 1번
total이 현재 2번째 최대경로보다 크면 2번 = total

 

dfs 2번 풀이는 해당 문제에 최적화된 풀이이고 dp식 풀이는 여러가지 조건을 꼬아서 올리게 되면 조금 확장하면 풀 수 있는 구조라서 확장성이 좋다고 생각되어 정리했다.

---

문제 - 트리 최적의 노드

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-tree-optimal-node/description

트리 최적의 노드 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N;
    static ArrayList<Integer>[] g;
    static boolean[] visited;
    
    static int maxDist = 0;
    static int far = -1;

    static void dfs(int ci, int dist){
        if(dist > maxDist){
            maxDist = dist;
            far = ci;
        }

        for(int n : g[ci]){
            if(visited[n])
                continue;
            visited[n] = true;
            dfs(n, dist+1);
        }
    }

    public static void main(String[] args) throws IOException{
        N = read();
        g = new ArrayList[N+1];
        for(int i = 1; i<=N; i++){
            g[i] = new ArrayList<>();
        }

        int M = N-1;
        while(M-->0){
            int u = read();
            int v = read();
            g[u].add(v);
            g[v].add(u);
        }

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

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

        int ans = (maxDist % 2 != 0 ? maxDist/2+1 : maxDist/2);
        System.out.print(ans);
    }
}

사고의 흐름 및 풀이

다른 노드와의 거리의 최댓값이 최소가 된다..? 이걸 어떻게 처리해야하는지 문제 해석이 어려웠던 문제다.

1-2-3-4-5 라는 일자형 트리가 있다고 치자.

각자 다른 노드와의 거리의 최댓값을 구하면 다음과 같다.

1 -> 4, 2 -> 3, 3-> 2, 4->3, 5->4

그러면 이중 다른 노드와의 거리의 최댓값이 최소가 되는건 3번 노드이다. 

-> 즉, 트리의 중심을 찾는 문제

 

다만 노드 갯수가 짝수라면 중심은 2개가 있을 것이고 홀수면 중심이 1개일 것이다. 

다행히 간선의 길이는 1이고 그냥 트리 지름 구해서 /2하고 2로 나눠 떨어지지 않으면 +1을 해 주면 된다.

트리의 중심을 어디다가 활용할지 아직은 감이 안 오긴 한다.

---

문제 - 간선 순회

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-touring-the-line/description

간선 순회 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N, D;
    static boolean[] visited;
    // 간선갯수계산용
    // static ArrayList<Integer>[] g1;
    //거리계산용
    static ArrayList<int[]>[] g;
    static int far = -1;

    // 간선은 최대한 많이, 
    // 날짜수는 최소한으로 해야하니까 거리는 최단거리로 
    static int minDist = Integer.MAX_VALUE;
    static int maxDepth = -1;

    static void dfs(int ci, int depth, int dist){
        if(depth > maxDepth
            || depth == maxDepth && dist < minDist){
            maxDepth = depth;
            minDist = dist;
            far = ci;
        }

        for(int[] n : g[ci]){
            if(visited[n[0]])
                continue;
            visited[n[0]] = true;
            dfs(n[0], depth+1, dist+n[1]);
        }
    }

    public static void main(String[] args) throws IOException{
        N = read();
        D = read();
        g = new ArrayList[N+1];

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

        int M = N-1;
        while(M-->0){
            int u = read();
            int v = read();
            int w = read();
            g[u].add(new int[]{v,w});
            g[v].add(new int[]{u,w});
        }

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

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

        int ans = (minDist % D == 0) ? (minDist / D) : (minDist / D)+1;
        System.out.print(ans);
    }
}

사고의 흐름

이거 좀 많은 생각을 하게 만드는 재미있던 문제였다. 일단 최대한 많은 간선 수를 지나가면서 하루에 D만큼 이동할 수 있을 때 걸리는 이동 일 수를 최소화하는 문제였다. 그래서 dfs 2번하고 dfs 경로계산 이렇게 3번??

처음에는 그래프를 두 개 만들어서 하나는 간선 비용을 1로 잡고 최대 간선 갯수로 경로를 하나 구하고 다른 그래프는 원래 weigth까지 입력받는 그래프를 만들어서 처음 최대 간선 경로의 양 끝점을 끝점으로 갖는 경로의 길이를 구해서 D로 올림 나눗셈을 해줄 생각이었다. 

하지만 좀 생각해보니까 반례가 있었다. 

-> weight가 1일 때 최대 간선 갯수를 가지는 경로는 유일하지 않았다.

 

풀이

그래서 dfs 3번 돌리던 원래 풀이를 다 갈아엎고 

조건이 2가지니까 파라미터를 하나 더 추가해서 return 할때 조건을 추가로 달면 될 것 같았다.

최대 간선 갯수가 상위 조건이니까 그걸 먼저 걸고 그게 같다면 걸리는 일자를 최소로 해야 한다는 조건은 다시 해석하면

-> 경로의 길이가 최소화되어야 한다는 것이다.

 

dfs 파라미터를 현재 노드 번호, 현재 depth, 현재 dist로 줘서

dfs 레벨 하나 넘어갈때마다 depth +1, dist + cost로 넘겨주고 그때의 minDist를 갱신하는 방식으로 짯다.

그렇게 아무 노드에서 시작해서 minDist 한번, 끝점 구해서 한번 하면 최대 간선 경로이면서 동시에 실제 거리 합이 최소인 경로중 하나가 구해지게 되고 해당 문제에서는 실제 경로 추적이 아니라 값만 보므로 minDist로 연산하면 된다. 

 

IF.. 경로추적

일반 그래프고 경로 추적이 있었다면..?

조건은 똑같이 보고 단순 방문 배열이 아니라 현재 정점까지의 최적 상태 (depth, dist)를 같이 보면서 parent 배열을 갱신하고 갱신된 parent 배열을 따라가면서 경로를 출력하면 될 것 같다. (dfs)

대신 visited는 그대로 못 쓰고 -> 이건 트리라서 가능한거고

bestDepth[ 노드 수 ] 랑 bestDist [ 노드 수 ] 같은 형태로 relaxation이 들어가야 할 것 같다.

---

문제 - 트리의 2번째 지름 (다시 보기)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-diameter-of-tree-3/description

트리의 지름 3 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N;
    static ArrayList<int[]>[] g;
    
    static int p1;
    static int p2;
    static long maxDist = -1;
    
    static void dfs(int ci, long dist, int parent, boolean isFirst){
        if(dist > maxDist){
            maxDist = dist;
            if(isFirst)
                p1 = ci;
            else
                p2 = ci;
        }

        for(int[] n : g[ci]){
            if(n[0] == parent)
                continue;
            dfs(n[0], dist+n[1], ci, isFirst);
        }
    }

    // 트리의 각 끝점 잡고 모든 정점에 대해서 경로 구하기
    // no는 피해야할 다른 끝점임
    static long bfs(int si, int no){
        long[] dist = new long[N+1];
        Arrays.fill(dist, -1);
        boolean[] visited = new boolean[N+1];
        Queue<Integer> q = new ArrayDeque<>();
        q.add(si);
        visited[si] = true;
        dist[si] = 0;

        while(!q.isEmpty()){
            int ci = q.poll();
            for(int[] n : g[ci]){
                if(n[0] == no)
                    continue;
                if(visited[n[0]])
                    continue;
                visited[n[0]] = true;
                dist[n[0]] = dist[ci] + n[1];
                q.add(n[0]);
            }
        }

        long rst = 0;
        for(long d : dist){
            rst = Math.max(rst, d);
        }
        return rst;
    }

    public static void main(String[] args) throws IOException{
        N = read();
        g = new ArrayList[N+1];
        for(int i = 1; i<=N; i++)
            g[i] = new ArrayList<>();

        int M = N-1;
        while(M-->0){
            int u = read();
            int v = read();
            int w = read();

            g[u].add(new int[]{v,w});
            g[v].add(new int[]{u,w});
        }        

        dfs(1, 0, -1, true);

        maxDist = -1;
        dfs(p1, 0, -1, false);

        long d1 = bfs(p1, p2);
        long d2 = bfs(p2, p1);
        System.out.print(Math.max(d1,d2));
    }
}

사고의 흐름 및 발상 찾기

굉장히 교육적인 문제였다. 처음에는 트리 DP로 접근해서 자식들간의 top3까지 경로 합을 뽑고 a>=b, b>=c 라 한다면 a+b, a+c, b+c 3개중에 2번째로 긴걸 전역 변수에다가 최대값으로 갱신하고 dfs 자체는 top1 만 리턴하게끔 했는데 후보 경로가 턱없이 부족해서 계속 WA가 나왔다. 

 

그래서 갈아엎고 뭔가 트리의 지름을 어떻게 조작을 하고 트리는 경로가 유일하니까 뭐 이걸 적용하면 될거라고 생각했다. 

아까 내 처음 풀이에서 반례가 후보가 부족하다는 것이엿는데 거기서부터 출발해보면,

트리의 지름을 구성하는 양 끝점중 하나를 시작점으로 잡고 다른 모든 정점에 대한 경로는 유일하다. 

-> BFS로 구하면 될거 같고

그러면 지름의 한 끝점에서 출발하는 모든 경로는 트리의 모든 가능한 경로 중 가장 긴 후보들을 포함하는 것이 된다. 

-> 그러니까 트리의 지름에 포함되는 다른 점을 빼고 제일 긴걸 뽑아주면 2등 후보로 적합해 보였다.

풀이

일단 DFS 2번 돌려서 트리의 지름을 구성하는 양 끝점을 a,b라 하고 a,b를 구한다. 

이번에는 visited 배열 안 쓰고 어차피 경로는 유일하고 그말인즉슨 parent로 visited 처리를 할 수 있다는 것이다. 

그래서 파라미터로 parent를 넘겨주고 parent == next면 못 가게 막았다. 

-> 입력 받을때는 트리라서 양방향 그래프로 입력 받았으니까 막아야한다. 

물론 이번에도 maxDist를 갱신하는데 대신 2번째 dfs전에 초기화를 한번 해줬다.

안해줘도 돌긴 하는데 그게 정확할거 같아서 해줌.

 

BFS를 쓴 이유는 처음에는 dijkstra를 쓰려고 했는데 트리라서 쓸 필요가 없을 것 같고 

처음에 방문하지 말아야 하는 노드를 visited 처리하면 위험할 수 있다. 

-> 그 아래 subtree를 방문하지 못할 수 있기 때문에 명시적으로 for문 안에서 조건 처리를 해 줬다.

N이 최대 10만이고 weight가 2만이므로 안전하게 long 배열로 잡고 

dist를 모든 정점에 대해서 갱신하고 다른 끝점은 빠졌으니까 그중 제일 긴 걸 리턴시킨다.

 

마지막에 그렇게 구한 a에서 시작하는 b를 제외한 최장 경로와 b에서 시작하는 a를 제외한 최장경로를 비교해서 

더 큰게 2등 트리의 지름이 된다.

-> 시간 복잡도는 O(4*N) = O(N)

---

문제 - 트리 수정 (rerooting tree DP) (다시 보기)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-modify-tree/description

트리 수정 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N;
    // (int) 노드 번호, (long) weight
    static ArrayList<int[]>[] g;

    static long maxDist = 0;
    // i에서 자식 방향으로 가장 깊은 최대 거리
    static long[] down;
    // 부모 방향에서 내려오는 최대 거리
    static long[] up;
    // i번 노드의 subtree 내부 지름
    static long[] diam;
    // i번 노드의 subtree를 제외한 나머지 트리의 지름
    static long[] outDiam;

    static long ans = 0;

    static void dfs1(int ci, int parent){
        long top1 = 0;
        long top2 = 0;

        diam[ci] = 0;

        for(int[] n : g[ci]){
            if(n[0] == parent)
                continue;
            dfs1(n[0], ci);

            long tot = down[n[0]] + n[1];

            if(tot > top1){
                top2 = top1;
                top1 = tot;
            }
            else if(tot > top2){
                top2 = tot;
            }

            diam[ci] = Math.max(diam[ci], diam[n[0]]);
        }
        down[ci] = top1;
        diam[ci] = Math.max(diam[ci], top1 + top2);
    }

    // rerooting DP
    // 각 u-v 끊었을때 두 서브트리를 다시 연결했을때 가능한 최댓값 갱신
    static void dfs2(int ci, int parent){
        int m = g[ci].size();

        // val[i] = ci에서 i번째 자식으로 내려가는 최대 거리
        long[] val = new long[m];
        int[] nodes = new int[m];
        // prefix, suffix
        long[] prefix = new long[m+1];
        long[] suffix = new long[m+1];

        for(int i = 0; i<m; i++){
            nodes[i] = g[ci].get(i)[0];
            int cw = g[ci].get(i)[1];

            if(nodes[i] == parent)
                val[i] = -1;
            else
                val[i] = down[nodes[i]] + cw;
        }

        // 특정 child 하나를 제외하고 나머지 중 최대 down 값 구하기
        for(int i = 0; i<m; i++)
            prefix[i+1] = Math.max(prefix[i], val[i]);

        for(int i = m-1; i>=0; i--)
            suffix[i] = Math.max(suffix[i+1], val[i]);


        // 각 ni 기준으로 간선 끊기
        for(int i = 0;  i<m; i++){
            int ni = nodes[i];
            int cw = g[ci].get(i)[1];

            if(ni == parent)
                continue;
            
            // ni 제외한 U의 지름 계싼
            long top1 = 0;
            long top2 = 0;
            long maxSib = 0;
            
            // up 방향 arm (root면 0)
            long upArm = up[ci];
            if(upArm > top1){
                top2 = top1;
                top1 = upArm;
            }
            else if(upArm > top2){
                top2 = upArm;
            }

            // 다른 자식 arm + 지름
            for(int j = 0; j<m; j++){
                if(nodes[j] == parent || nodes[j] == ni)
                    continue;
                long otherArm = val[j];
                if(otherArm > top1){
                    top2 = top1;
                    top1 = otherArm;
                }
                else if(otherArm > top2)
                    top2 = otherArm;
                maxSib = Math.max(maxSib, diam[nodes[j]]);
            }

            long withCi = top1 + top2;
            long diamU = Math.max(withCi, Math.max(maxSib, outDiam[ci]));

            // ni의 subtree 지름 
            long diamV = diam[ni];

            // 제거한 간선 ci-ni, cw에 대해 재연결후 가능한 max 지름
            ans = Math.max(ans, diamU + diamV + cw);
            //ans = Math.max(ans, diamV);

            // rerooting 전파
            long bestOther = Math.max(prefix[i], suffix[i+1]);
            long uSide = Math.max(up[ci], bestOther);
            up[ni] = uSide + cw;

            // 다른쪽 트리 지름 전파
            outDiam[ni] = diamU;

            dfs2(ni, ci);

        }
    }

    public static void main(String[] args) throws IOException{
        N = read();
        g = new ArrayList[N];
        for(int i= 0; i<N; i++)
            g[i] = new ArrayList<>();
        int M = N-1;
        while(M-->0){
            int u = read();
            int v = read();
            int w = read();
            int used = 0;
            g[u].add(new int[]{v,w, used});
            g[v].add(new int[]{u,w, used});
        }

        down = new long[N];
        up = new long[N];
        diam = new long[N];
        outDiam = new long[N];

        dfs1(0,-1);
        ans = diam[0];
        dfs2(0,-1);

        System.out.print(ans);
    }
}

사고의 흐름 및 발상

정말 말도 안되게 어려웠다. 백준으로 치면 한 체감 플레 중상위?? 쯤 되는 문제였다.

풀이 발상 + 구현 디버깅 해서 대충 3~4시간 걸린거 같다..

 

처음에는 나이브하게 음 트리는 경로가 유일하니까 트리 지름 구하면서 dist 배열에 각 정점까지의 거리를 일단 저장한다.

a->b로 트리 지름 구했으면 b->a로 역추적하면서 dist 정보를 가지고 트리의 지름에 해당하는 노드들을 구하기로 했다. 

그리고 여기서 자르고 뻗고 하면 트리의 후보가 될 줄 알았다.

-> 당연하게도 다른 부분에서 제거하고 추가했을때 최적 답이 존재하기 때문에 첫번째 WA를 받았다.

 

그러면 당연히 모든 간선을 추가하고 제거하고 그때마다 지름을 계산하는건 느낌상 안될 거 같아서 

트리의 성질을 생각하면 

-> 모든 경로 유일함 -> 간선 하나 끊으면 컴포넌트 2개로 트리가 갈라짐

-> 끊은 간선 기준으로 up (부모방향) 최대거리 + 끊은 간선 가중치 + down (자식방향) 최대거리

면 아무래도 그게 문제 조건상 트리의 지름의 최대값이 되지 않나 싶었다. 

말하자면 DP 느낌으로 모든 서브트리에 대한 최장경로 정보를 저장하고 재사용해서 연산을 줄인다는 발상이었다. 

-> 이렇게 해서 두번째 WA가 났다. 

 

문제에서 필요한 것은 최대 depth가 아니라 컴포넌트 전체의 지름이었기 때문이다. 

간선 u-v를 제거하면 v의 서브트리 + 나머지 트리 로 나뉘게 된다.

따라서 필요한 정보는 1) subtree 내부 지름 2) subtree 바깥 지름 이다.

-> depth(arm) 기준 DP가 아니라 diameter(지름) 기준 DP로 재구성해야 한다.

 

풀이 : 트리 DP + Rerooting DP

1) down [ i ] = i 에서 서브트리 내부 방향으로 내려갈 수 있는 최대 거리

-> u에서 leaf 최대 거리

-> 서브트리 내부에서 가장 긴 arm 역할이고 지름 계산에 활용된다.

down[u] = max(down[child] + edgeWeight)

 

2) diam[ i ] = i 를 루트로 하는 서브트리 내부의 지름

-> 지름의 후보로는 diam [ child ] (내부 지름) , 현재 노드를 통과하는 경로 ( top1 + top2 ) 가 있다. 

diam[u] = max(child diameters, top1 + top2 )

 

3) up [ i ] = i 서브트리 바깥에서 들어오는 최대 depth 

-> 부모 방향으로 확장 가능한 최대 거리

-> 자식 입장에서 보면 자신을 제외한 나머지 트리에 대한 정보가 필요하다.

 

4) outDiam[ i ] = i 서브트리를 제외한 나머지 트리의 지름 

-> 간선 ( parent - i ) 를 제거했을 때 반대편 컴포넌트의 지름을 의미한다.

 

최종 계산

각 간선 제거 시 : 왼쪽 지름 + 현재 간선 weight + 오른쪽 지름 을 연결하면 가능한 최대 지름이 된다.

-> diam [ u ] + outDiam [ u ] + w

-> 지름 endpoint를 새 간선으로 연결 가능하다는 것임 ( 문제 조건에 의해)

-> 트리는 방향성이 없어서 두 컴포넌트의 지름이라고 쓰는게 더 맞을 거 같긴 한데 일단 문제상 제거하는 간선 입장으로 왼쪽 오른쪽으로 표현하고 싶어서 그렇게 썼다.

 

Rerooting DP

1) dfs1에서 아래 방향 서브트리 정보( u 에서 아래로 최대거리, u 서브트리 내부 지름) 만 계산한다. 

2) dfs2에서 부모 입장에서 계산된 정보를 자식에게 전파한다. 

-> 부모 기준 최적 정보를 자식 기준으로 다시 변환해서 재사용하게끔 하는 것이다.

 

up [ v ] 계산

up [ v ] 는 v 서브트리 밖에서 갈 수 있는 최대 depth이다. 

u -> v 로 내려갈 때 v를 제외하면 갈 수 있는 곳은, 

1) up [ u ] = 부모 방향

2) bestOther = 현재 child를 제외한 다른 방향으로 갈 수 있는 최대 arm의 길이

-> 여기서 prefix와 suffix를 사용해서 현재 자식을 제외한 arm 최댓값을 빠르게 구한다. 

-> arm인 이유는 지름은 양팔이고 이건 한 방향으로 뻗는거라 arm이라 했다.

둘 중 더 큰 값을 선택하고 up [ v ] 에 그 값에 현재 가중치 (cw)를 더해서 저장한다.

 

최적화 : prefix 와 suffix

prefix [ i ] = 0 ~ i-1 의 최댓값

suffix [ i ] = i ~ 끝의 최댓값 

이다. 

이걸 활용하면 자식들을 매번 순회하지 않고 O(1)에 

i (나 자신 인덱스)를 제외한 형제 노드 기준 서브트리 최댓값

= max ( prefix [ i ] , suffix [ i + 1 ] ) 를 구할 수 있다.

 

outDiam[ v ] 

: v 서브트리를 제외한 나머지 트리의 지름을 의미한다. 

계산 후보로는 

1) 부모 방향 기존 지름 ( outDiam[ u ] )

2) 형제 노드 서브트리 내부 지름 ( diam [ sibling ] )

3) 현재 u를 통과하는 지름 ( 남아있는 arm 2개 연결 )

-> 이 3개 중 가장 큰 걸 선택해서 outDiam[ v ] 에 저장한다.

 

따라서 문제 조건에 따라 간선을 제거하게 되면

새로 연결 시 최대 지름의 값은 다음과 같다.

v의 서브트리 지름 ( diam[ v ] ) + 반대편 트리 지름 ( outDiam[ v ] ) + 현재 가중치 ( cw )

 

요약하면, 모든 간선 제거 상황을 rerooting DP로 O(N)에 압축 계산 하려고 몸비틀어가며 풀었다. 

dfs 1 : subtree 정보 계산

dfs 2 : 부모 방향(서브 트리 밖) 정보 전파

간선마다 : 제거 결과를 O(1)에 연산

 

공식 해설과 비교

공식 해설은 처음 생각한데로 모든 간선을 제거했을때마다 양쪽 지름을 다시 계산한 것 같다.

모든 간선 정보에 대해서 u,v가 있을때 u에서 시작하는 dfs, 끝점 구해가지고 dfs 해서 diam 1

v에서 시작하는 dfs, 끝점 구해가지고 dfs diam 2 구하고 diam1 + diam2 + curWeight 한거 같은데

이러면 트리를 4번 순회하게 되고 총 시간복잡도는 O(N^2)이다.

---

문제 - 그래프와 트리 

https://www.codetree.ai/ko/trails/complete/curated-cards/test-graphs-and-trees/description

그래프와 트리 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N,M;
    static ArrayList<Integer>[] g;
    static int[] v;
    static int vNum = 0;
    static boolean hasCycle;

    static void dfs(int cur, int parent, int cv){
        v[cur] = cv;

        for(int n : g[cur]){
            if(n == parent)
                continue;
            if(v[n] == cv)
                hasCycle = true;
            else if(v[n] == -1)
                dfs(n, cur, cv);
        }
    }


    public static void main(String[] args) throws IOException{
        N = read();
        M = read();
        g = new ArrayList[N+1];
        for(int i = 1; i<=N; i++)
            g[i] = new ArrayList<>();

        v = new int[N+1];
        Arrays.fill(v,-1);

        while(M-->0){
            int u = read();
            int vv = read();
            g[u].add(vv);
            g[vv].add(u);
        }

        int ans = 0;
        for(int i = 1; i<=N; i++){
            if(v[i] == -1){
                hasCycle = false;
                dfs(i,-1,vNum++);
                if(!hasCycle)
                    ans++;
            }
        }
        System.out.print(ans);
    }
}

사고의 흐름

입력으로 주어지는 그래프는 무방향 트리이고 여러 컴포넌트로 이루어져 있다. 

따라서 visited를 int로 잡고 컴포넌트 번호를 해당 탐색의 번호로 준다. 

그리고 주어진 그래프 내에서 

• 사이클이 없습니다.
• 정점이 N개이면, 간선이 N−1개 있습니다
• 임의의 두 정점에 대해서 경로가 유일합니다.

위 조건은 결국 사이클 검출 로직을 묻는 문제이다.

 

풀이

visited 초기값을 -1로 잡고 vNum을 0부터 시작한다. 

그리고 아직 방문하지 않은 정점에 대해서 시작정점으로 잡고 트리의 형태니까 dfs로 방문을 하고 중간에 현재 탐색 번호가 걸려있는 visited를 만나게 되면 사이클이라고 전역 변수에 기록한다.

 

주의점

여기서 현재 vNum이 기록된 visited를 다시 만났다 하더라도 바로 boolean 반환형으로 return 하면 안된다.

왜냐하면 그 다음 서브트리에 대해서 탐색을 전부 수행하지 않고 끝날 수 있기 때문에 모든 정점을 볼 수 없기 때문이다.

 

공식 풀이와의 비교

공식 풀이는 dfs로 탐색을 하면서 지금까지의 정점 갯수와 간선 갯수를 센다. 

그리고 무방향 그래프이기 때문에 정점 갯수를 /2를 해 주고 이를 간선 갯수와 비교해서 

-> 정점이 N개일때 간선이 N-1개인 성질 활용

해서 푼다.

---

문제 - 이진트리 순회

https://www.codetree.ai/ko/trails/complete/curated-cards/intro-the-tree-traversal/description

트리 순회 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int readNum() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static char read() throws IOException{
        sst.nextToken();

        if(sst.ttype == StreamTokenizer.TT_WORD)
            return sst.sval.charAt(0);

        return (char) sst.ttype;
    }

    static int N;
    // 왼쪽, 오른쪽 자식
    static char[] left;
    static char[] right;
    static StringBuilder sb = new StringBuilder();

    static void preOrder(int ci){
        char cur = (char)(ci + 'A');
        sb.append(cur);
        if(left[ci] != '.')
            preOrder(left[ci]-'A');
        if(right[ci] != '.')
            preOrder(right[ci]-'A');
    }

    static void inOrder(int ci){
        char cur = (char)(ci + 'A');
        
        if(left[ci] != '.')
            inOrder(left[ci]-'A');
        sb.append(cur);
        if(right[ci] != '.')
            inOrder(right[ci]-'A');
    }

    static void postOrder(int ci){
        char cur = (char)(ci + 'A');
        
        if(left[ci] != '.')
            postOrder(left[ci]-'A');
        if(right[ci] != '.')
            postOrder(right[ci]-'A');
        sb.append(cur);
    }

    public static void main(String[] args) throws IOException{
        // 파싱문제
        sst.ordinaryChar('.');

        N = readNum();
        left = new char[26];
        Arrays.fill(left, '.');
        right = new char[26];
        Arrays.fill(right, '.');

        while(N-->0){
            char u = read();
            char v1 = read();
            char v2 = read();

            left[u-'A'] = v1;
            right[u-'A'] = v2;
        }

        preOrder(0);
        sb.append("\n");
        inOrder(0);
        sb.append("\n");
        postOrder(0);

        System.out.print(sb);
    }
}

사고의 흐름

전위, 중위, 후위 재귀로 자식 유무 체크해서 이진트리로 받아온 데이터를 탐색하고 valid한 노드가 발견될 때 출력해주면 된다.

 

풀이

해당 문제에서는 완전 이진 트리라고 명시하지 않아서 1<<N 크기의 배열을 설정하고 노드 번호 자체로 인덱스를 설정하게 되면

실제 노드 값과 인덱스가 밀려서 트리를 제대로 형성할 수 없다. 

그냥 이진트리이기 때문에 클래스로 left, right 잡아주던가 left, right 배열을 설정해서 트리를 구성해야한다.

여기서는 입력이 [ A, Z ] 이기 때문에 각각 26으로 크기 잡아서 왼쪽 자식, 오른쪽 자식을 넣어주고 초기값을 '.'로 잡아줬다.

---

문제 - 트리 중위 순회

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-tree-inorder/description

트리 중위 순회 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int K;
    static int[] tree;
    static ArrayList<Integer>[] level;

    static void dfs(int s, int e, int cl){
        // 종료조건
        if(s > e)
            return;

        int mid = (s+e)/2;
        dfs(s,mid-1,cl+1);
        level[cl].add(tree[mid]);
        dfs(mid+1,e,cl+1);
    } 

    public static void main(String[] args) throws IOException{
        K = read();
        tree = new int[(1<<K)-1];
        level = new ArrayList[K];
        for(int i = 0; i<K; i++)
            level[i] = new ArrayList<>();

        for(int i = 0; i<(1<<K)-1; i++){
            tree[i] = read();
        }

        dfs(0, (1<<K)-2, 0);
        StringBuilder sb = new StringBuilder();
        for(ArrayList<Integer> a : level){
            for(int n : a)
                sb.append(n).append(" ");
            sb.append("\n");
        }
        System.out.print(sb);
    }
}

사고의 흐름

문제에서 주어진건 중위 순회 결과이다. 중위 순회는 루트가 중앙에 오고 왼쪽 과 오른쪽으로 나뉘어지며 (이진 트리니까)

그러면 또다시 왼쪽 파트의 중간은 아까 루트의 왼쪽 자식이 되고 오른쪽도 똑같다. 

이걸 일반화하면 현재 왼쪽 끝 인덱스와 오른쪽 끝 인덱스를 파라미터로 주고 inOrder 순회처럼 중간에 값 처리하는걸 넣고 

dfs(prevLeft, mid-1) + curRoot(mid) + dfs(mid+1, preRight)

Top-Down 식으로 재귀 진행하고 left가 right보다 커지게 되면 리턴하는 식으로 하면 될 거 같았다.

 

풀이

근데 분명 트리 구성은 되는거 같은데 출력을 찍어보니까 모양이 안 맞는다. 

정확히는 레벨 구성을 제대로 구현하지 못하고 있었다. 

그래서 현재 루트는 현재 레벨에 붙여주고 파라미터로 레벨 값 + 1을 넘겨서 

다음 자식들은 바로 아래 레벨의 List에 붙여 줌으로써 해결하고 

출력은 List 배열인 level을 따라가며 적절히 출력해주면 된다.

 

공식 풀이와의 비교

난 직관적인 관찰에 의한 분할-정복으로 해결했고 공식 해설은 트리의 성질을 이용해 직접 인덱스로 값을 삽입하는 방식을 취했다.

완전 이진 트리에서 inOrder를 하면 배열 인덱스 순서와 딱 맞는다는 것을 활용해 문제를 재정의하는 방식이다. 

---

문제 - 트리 경유

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-a-way-through-the-tree/description

트리 경유 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N,Q;
    static Set<Integer> used = new HashSet<>();

    static int setRoute(int dest){
        ArrayList<Integer> path = new ArrayList<>();

        while(dest > 0){
            path.add(dest);
            dest /= 2;
        }
        for(int i = path.size()-1; i>=0; i--){
            if(used.contains(path.get(i)))
                return path.get(i);
        }
        return 0;
    }

    public static void main(String[] args) throws IOException{
        N = read();
        Q = read();

        StringBuilder sb = new StringBuilder();
        while(Q-->0){
            int dest = read();
            int rst = setRoute(dest);
            if(rst == 0){
                used.add(dest);
            }
            sb.append(rst).append("\n");
        }
        System.out.print(sb);
    }
}

사고의 흐름

루트 -> 목적지 로 가는 경로에서 색칠된 노드가 있으면 해당 노드 번호를 출력하고, 없으면 0을 출력하라는 문제이다.

처음 읽었을 때 경로에서 visited를 공유하지 않는데 어째서 막힌 노드가 나오지?..

-> 그야 visited를 공유해야하니까! Set에다가 번호를 넣자

경로를 전부 색칠하는거 아닌가?

-> 이거때문에 문제 여러번 읽었다. 목적지에 도달 가능하면 목적지"만" 1로 색칠한다.

 

풀이

킥 발상은 경로는 루트에서 시작하나 목적지에서 시작하나 결국 트리라서 경로는 유일하다는 것이다. 

또한, 거쳐가는 노드의 종류들도 유일하여 결과가 같은데 

목적지 -> 루트 경로로 탐색하게 되면, 자식에서 부모는 1개 뿐이라 상태압축이 가능하다.

 

따라서,  목적지를 /=2 해 주며 루트까지 탐색한 경로를 저장하고 

원래는 루트 -> 목적지 이므로 루트에서 가까운 막힌 지점을 리턴해야 하니 

저장한 경로를 역으로 순회해서 만나는 가장 가까운 used 에 들어있는 노드 번호를 리턴한다. 

별 문제 없었으면 0 리턴

 

최적화 방향

지금 풀이는 Set과 쿼리마다 Integer 리스트를 쓰고 있는데 

Set 대신 전역 int 배열을 쓰던가 boolean 배열의 raw 자료형 배열을 쓰는 버릇을 들여야 한다. 

객체를 사용하는 오버헤드가 크기 때문에 StreamTokenizer로 입력 저수준으로 처리해봤자다.

---

문제 - 트리에서 공 떨어뜨리기 (다시보기)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-drop-a-ball-in-a-tree/description

트리에서 공 떨어뜨리기 설명 | 코드트리

public class Main {
    static int N;
    static long K;
    static int[] left;
    static int[] right;

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

        for(int i = 1; i<=N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            left[i] = Integer.parseInt(st.nextToken());
            right[i] = Integer.parseInt(st.nextToken());
        }

        K = Long.parseLong(br.readLine());
        int ci = 1;

        while(true){
            // 리프노드일때
            if(left[ci] == -1 && right[ci] == -1){
                System.out.print(ci);
                return;
            }

            // 자식 하나면 그냥 떨어지고
            if(left[ci] == -1)
                ci = right[ci];
            else if(right[ci] == -1)
                ci = left[ci];
            else{
                // 짝수번째 공은 오른쪽
                if(K % 2 == 0){
                    ci = right[ci];
                    K /= 2;
                }
                else{
                    ci = left[ci];
                    K = (K+1)/2;
                }
            }
        }
    }
}

사고의 흐름

루트 노드에서 시작해서 이진트리를 따라 문제 조건에 맞는 자식 노드 방향으로 리프노드까지 공을 흘려넣는 문제이다.

문제 조건에서 서브트리의 현재까지 흘려넣은 공의 합을 얘기하니까 업데이트되는 트리라고 생각해서 

세그트리를 생각했는데 K가 최대 10의 18승으로 long 수준으로 커서 

이걸 하나하나 시뮬레이션해서 10^18하면 당연히 터질거고 K가 엄청 큰걸 봐서는 저거 하나 잡고 쪼개가지고 할거 같았다.

 

실제로 입력을 가지고 넣어보면 K번째의 공이 짝수이면 오른쪽 자식으로 빠지고 홀수이면 왼쪽 자식으로 빠지는 홀짝성을 발견했다. 따라서 K를 가지고 적절히 2로 나눠서 리프노드 조건에 만족할때까지 반복문으로 줄여나가면 될거 같았다. 

발상을 발견하기까지가 오래 걸린 문제였다.

 

풀이

일단 left 자식과 right 자식을 저장하는 배열 두개로 입력을 받고 

while문 안에서 노드부터 시작하니 현재 노드는 1로 설정 공은 K로 설정한다.

 

1) 리프노드일때는 (left == -1 && right == -1) 바로 출력하고 끝내고

2) 자식이 하나일땐 가능한 자식으로 노드를 이동한다.

3) 자식이 둘일때는 K의 홀짝성으로 판단해서

짝수는 오른쪽 자식으로 노드 업데이트 하고 /=2,

홀수는 왼쪽 자식으로 노드 업데이트하고 +1한뒤 /=2

---

문제 - 트리 순회법 변경 2,3

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-change-tree-traversal-3/description

트리 순회법 변경 3 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N;
    static int[] in;
    static int[] post;
    static Map<Integer, Integer> nToI = new HashMap<>();
    static StringBuilder sb = new StringBuilder();

    // 복원하지 말고 바로 후위로 뽑으려면
    // L , R, root처리
    // preStart (root), inStart, inEnd
    static void dfs(int pi, int si, int ei){
        if(si > ei)
            return;

        int root = pre[pi];
        int rootIdx = nToI.get(root);
        int leftSize = rootIdx - si;

        dfs(pi+1, si, rootIdx-1);
        dfs(pi+leftSize+1, rootIdx+1, ei);
        sb.append(root).append(" ");    
    }

    // in + post 주어질때
    // postEnd (root), inStart, inEnd
    static void dfs(int ep, int si, int ei){
        if(si > ei)
            return;
        
        int root = post[ep];
        int rootIdx = nToI.get(root);
        int rightSize = ei-rootIdx;

        sb.append(root).append(" ");
        dfs(ep-rightSize-1, si, rootIdx-1);
        dfs(ep-1, rootIdx+1, ei);
    }

    public static void main(String[] args) throws IOException{
        N = read();
        in = new int[N];
        post = new int[N];

        for(int i = 0; i<N; i++){
            in[i] = read();
            nToI.put(in[i], i);
        }
        
        for(int i = 0; i<N; i++){
            post[i] = read();
        }
        
        dfs(N-1, 0, N-1);
        System.out.print(sb);
    }
}

사고의 흐름

2,3 둘다 똑같은 문제다. 

2번은 중위 순회 결과와 전위 순회 결과가 주어졌을때 후위 순회 결과를 출력하는 문제이고

3번은 중위 순회 결과와 후위 순회 결과가 주어졌을때 전위 순회 결과를 출력하는 문제이다.

 

핵심 아이디어는 전위와 후위 순회 결과에서 최상위 루트노드의 위치를 파악하고 left 서브트리와 right 서브트리 구간을 나눈 후 재귀적으로 루트노드의 위치를 변경하고 루트 노드를 만날때 출력 처리라던지 여튼 처리해주면 된다.

-> 코드는 3번 코드에 2번 dfs만 참고로 가져와서 넣었다.

 

풀이

먼저 root value를 구해야 한다.

루트 값은 중위 순회 결과와 같이 주어지는 다른 순회 결과의 종류를 보고 알아내면 된다. 

-> 다른 순회 [ rootIdx (parameter) ]

 

중위 순회 결과는 위에서 구한 root value를 이용해서 중위 순회 안에서 루트 인덱스를 알아내게 되면 그것을 중심으로 

왼쪽 자식과 오른쪽 자식의 구간을 특정할 수 있게 된다. 

-> 매번 탐색하는건 비효율적이므로 입력할때 중위 순호의 값-인덱스 페어링을 해서 map에서 O(1)에 찾도록 한다.

전위 순회 결과는 왼쪽에서부터 루트 + 왼쪽 subtree + 오른쪽 subtree 으로 이루어져 있다. 

-> 왼쪽 서브트리의 새 root Idx = 현재 루트 인덱스의 + 1

-> 오른쪽 서브트리의 root Idx = 현재 루트 인덱스의 + 1 + 왼쪽 서브트리의 크기

 

후위 순회 결과는 끝에서부터 왼쪽 subtree + 오른쪽 subtree + 루트 로 이루어져 있다.

-> 왼쪽 서브트리의 새 root Idx = 현재 루트 인덱스 - 오른쪽 서브트리의 크기 - 1

-> 오른쪽 서브트리의 새 root Idx = 현재 루트 인덱스 - 1

 

이렇게 넣고 출력해줄 방법에 따라 root 만났을때 순서에 맞게 처리해주면 된다.

 

왜 전위 + 후위로는 풀 수 없을까?

중위 결과가 주어지는 이유는 전위, 후위로는 최상위 루트를 알 수 있지만

왼쪽 subtree와 오른쪽 subtree의 경계를 유일하게 정할 수 있는 방법이 존재하지 않기 때문이다. 

다시 말해, 굳이 중위 결과가 아니더라도 경계를 정할 수 있는 조건(heap 정렬이라던지)이 주어진다면 

전위만으로도 트리를 올바르게 재구성할 수 있기 때문이다.

---

문제 - 트리 순회법 변경

https://www.codetree.ai/ko/trails/complete/curated-cards/test-change-tree-traversal/description

트리 순회법 변경 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N;
    static int[] pre;
    static int[] nextGreat;
    static StringBuilder sb = new StringBuilder();

    // 후위로 출력
    static void dfs(int s, int e){
        if(s > e)
            return;
        
        int root = pre[s];
        int mid = nextGreat[s];

        if(mid > e)
            mid = e+1;

        // l,r, root
        dfs(s+1, mid-1);
        dfs(mid, e);
        sb.append(root).append("\n");
    }

    public static void main(String[] args) throws IOException{
        N = read();
        pre = new int[N];
        for(int i = 0; i<N; i++){
            pre[i] = read();
        }
        nextGreat = new int[N];
        // 만약 root보다 큰 값이 끝까지 없으면 갱신이 안되니까
        Arrays.fill(nextGreat, N);

        // 전에 지난 원소들이 현재 원소보다 작으면 
        // 그 원소들의 다음으로 큰 값 인덱스는 현재 원소의 인덱스임
        Deque<Integer> s = new ArrayDeque<>();
        for(int i = 0; i<N; i++){
            while(!s.isEmpty() && pre[i] > pre[s.peekFirst()])
                nextGreat[s.pollFirst()] = i;
            s.addFirst(i);
        }
        dfs(0,N-1);
        System.out.print(sb);
    }
}

사고의 흐름

바로 위에 문제에서 전위 + 구간을 정해주는 적당한 기준이면 어떻게 되나 상상했는데 딱 그 조건을 달고 다음 문제로 나왔다.

해당 문제는 전위 탐색 결과가 주어지고 트리에서의 삽입 기준이 주어진다. 

조건은 현재 노드보다 작으면 왼쪽, 크면 오른쪽이다. BST 의 조건이다. 

 

입력으로는 pre order 가 주어지는데 각 subtree의 구간을 정하는 기준은 현재 root 값보다 처음으로 큰 원소의 등장 위치이다.

naive하게 구현하면 재귀로 매번 pre를 읽어서 탐색하는 방법이 있긴 한데 비효율적이고 이걸 뭔가 빠르게 처리하는 방법이 아무래도 정답을 가르는 포인트라고 생각된다.

-> 약간 그 백준에서 히스토그램에서 가장 큰 직사각형을 세그트리 말고 스택으로 푸는 느낌으로 

pre를 가지고 O(N)에 전처리해주고 오른쪽 자식이 시작되는 부분을 재귀마다 O(1)에 구하면 될 거 같았다.

 

전처리 : 모노토닉 스택 활용

nextGreat [ i ] 는 현재 값( pre[ i ]  )보다 큰 값이 처음으로 나타나는 pre의 인덱스를 저장한다.

만약 루트값보다 큰 값이 뒤에서 한번도 나타나지 않을 때를 고려해서 초기화를 꼭 시켜줘야 한다.

-> 끝까지 한번도 안 나타난다면 끝을 의미하는 N을 넣어줌

-> N-1이 아닌 이유는 그 이후를 나타내는 거니까 N임

 

for문으로 모든 인덱스에 대해서 연산용 임시 스택을 하나 두고 

스택에 값이 존재하고 스택의 가장 위의 값( idx )이 가르키는 값( pre[ idx ] )이 현재 값보다 작으면

이 조건을 만족하지 않을때까지 다 뽑아내서 nextGreat [ poll Value ] 에 현재 idx를 저장한다.

그리고 현재 인덱스를 스택에 push

  

풀이

재귀적으로 start와 end를 구해서 풀면 된다. 

start가 end보다 커지면 리턴하고 

주어진 전위 탐색은 맨 앞이 root 이므로 root = pre [ start ] 이고 

오른쪽 자식 루트는 현재 root 값보다 처음으로 등장하는 더 큰 수의 위치이기 때문에 nextGreat [ start ] 로 바로 구한다.

 

문제에서 요구하는 출력 방식은 후위탐색이므로 그 순서에 맞게 처리하면 된다.

왼쪽자식 -> dfs ( s+1, mid-1 ) , 오른쪽 자식 -> dfs ( mid, e ) , Root -> 출력 처리

 

오른쪽 sub tree 주의점

여기서 오른쪽 자식 값을 nextGreat로 구했을 때

만약 현재 오른쪽 구간 값을 벗어난다면 (더 큰 노드가 없다면) e + 1로 보정해줘야 한다. 

-> 이 상황은 지금 처리하는 구간이 [ s, e ] 인데 현재 root 값보다 더 큰 숫자들이 존재하지 않아서 

오른쪽 트리가 비게 되는 상황을 말하는 것이므로 mid가 e+1된다면 자동으로 

오른쪽 자식 subtree는 dfs( e+1, e ) 가 되어 빈 sub tree로 취급되고 다음 재귀 호출때 종료된다.

 

 

#코드트리 #코딩테스트 #코테공부 #코테독학 #개발자루틴 #1일1코테