[JAVA] 백준 트리 뿌수기4

 

 

이전글

https://fladi.tistory.com/405

[JAVA] 백준 트리 뿌수기1

https://fladi.tistory.com/406

[JAVA] 백준 트리 뿌수기2

https://fladi.tistory.com/407

[JAVA] 백준 트리 뿌수기3

 

 

트리부수기 시즌4다! 크리스마스 전에 골드3을 거의 다 부숴서 다행이당

 

 

 

 

 

1135 뉴스 전하기 - 골드2

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

1135번: 뉴스 전하기

• dp냄새가 난다
• 일단 트리를 만들고 루트부터 내려가면서 재귀호출을 해주며 dp를 하면 될 것 같다
• 내가 들을 수 있는 시간 1부터 시작
• 자식들 시간을 오름차순 정렬해서 각각 1,2,3,4, ...를 더해주고, 여기의 최댓값을 반환
• 이걸 계속 민식이까지 반복하고 출력하면 될듯 

 

public class Main {
    static ArrayList<Integer>[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cnt = Integer.parseInt(br.readLine());

        arr = new ArrayList[cnt];
        for (int i =0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        st.nextToken();
        for (int i =1; i<cnt; i++) {
            int parent = Integer.parseInt(st.nextToken());
            arr[parent].add(i);
        }

        int min = getValue(0);
        System.out.println(min);
    }

    private static int getValue(int node) {
        ArrayList<Integer> children = arr[node];
        int childCnt = children.size();
        if (childCnt == 0) {
            return 0;
        }

        Integer[] values = new Integer[childCnt];
        for (int i=0; i<childCnt; i++) {
            values[i] = getValue(children.get(i));
        }

        Arrays.sort(values, Collections.reverseOrder());

        int max = 0;
        for (int i=1; i<=childCnt; i++) {
            values[i-1] += i;
            if (values[i-1] > max) {
                max = values[i-1];
            }
        }

        return max;
    }
}

• dp인거 빼면 어렵지 않은 문제다

 

 

1167 트리의 지름 - 골드2

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

1167번: 트리의 지름

• 이전에 푼 기억이 난다
  • 지름이 되려면 무조건 지름의 한 끝은 리프노드여야함
  • 이전에는 리프노드들에 대해 dfs로 나와 가장 먼 지름을 찾아줬었다
  • => 시간초과
• 구글링을 하여 새로운 방식의 접근법을 알아냈다
• 풀이법:
  1. 임의의 점에서 나와 가장 먼 점 찾기
  2. 해당 점에서 가장 먼 점과의 거리를 구하기 = 지름
• 임의의 리프노드에서 가장 먼 점은 트리의 지름의 끝 점 2개 중 하나이다. 
• 이 증명은 다음과 같이 할 수 있음

 

case1) 지름 끝 점 A와 B가 직접 연결된 경우

• A와 B는 무조건 리프노드여야하므로, 옆에 다른 노드가 붙을 수 없음

 

case2) 지름의 끝 점 A와 B 사이에 다른 노드가 있는 경우

• u에서 가장 먼 점은 A와 B 중 하나여야한다.
• 이를 증명하기 위해 지름의 구성점이 아닌 v에 대해 u -> v가 u에서 가장 먼 점이라고 가정해보자 (이제 이게 모순이라는 걸 밝혀야함)
• (u -> v) 가 최대거리라면 (? -> v)가 (A -> ?), (B -> ?) 보다 커야한다.
  • 이렇게 되면 (A -> ? -> v)가 (A -> ? -> B)보다 크다
  • 지름보다 큰 거리가 있음(A -> ? -> B가 아님) = 모순

 

코드

class Node {
    int num;
    int distance;

    public Node(int num, int distance) {
        this.num = num;
        this.distance = distance;
    }
}

public class Main {
    static ArrayList<Node>[] arr;
    static int max = 0;
    static int far = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int nodeCnt = Integer.parseInt(br.readLine());

        arr = new ArrayList[nodeCnt];
        for (int i =0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i=0; i<nodeCnt; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int value = Integer.parseInt(st.nextToken())-1;
            while (st.hasMoreTokens()) {
                int num = Integer.parseInt(st.nextToken())-1;
                if (num == -2) {
                    break;
                }
                int distance = Integer.parseInt(st.nextToken());

                arr[value].add(new Node(num, distance));
            }
        }

        //이어진 개수가 하나인 애들 다 모으기 - 리프노드
        for (int i =0; i<arr.length; i++) {
            if (arr[i].size() == 1) {
                dfs(i, i, 0);
                break;
            }
        }

