[BOJ] #1068 트리

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

1068번: 트리

---

DFS 활용해 얼마나 그래프를 능숙하게 탐색할 수 있는지 물어보는 문제인 것 같다.

문제 자체는 굉장히 간단하다. 입력을 통해 인접리스트 형태로 그래프를 주고, 삭제할 노드를 하나 제시해준다. 그러면 해당 노드를 삭제한 후, 남은 리프노드(더 이상 밑에 자식이 없는 자식노드) 의 개수를 세주면 된다.

코드의 매커니즘은 크게 3단계로 구성된다.

1. 주어진 입력에 따라 인접리스트 형태로 그래프를 구성하는 단계
2. 구성된 그래프에서 삭제할 노드를 제거하여 그래프를 재구성하는 단계
3. 재구성된 그래프를 DFS로 순회하며 리프노드를 발견할때마다 cnt를 하나씩 올려주는 단계

 

1차 시도때에 2번 단계를 생략하고 제출했었는데 4퍼센트 남짓 갔다가 틀렸습니다 가 떴다. 그 이유는 질문게시판에 어떤분이 올려주신 글을 참고해서 해결하였다.

https://www.acmicpc.net/board/view/132447

글 읽기 - 2%나 78%나 99%나서 발생할 수 있는 문제 종합..

여기서 두번째, 루트노드가 리프노드가 되는 반례를 고려하지 않았던 것이다. 따라서, 해당 반례들을 처리하려면 DFS를 돌리기 전, 구성된 그래프에서 삭제할 노드가 들어있는 모든 인덱스를 그래프에서 제거하여 재구성해주어야 한다.

#include <iostream>
#include <vector>

#define MAX 51

using namespace std;

int N,K;
int cnt;
vector<int> Graph[MAX];
bool visited[MAX];

void DFS(int start) {
    visited[start] = true;

    if (start==K) return;

    if (Graph[start].empty()) {
        cnt++;
        return;
    }

    for (int i=0; i<Graph[start].size(); i++) {
        int idx = Graph[start][i];

        if (idx==K) continue;

        if (!visited[idx]) {
            DFS(idx);
        }
    }
}

int main() {
    cin.tie();
    cout.tie();
    ios::sync_with_stdio(false);

    int root;
    cin >> N;
    for (int i=0; i<N; i++) {
        int a;
        cin >> a;

        if (a==-1) {
            root = i;
            continue;
        }
        
        Graph[a].push_back(i);
    }

    cin >> K;

    Graph[K].clear();
    for (int i=0; i<N; i++) {
        for (int j=0; j<Graph[i].size(); j++) {
            if (Graph[i][j] == K)
                Graph[i].erase(Graph[i].begin() + j);
        }
    }

    DFS(root);
    cout << cnt << '\n';

    return 0;
}

 

혹시나 다른 방법이 될까 싶어 하나 더 제출해봤는데, 그건 안되는걸로...