[ 백준 - 1068 ] 트리

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

1068번: 트리

트리가 주어지고 그래프를 구성해서 그래프 탐색 알고리즘을 사용해서 푸는 문제이다.

목표는 리프 노드의 개수를 구하는 것이고, 고려 조건은 단 1개로 1개의 지워지는 노드가 있다는 점이다.

---

[ 📌 풀이 ]

• 루트 노드를 기록해두었다. (탐색 시작 기준을 정하기 위해서)
  • 지워지는 노드가 있기 때문에 임의의 노드를 기준으로 탐색을 하게되면 안된다.
• 지워지는 노드는 그래프에 넣지 않았다.
  • 지워지는 노드를 그래프에서 제외 한다면 탐색할 때 해당 노드를 방문하지 않기 때문에 
• 루트 노드가 지워지는 노드라면 0을 출력하고 시스템을 종료

---

[ 📌 주의 사항 ]

• 루트 노드가 삭제되면 탐색 없이 0 출력 후 종료
• 그래프가 순환참조 형식으로 2개의 노드가 서로의 자식으로 있다면 2가 출력되어야 한다. (별도의 처리는 안하지만 고려 해야함)

[ 순환 그래프 ]

두 노드가 리프 노드이자 루트 노드이기 때문에 카운팅이 되어야 한다.

---

[ 📌 코드 - Python ]

import sys
from collections import deque
inp = sys.stdin.readline

N = int(inp())
root = sys.maxsize
nodes = list(map(int, inp().split()))
graph = [[] for _ in range(N)]
R = int(inp())

for idx in range(N):
  if nodes[idx] == -1:
    root = idx

  if idx == R:
    continue

  if nodes[idx] != -1:
    graph[nodes[idx]].append(idx)

print(graph)

if R == root:
  print(0)
  sys.exit()

def bfs():
  visited = [False] * N
  visited[R] = True
  queue = deque()
  queue.append(root)
  cnt = 0

  while queue:
    curN = queue.pop()

    if len(graph[curN]) == 0:
      cnt += 1
      continue

    for nextN in graph[curN]:
      if not visited[nextN]:
        visited[nextN] = True
        queue.append(nextN)

  return cnt

print(bfs())

[ 📌 코드 - Java  ]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class Q1068 {
  
  public static int N;
  public static LinkedList<Integer>[] graph;
  public static int R;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    int[] nodes = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    R = Integer.parseInt(br.readLine());
    graph = new LinkedList[N];
    int root = Integer.MAX_VALUE;

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

    for(int i = 0; i < N; i++){
      // 루트 삭제시 종료
      if(nodes[i] == -1 && i == R) {
        System.out.println(0);
        System.exit(0);
      }

      // 삭제된 인덱스의 노드인 경우 그래프에서 제외
      if(i == R) {
        continue;
      }

      // 루트 x: 그래프에 추가
      // 루트 o: root 인덱스 기록(시작 노드 기록)
      if(nodes[i] != -1) {
        graph[nodes[i]].add(i);
      } else if(nodes[i] == -1) {
        root = i;
      }
    }

    System.out.println(bfs(root));
  }

  public static int bfs(int root) {
    Queue<Integer> queue = new LinkedList<>();
    boolean[] visited = new boolean[N];
    int cnt = 0;

    queue.add(root);
    visited[root] = true;

    while(!queue.isEmpty()) {
      int cur = queue.poll();

      if(graph[cur].size() == 0) {
        cnt++;
        continue;
      }

      Iterator<Integer> it = graph[cur].iterator();

      while(it.hasNext()) {
        int next = it.next();

        if(!visited[next]) {
          queue.add(next);
          visited[next] = true;
        }
      }
    }

    return cnt;
  }
}

---

[ 📌 결과 - Python & Java  ]

[ Result - Java & Python ]