        int one = far;
        max = 0;
        dfs(one, one, 0);

        System.out.println(max);
    }

    private static void dfs(int num, int parent, int sum) {
        int cnt = 0;

        for (Node adj: arr[num]) {
            if (adj.num != parent) {
                dfs(adj.num, num, sum + adj.distance);
                cnt ++;
            }
        }

        if (cnt == 0) {
            if (sum > max) {
                max = sum;
                far = num;
            }
        }
    }
}

• 일단 아무 리프노드를 구해서 dfs를 해준다 -> 나와 가장 먼 점 far를 찾음
• far 점에 대해 dfs를 수행하고, 나와 가장 거리가 먼 노드와의 거리를 max에 저장한다
• max를 출력

 

 

 

 

1949 우수 마을 - 골드2

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

1949번: 우수 마을

• 인접하지 않는 노드를 선택하되, 주민 수 총합을 최대로하기
• 하나와 인접해야함
• dp냄새가 난다. 임의의 점에서 시작하여 dp로 풀어주면 될듯

 

public class Main {
    static int[] manCnt;
    static ArrayList<Integer>[] arr;
    static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int nodeCnt = Integer.parseInt(br.readLine());

        manCnt  = new int[nodeCnt];
        arr = new ArrayList[nodeCnt];
        for (int i =0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        dp = new int[nodeCnt][2];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i =0; i<nodeCnt; i++) {
            manCnt[i] = Integer.parseInt(st.nextToken());
        }

        for (int i =0; i<nodeCnt-1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;

            arr[a].add(b);
            arr[b].add(a);
        }

        method(0, 0);
        System.out.println(Math.max(dp[0][0], dp[0][1]));
    }

    private static void method(int num, int parent) {
        dp[num][0] = manCnt[num];
        dp[num][1] = 0;

        for (int adj: arr[num]) {
            if (adj != parent) {
                method(adj, num);
                dp[num][0] += dp[adj][1];
                dp[num][1] += Math.max(dp[adj][0], dp[adj][1]);
            }
        }
    }
}

• dp문제는 어렵게 생각할 수록 안풀리고 간단하게 생각해야 잘풀린다
• 임의의 점을 기준으로 트리를 dfs탐색해준다
• 해당 점이 우수 마을일 때, 아닐때를 구분한다
  • 우수마을일 때 = 옆마을은 우수마을이 아니다
  • 우수마을이 아닐 때 = 옆마을은 우수마을일 수도 있고, 아닐수도 있다
• 이 문제는 꼭 다시 풀어봐야겠다

 

 

 

 

2176 합리적인 이동경로 - 골드2

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

2176번: 합리적인 이동경로

• T에서 다른 정점까지 최단경로 거리를 구해야할 것 같음
  • 다익스트라를 써서 일단 최단경로 거리를 구함
  • 이후 T점에서 dfs를 하며 점점 멀어지는 곳으로 이동하면 될듯
  • => 시간초과가 났다
• 풀이를 찾아보니 dfs가 아니라 dp를 사용해야하고, 노드개수만큼만 queue에 넣어야 시간초과가 나지 않았다. 그래서 나도 정렬을 넣어봤더니 문제가 풀림
  
  • 참고한 풀이: https://chb2005.tistory.com/142

 

class Node implements Comparable<Node> {
    int end;
    int value;

    public Node(int end, int value) {
        this.end = end;
        this.value = value;
    }

    @Override
    public int compareTo(Node o) {
        return value - o.value;
    }
}

public class Main {
    static ArrayList<Node>[] arr;
    static int[] dp;
    static int[] distances;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int nodeCnt = Integer.parseInt(st.nextToken());
        int lineCnt = Integer.parseInt(st.nextToken());

        arr = new ArrayList[nodeCnt];
        for (int i =0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        dp = new int[nodeCnt];
        distances = new int[nodeCnt];

        for (int i =0; i<lineCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            int distance = Integer.parseInt(st.nextToken());

            arr[a].add(new Node(b, distance));
            arr[b].add(new Node(a, distance));
        }

        dijkstra(1);

        dp[0] = 1;
        calculate(1, distances[0]);

        System.out.println(dp[1]);
    }

