[240430] 알고리즘 리부트 56일차 - 백준 11725, 11681 자바

[Part2-Chapter04-Clip02]

- 백준 11725 트리의 부모 찾기

트리도 그래프의 일종이다. 단, 순환이 없는 그래프이다. 그래프 문제를 풀 때와 마찬가지로 인접 리스트를 선언하고 간선의 양 끝 정점을 리스트에 담아줬다. 부모를 찾는 함수를 구현하는 데 약간 어려움을 겪었다. 정점들을 연결된 순서대로 타고 가는데 루트 노드인 1부터 시작해서 따라가다 보면 직전의 정점이 즉, 나를 호출한 정점이 부모가 되는 로직이다. 이미 방문한 경우는 제외하고 자식 노드를 계속 찾아나가면서 자식 노드를 찾을 때마다 정답 배열에 부모인 직전 정점을 넣어주면 문제를 해결할 수 있다.

package BaekJoon.tree;

import java.util.ArrayList;
import java.util.Scanner;

public class BJ11725 {
    public static int n;
    public static ArrayList[] tree;
    public static int[] ans;
    public static boolean[] visited;

    public static void main(String[] args) {
        // 루트는 1 -> 항상

        // 정점 갯수 입력 받고
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();

        tree = new ArrayList[n + 1];

        for (int i = 0; i <= n; i++) tree[i] = new ArrayList<Integer>();

        // 연결된 두 정점 입력 받기 -> 인접 리스트
        for (int i = 0; i < n - 1; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            tree[a].add(b);
            tree[b].add(a);
        }

        ans = new int[n + 1];
        visited = new boolean[n + 1];


        findParents(1);

        for (int i = 2; i <= n; i++) {
            System.out.println(ans[i]);
        }

    }

    private static void findParents(int target) {

        visited[target] = true;

        for (int i = 0; i < tree[target].size(); i++) {
            int curr = (int) tree[target].get(i);
            if (visited[curr]) continue;
            ans[curr] = target;
            //System.out.printf("%d의 부모는 %d\n", curr, target);

            findParents(curr);
        }

    }
}

 

[Part2-Chapter04-Clip03]

- 백준 11681 트리와 쿼리

 

모든 정점에 자신의 갯수를 1로 초기화해놓고 다시 본인 함수로 돌아왔을 때 (부모 노드로 돌아와서는) 자식의 정점에서의 갯수를 본인의 갯수에 더해주면 하위 정점의 갯수를 누적해서 더할 수 있다.

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {

    public static int n, r, q;
    public static ArrayList[] tree;
    public static boolean[] visited;
    public static int[] ans;
    public static BufferedWriter bw;

    public static void main(String[] args) throws IOException {

        Scanner sc = new Scanner(System.in);
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = sc.nextInt();
        r = sc.nextInt();
        q = sc.nextInt();

        tree = new ArrayList[n + 1];
        visited = new boolean[n + 1];
        ans = new int[n + 1];

        for (int i = 0; i <= n; i++) tree[i] = new ArrayList<Integer>();

        for (int i = 0; i < n - 1; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            tree[u].add(v); // 가중치와 방향성이 없기 때문에 양방향으로!
            tree[v].add(u);
        }

        findDepth(r);

        for (int i = 0; i < q; i++) {
            int target = sc.nextInt();
            bw.write(ans[target] + "\n");
        }

        bw.flush();
        bw.close();
    }

    private static void findDepth(int node) {

        visited[node] = true;
        ans[node] = 1;

        for (int i = 0; i < tree[node].size(); i++) {
            int now = (int) tree[node].get(i);
            if (visited[now]) continue;
            findDepth(now); 
            ans[node] += ans[now];
        }
    }
}

메모리 초과 코드

package BaekJoon.tree;

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.*;

public class BJ15681 {

    public static int n, r, q, cnt;
    public static ArrayList[] tree;
    public static boolean[] visited;
    public static int[] depth;
    public static BufferedWriter bw;

    public static void main(String[] args) throws IOException {

        Scanner sc = new Scanner(System.in);
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = sc.nextInt();
        r = sc.nextInt();
        q = sc.nextInt();

        tree = new ArrayList[n + 1];
        visited = new boolean[n + 1];
        depth = new int[n + 1];

        for (int i = 0; i <= n; i++) tree[i] = new ArrayList<Integer>();

        for (int i = 0; i < n - 1; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            tree[u].add(v); // 가중치와 방향성이 없기 때문에 양방향으로!
            tree[v].add(u);
        }

        findDepth(r, 1);

        //System.out.println(Arrays.toString(depth));

        for (int i = 0; i < q; i++) {
            visited = new boolean[n + 1];
            int target = sc.nextInt();
            cnt = 0;
            getCount(target);
            bw.write(cnt + "\n");
        }

        bw.flush();
        bw.close();
    }

    private static void getCount(int target) {
        visited[target] = true;
        cnt++;

        for (int i = 0; i < tree[target].size(); i++) {
            int now = (int) tree[target].get(i);
            if (visited[now] || depth[target] > depth[now]) continue;
            visited[now] = true;
            getCount(now);
        }
    }

    private static void findDepth(int node, int dep) {

        visited[node] = true;
        depth[node] = dep;

        for (int i = 0; i < tree[node].size(); i++) {
            int now = (int) tree[node].get(i);
            if (visited[now]) continue;
            visited[now] = true;
            findDepth(now, dep + 1);
        }
    }
}