[백준] 1068 트리

깊이 우선 탐색으로 문제를 푼 사람이 많은 것 같지만 개인적으로 너비 우선 탐색 알고리즘이 더 익숙해서 너비 우선 탐색 알고리즘으로 풀었다.

제거된 노드는 배열에 미리 방문된 노드로 표시하고 너비 우선 탐색을 실시한다. 마지막 리프 노드에 도달 할 경우 카운트를 올려준다. 이렇게 풀 경우 제거된 노드로 인하여 리프 노드가 될 경우를 카운트 해주는 if문을 이용해야한다.

#include <cstring>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

vector<int> vec[51];
int is_visited[51];

int main() {
  int n, root, del, cnt = 0;
  queue<int> q;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int tmp;
    cin >> tmp;
    if (tmp == -1) {
      root = i;
    } else {
      vec[tmp].push_back(i);
    }
  }
  cin >> del;
  memset(is_visited, 0, sizeof(is_visited));
  q.push(root);
  is_visited[root] = 1;
  is_visited[del] = 1;
  if (root == del) {
    cout << 0;
    return 0;
  }
  while (!q.empty()) {
    int current_node = q.front();
    is_visited[current_node] = 1;
    q.pop();

    if (!vec[current_node].size()) {
      cnt++;
    }
    for (int i = 0; i < vec[current_node].size(); i++) {
      if (vec[current_node].size() == 1 && vec[current_node][i] == del) {
        cnt++;
      }
      if (is_visited[vec[current_node][i]])
        continue;
      q.push(vec[current_node][i]);
    }
  }
  cout << cnt;
  return 0;
}

[백준] 1068 트리

Abstract

[백준] 1068번 트리

알고리즘 유형

문제 이해

풀이방법