    private static void calculate(int target, int minDistance) {
        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o2.value - o1.value;
            }
        });

        for (int i =0; i< distances.length; i++) {
            if (distances[i] <= minDistance) {
                pq.add(new Node(i, distances[i]));
            }
        }

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            int current = currentNode.end;

            if (current == target) {
                break;
            }

            for (Node adj: arr[current]) {
                if (distances[adj.end] < distances[current]) {
                    dp[adj.end] += dp[current];
                }
            }
        }
    }

    private static void dijkstra(int num) {
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[num] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.value - o2.value;
            }
        });
        pq.add(new Node(num, 0));

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            int current = currentNode.end;

            if (currentNode.value > distances[current]) {
                continue;
            }

            for (Node adj: arr[current]) {
                if (distances[adj.end] > distances[current] + adj.value) {
                    distances[adj.end] = distances[current] + adj.value;
                    pq.add(new Node(adj.end, distances[adj.end]));
                }
            }
        }
    }
}

• 내 풀이는 돌고돌아서 조금 꼬여있지만 pass는 된다
  1. 일단 T점부터 다익스트라로 모든 점과의 거리를 구하고 distance[] 배열에 저장
  2. calculate함수로 dp를 시작한다
  3. value값을 기준으로 내림차순 정렬하고, 점 0에서 점 1까지 거리보다 작은 애들만 PriorityQueue에 넣어준다
  4. dp[0]은 1로 설정한다(=경우의 수 1)
  5. 거리가 먼 애들(점0을 포함)을 하나씩 빼면서 dp[] 배열에 경우의 수를 더해준다
  6. 마지막에 dp[1]을 출력하면 끝

 

 

 

 

2233 사과나무 - 골드2

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

2233번: 사과나무

• 우측을 먼저 방문하는 전위순회를 한 결과가 01010로 주어진다
• 썩은 사과의 공통조상을 찾아서 해당 사과를 잘라내면 될 것 같다
• 트리를 구성하는 게 조금 까다롭고 시간초과가 날 수도 있을 것 같다 
  • 실제로 트리를 구성하니 시간초과가 났다
• 스택에 넣고 내가 pop될 때(=1일 때)를 기록하여 공통조상을 찾는 방법도 생각해봤다

 

스택풀이(내 풀이)

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

        int[] arr = new int[input.length()];
        for (int i =0; i<input.length(); i++) {
            arr[i] = Character.getNumericValue(input.charAt(i));
        }

        StringTokenizer st=  new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken())-1;
        int b = Integer.parseInt(st.nextToken())-1;

        //루트값으로 초기화
        int start = 0;
        int end = input.length()-1;

        int check = 0;

        Stack<Integer> stack = new Stack<>();
        for (int i =0; i<arr.length; i++) {
            if (i == a) {
                if (check == 0) {
                    if (arr[i] == 0) {
                        start = i;
                    } else {
                        start = stack.peek();
                    }
                }
                check ++;
            }

            if (i == b) {
                if (check == 0) {
                    if (arr[i] == 0) {
                        start = i;
                    } else {
                        start = stack.peek();
                    }
                }
                check ++;
            }


            if (arr[i] == 0) {
                stack.push(i);
            } else {
                int prev = stack.pop();
                if (prev == start) {
                    end = i;

                    if (check == 2) {
                        break;
                    }

                    if (!stack.isEmpty()) {
                        start = stack.peek();
                    }
                }
            }
        }

        System.out.println((start+1) + " " + (end+1));
    }
}

• 그냥 stack을 이용하는 방식으로 풀었다
• 노드가 같을 때, 노드가 1개일 때 등 변수가 너무 많아서 좋은 풀이는 아닌 것 같다.
• 다른 좋은 풀이가 많을 것 같아 찾아봤음

 

다른풀이

1. dpeth와 parent를 저장하여 LCA해주기
   • 이게 내 풀이보다 간단하고 좋은 풀이인 것 같다
   • LCA에 대해 내가 잘 모르는 것 같다. 그래서 이 방식으로도 풀이해보려고 함
   • https://loosie.tistory.com/606

 

 

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br.readLine();
        String input = br.readLine();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken())-1;
        int b = Integer.parseInt(st.nextToken())-1;

        int[] parent = new int[input.length()];
        int[] depth = new int[input.length()];
        int[] start = new int[input.length()];
        int[] end = new int[input.length()];

        int prev = 0;
        for (int i =0; i<input.length(); i++) {
            if (input.charAt(i) == '0') {
                start[i] = i;
                depth[i] = depth[prev]+1;
                parent[i] = prev;
                prev = i;
            } else {
                start[i] = prev;
                end[prev] = i;
                prev = parent[prev];
            }
        }

        a = start[a];
        b = start[b];

        while (depth[a] > depth[b]) {
            a = parent[a];
        }

        while (depth[a] < depth[b]) {
            b = parent[b];
        }

        while (a != b) {
            a = parent[a];
            b = parent[b];
        }

        System.out.println((a+1) + " " + (end[a]+1));
    }
}

 

 

 

 

 

