[BOJ][실1][1068] 트리

문제 링크

문제링크

첫 번째 풀이 : DFS

알고리즘

인접리스트로 정보를 저장한 후 전체 리프 노드의 갯수를 count합니다. 그리고 지우려하는 노드부터 dfs를 진행해서 leaf 노드의 갯수만큼 뺍니다. 이 때 지운 노드에 의해서 지운 노드의 부모가 leaf가 되는지 추가적으로 확인해야 합니다.

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
vector<int> v[50];
vector<bool> visited(50, false);
vector<int> root;
int ans = 0;
void dfs(int x) {
    visited[x] = true;
    
    bool flag = true; // 리프노드이면 true
    for (int i = 0; i < v[x].size(); i++) {
        int next = v[x][i];
        if (!visited[next]) {
            dfs(next);
            flag = false;
        }
    }
    if (flag)ans--;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    
    int t = 0;
    for (int i = 0; i < n; i++) {
        cin >> t;
        if (t == -1) {
            root.push_back(i);
        }
        else {
            // t는 i의 부모
            v[t].push_back(i);
        }
    }

    for (int i = 0; i < n; i++) {
        if (v[i].size() == 0) ans++;
    }

    cin >> t;

    dfs(t);
    for (int i = 0; i < n; i++) {
        if (v[i].size() == 1 && v[i][0] == t) ans++;
    }
    cout << ans << "\n";
    return 0;
}

두 번째 풀이 : dfs

알고리즘

그래프를 문제에서 주어진 그대로, 각 노드의 부모 노드 번호를 저장하는 형태로 사용합니다.

추가적인 설명은 주석으로 남겨놨습니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
int p[50]; // parent number
int c[50]; // # of child

// 현재 노드를 지운다
void dfs(int x) {
  // 부모의 자식을 1개 줄인다
  if (p[x] != -1) {
    c[p[x]]--;
  }
  // 현재 노드의 부모를 없애기
  c[x] = -1;
  
  // 자식노드도 같은 과정 반복하기
  for (int i = 0; i < n; i++) {
    if (p[i] == x) {
      dfs(i);
    }
  }

}

int main()
{
  //freopen("input.txt", "r", stdin);
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> p[i];
    if (p[i] != -1) {
      c[p[i]]++; // 부모가 가지는 자식의 갯수 + 1
    }
  }
  int d = 0;
  cin >> d;
  dfs(d);
  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (c[i] == 0) ans++;
  }
  cout << ans;

  return 0;
}

세 번째 풀이 : DFS

알고리즘

그래프에서 특정 노드를 삭제하는 유형을 자주 나옵니다. 세 번째 풀이는 삭제하려고 하는 노드를 미리 방문했다고 처리하고, 방문한 곳은 dfs를 더이상 진행하지 않도록 해서 leaf의 갯수를 파악하는 방법입니다.

소스 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
vector<int> v[50];
vector<bool> visited(50, false);

int root = 0;
int ans = 0;
void dfs(int x) {
    // 이미 방문한 노드인 경우 종료
    if (visited[x]) return;

    // 노드방문
    visited[x] = true;

    bool flag = true; // 리프노드이면 true
    for (int i = 0; i < v[x].size(); i++) {
        int next = v[x][i];
        if (!visited[next]) {
            dfs(next);
            flag = false; // 방문하지 않는 자식 노드가 있는 경우
        }
    }
    if (flag)ans++;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;

    int t = 0;
    for (int i = 0; i < n; i++) {
        cin >> t;
        if (t == -1) {
            root = i;
        }
        else {
            // t는 i의 루트
            v[t].push_back(i);
        }
    }
    cin >> t;
    // 지워야하는 노드 방문처리
    visited[t] = true;

    dfs(root);
    cout << ans << "\n";
    return 0;
}

Success Notice: 수고하셨습니다.