[c++][백준 22856][그래프탐색] 트리 순회 - 컴도리돌이

---

 

22856번: 트리 순회

---

풀이 과정

해당 문제는 중회 순회를 하면서 이동 횟수를 출력을 해야 한다. 그래서 기본 적인 중회 순회 알고리즘에서 전체 이동 횟수 * 2에서 루트 노드에서 오른쪽 노드의 이동 횟수를 뺀 값을 출력하면 된다.

 

문제는 map 함수를 이용해서 부모 노드가 갖고 있는 자식 노드를 pair<int, int>를 사용해서 왼쪽 자식 노드, 오른쪽 자식 노드를 표현하였다.

 

탐색 함수 dfs(int, bool)

 

탐색을 할 때는 루프 노드부터 시작하고, 해당 노드의 값이 -1일 경우 반환시킨다. 탐색이 시작되면 전체 이동 횟수를 증가시키고 왼쪽 노드를 탐색한다. 여기서 중요한 것은 탐색할 때 bool형 인자 값도 전달시키는데 루트 노드에서 왼쪽 노드를 탐색할 때는 bool값을 false로 설정하여서 왼쪽 노드 탐색에서는 오른쪽 노드의 이동 횟수를 빼는 것을 배제시켰다. 루트에서 왼쪽 자식 노드 탐색이 끝났으면 오른쪽 자식 노드를 탐색을 한다. 해당 값부터는 오른쪽 자식 노드를 탐색할 때마다 후에 뺄 값을 증가시킨다. 

---

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>

using namespace std;

int n,a=-1,r=-1;

map<int,pair<int,int>> relation;

void input(){
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> n;
    for(int i=0,a,b,c; i<n; i++){
        cin >> a >> b >> c;
        relation[a].first = b;
        relation[a].second = c;
    }
}

void travel(int cur,bool flag){
    if(cur == -1) return;

    a ++,travel(relation[cur].first,0);

    if(flag) r++,travel(relation[cur].second,1);
    else travel(relation[cur].second,0);
}
void solution(){

    input();
    travel(1,1);
    cout << 2* a - r;
}

int main(){
    solution();
    return 0;
}

---

---