2250 트리의 높이와 너비 - 골드2

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

2250번: 트리의 높이와 너비

• 너무 어려워보여서 쉬운 부분인 리프노드부터 열을 판단하려고 한다.
• 재귀호출을 사용하면서, 서브트리의 너비를 생각해야할 것 같음
• 리프노드라면 1을 반환
• 각 자식노드의 가로길이를 받아서 합치고, 나를 더한 값을 반환
• 이걸 루트까지 반복하면 열 배치가 끝난다
• bfs로 depth를 순회하며 각각의 열의 min값과 max값을 판단, 너비를 저장하고 최종 출력을 하면 될듯

 

class Node {
    int left;
    int right;
    int parent;

    public Node(int parent, int left, int right) {
        this.parent = parent;
        this.left = left;
        this.right = right;
    }
}

class Value {
    int num;
    int depth;
    int startIdx;

    public Value(int num, int depth, int startIdx) {
        this.num = num;
        this.depth = depth;
        this.startIdx = startIdx;
    }
}

public class Main {
    static Node[] nodes;
    static int[][] location;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int nodeCnt = Integer.parseInt(br.readLine());

        nodes = new Node[nodeCnt+1];
        boolean[] isNotRoot = new boolean[nodeCnt+1];

        location = new int[nodes.length][2];

        for (int i=1; i<nodes.length; i++) {
            nodes[i] = new Node(i,-1,-1);
        }

        for (int i =0; i<nodeCnt; i++) {
            StringTokenizer st= new StringTokenizer(br.readLine());
            int p = Integer.parseInt(st.nextToken());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());

            if (left != -1) {
                nodes[left].parent = p;
                isNotRoot[left] = true;
            }

            if (right != -1) {
                nodes[right].parent = p;
                isNotRoot[right] = true;
            }

            nodes[p].left = left;
            nodes[p].right = right;
        }

        int root = 1;
        for (int i =1; i<nodes.length; i++) {
            if (!isNotRoot[i]) {
                root = i;
                break;
            }
        }

        dfs(root);

        Queue<Value> queue = new LinkedList<>();
        queue.add(new Value(root, 1, 0));
        int min = Integer.MAX_VALUE;
        int max = -1;
        int result = 1;
        int resultDepth = 1;
        int depth = 1;

        while (!queue.isEmpty()) {
            Value value = queue.poll();
            int currentLocation = value.startIdx + location[value.num][0] + 1;
            if (depth != value.depth) {
                if (max - min + 1 > result) {
                    result = max - min + 1;
                    resultDepth = depth;
                }
                min = Integer.MAX_VALUE;
                max = -1;
                depth++;
            }

            if (min > currentLocation)
                min = currentLocation;

            if (max < currentLocation)
                max = currentLocation;

            if (nodes[value.num].left != -1) {
                queue.add(new Value(nodes[value.num].left, value.depth+1, value.startIdx));
            }

            if (nodes[value.num].right != -1) {
                queue.add(new Value(nodes[value.num].right, value.depth+1, currentLocation));
            }
        }

        if (max - min + 1 > result) {
            result = max - min + 1;
            resultDepth = depth;
        }

        System.out.println(resultDepth + " " + result);
    }

    private static int dfs(int num) {
        Node node = nodes[num];
        int leftSize = 0;
        int rightSize = 0;

        if (node.left != -1) {
            leftSize = dfs(node.left);
        }

        if (node.right != -1) {
            rightSize = dfs(node.right);
        }

        location[num][0] = leftSize;
        location[num][1] = rightSize;

        return leftSize+rightSize+1;
    }
}

• 아이디어만 잘 떠올리면 어렵지 않다
• dfs로 왼쪽, 오른쪽 서브트리의 크기를 재귀적으로 구하며 location에 저장해준다. location[i][0]은 왼쪽, location[i][1]은 오른쪽이다
• 이후 bfs로 트리의 깊이를 타고 내려가며 깊이마다 너비를 구해준다. 너비의 최댓값은 result에 저장하고, resultDepth에 최댓값인 depth를 저장한다.
• 그리고 출력해주면 됨