230828 - [Java-Python] Tree

[robert-min]

BOJ.11725 트리의 부모 찾기 링크

• 문제풀이
  • dfs 특징 활용 이전 노드가 다음 노드의 부모노드!!

python

import sys
input = sys.stdin.readline

N = int(input())
graph = [[] for _ in range(N+1)]

for _ in range(N-1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

from collections import deque

visited = [False] * (N+1)
result = []
def dfs():
    stack = deque()
    stack.append(1)
    visited[1] = True

    while stack:
        now = stack.pop()

        for nx in graph[now]:
            if not visited[nx]:
                visited[nx] = True
                result.append((nx, now))
                stack.append(nx)

dfs()

result = sorted(result, key=lambda x: x[0])
for r in result: print(r[1]) 

java

import java.io.*;
import java.util.*;

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        input();
        solution();
    }

    static int n;
    static ArrayList<Integer>[] adj;
    static int[] parent;

    static void input() {
        n = scan.nextInt();
        adj = new ArrayList[n+1];
        parent = new int[n+1];
        for (int i=1; i <= n; i++) adj[i] = new ArrayList<>();

        for (int i=1; i<n; i++) {
            int x = scan.nextInt(), y = scan.nextInt();
            adj[x].add(y);
            adj[y].add(x);
        }
    }

    static void solution() {
        // Root 1부터 Tree 구조 파악, root는 부모가 없으니 -1
        dfs(1, -1);

        for (int i=2; i <= n; i++) {
            sb.append(parent[i]).append("\n");
        }
        System.out.println(sb);
    }

    static void dfs(int x, int par) {
        for (int y: adj[x]) {
            if (y == par) continue;
            parent[y] = x;
            dfs(y, x);
        }
    }
}

[robert-min]

BOJ.1068 트리 링크

python

import sys
input = sys.stdin.readline

N = int(input())
parents = list(map(int, input().split()))
erased = int(input())

# tree
child = [[] for _ in range(N)]
leaf = [0] * N
root = 1
for i in range(N):
    if parents[i] == -1:
        root = i
    else:
        if erased == i: continue

        child[parents[i]].append(i)

def dfs(x, par):
    if not child[x]:
        leaf[x] = 1

    for y in child[x]:
        if y == par: continue

        dfs(y, x)
        leaf[x] += leaf[y]

if root != erased:
    dfs(root, -1)

print(leaf)

import sys
input = sys.stdin.readline

def dfs(v):
    tree[v] = -2
    for i in range(n): #전체 트리 반복
        if v == tree[i]: # 지우고자 하는 노드 v가  tree[i]에 들어있으면 tree[i]는 v의 자식
            dfs(i) # i의 자식도 지움

n = int(input())
tree = list(map(int, input().split())) # [-1, 0, 0, 1, 1]
erase = int(input())

cnt = 0

for i in range(n):
    if tree[i] != -2 and i not in tree: #-2는 지우는 노드들 // i노드의 자식이 트리 안에 없으면 == 리프노드임
        cnt+=1

print(cnt)

java

import java.io.*;
import java.util.*;

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        input();

        solution();

        System.out.println(leaf[root]);
    }

    static int n, root, erased;
    static ArrayList<Integer>[] child;
    static int[] leaf;

    static void input() {
        n = scan.nextInt();
        child = new ArrayList[n];
        leaf = new int[n];
        for (int i=0; i<n; i++) child[i] = new ArrayList<>();
        for (int i=0; i<n; i++) {
            int par = scan.nextInt();
            if (par == -1) {
                root = i;
                continue;
            }
            child[par].add(i);
        }
        erased = scan.nextInt();
    }

    static void solution() {
        // erased로 해당 노드와 부모사이 연결 삭제
        for (int i = 0; i < n; i++) {
            if (child[i].contains(erased)) {
                child[i].remove(child[i].indexOf(erased));
            }
        }

        // erased가 root 인 예외 처리
        if (root != erased) dfs(root, -1);
    }

    static void dfs(int x, int par) {
        if (child[x].isEmpty())
            leaf[x]++;
        for (int y : child[x]) {
            if (y == par) continue;
            dfs(y, x);
            leaf[x] += leaf[y];
        }
    }
}