[C++] 백준 22856 - 트리 순회

문제 이해 단계

---

 

 

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

 

 

이진트리에서 왼쪽노드 -> 자기 -> 오른쪽 노드 순으로
방문하는걸 중위 순회라고 한다.


그래서 원래 중위 순회는 제일 왼쪽 노드에서부터 출발하는데,
여기 문제에선 조금 다르다.

해당 문제에서는 무조건 루트 노드인 1에서 출발한다고 가정하고
이동을 거쳐 중위순회를 흉내 내는 것이다.


이때 움직였던 모든 이동 횟수를 구하는 문제 

 

 

문제 접근 단계

---

 

필요한 정보 찾기

일단 노드 1개의 관점에서 바라보자.
각 노드의 관점에서 몇 가지의 정보가 있을까? 총 4개가 있다.

해당 노드의 번호,
왼쪽 자식 노드의 번호,
오른쪽 자식 노드의 번호,
부모 노드의 번호

그리고 중위순회를 할 때 필요한 정보를 생각해 보자.


중위 순회를 할 때는 왼쪽 노드 -> 가운데 노드 -> 오른쪽 노드로 가기 때문에
현재 중위 순회를 진행하고 있는
노드의 왼쪽 자식 노드, 부모 노드,  오른쪽 자식 노드 번호가 필요하다.


결국 4개 다 필요하단 소리다.
이 정보를 노드마다 다 구해줘야 한다.

그나마 다행인 건 노드의 이름이 정수여서 인덱스로 표현이 가능하다는 것이다.


그래서 문제에서 이진트리라고도 했고 해서
각 노드마다 이진트리를 뜻하는 Node라는 구조체를 만들고,  


"parent [A] = B -> 노드 A의 부모는 B이다."라는 뜻으로 배열을 만들었다.  
간단히 코드를 적어보면 아래와 같다.

struct Node{
    int left;
    int right;
};

    
Node map[N+1];
int parent[N+1];

배열은 N+1만큼 해주는 이유는
인덱스를 0부터가 아닌 1부터 사용하기 위해서이다.

 

 

 

중위 순회 로직

이제 노드에 대해서 정의하는 것을 끝냈으니
다음으로 생각해야 하는 것은 중위 순회를 구현하는 것이다.


위에서 예시로 준 그림으로 생각해 보자.

중위 순회를 할 때 노드가 3개만 있다고 생각해 보자.
그럼 사실 간단하다.


해당 문제에서 중위 순회를 하려면
이런 식으로 해야 한다.

 

 

그냥 이렇게 될 것이다.
복잡해지는 거는 위에 그림처럼 되는 순간인데,
이걸 이렇게 한번 묶어서 생각해 보자.

 

루트 노드 아래 있는 노드를 모두 하나의 노드로 본다면
위에 있는 그림과 같아질 것이다. 


근데 실제로는 아래 노드가 있으니까
그 아래 노드에서 중위순회 작업을 해줘야 한다.


근데 중요한 것은 어차피 하는 작업이 똑같다는 것이다.
원래대로 작업한다면 화살표는 이렇게 된다.

 

노란색 삼각형은 내가 임의로 추가한 건데,
그냥 이것도 이런 식으로 하나의 노드로 보겠다는 것이다.


화살표의 방향을 보면
이 3개의 삼각형에 있는 화살표가
전부 다 비슷하게 움직이는 것을 볼 수가 있다.

차이점은 왼쪽 노드인데,
그냥 오른쪽 자식 노드에서 올라오는 것
하나 추가된 것뿐 달라진 건 없다.


여기서 끝 노드에 자식들이 추가돼도
똑같은 삼각형을 만들면 된다.

자기 자신과 자식 노드를 묶어서 보면
모두 3개의 노드이기 때문에
3개의 노드에 대한 중위순회처리만 해서
재귀호출해 주면 모든 노드에 대한 처리가 가능해진다.


이는 구현문제 겸 재귀함수 문제이기 때문에
글을 읽는 것보다는 코드를 보는 게 훨씬 더 도움이 될 것이다.

 

중위순회 종료 시점

하나 고려해줘야 할 점은 이 재귀함수를 끝낼 시점인데,
이 중위순회가 끝났다는 걸 어떻게 알 수 있을까?


바로 가장 오른쪽에 있는 노드를 방문했을 때라고 할 수 있다.


오른쪽 노드는 마지막에 방문하기 때문에
가장 오른쪽에 있는 노드에 방문했다는 것은
중위순회가 끝났다는 것을 의미한다.

한 가지 주의해줘야 할 점은
가장 오른쪽 노드가 한 재귀함수의 가운데 노드가 될 때이다. 


그림으로 보면 이렇다.

 

해당 상태에서는
오른쪽 노드로 이동하면서 바로 방문해 버린다.


그래서 이동이 1로 끝나버리는데,
사실 답은 3이 나와야 한다.


그래서 마지막 노드에 도달했을 때
해당 노드의 자식들을
모두 방문한 상태여야 한다는 조건을 추가해야 한다.

 

 

 

 

문제 구현 단계

---

struct Node{
    int left;
    int right;
};

    
Node map[100001]; // 각 노드
int parent[100001]; // 각 노드의 부모 정보
bool visited[100001]; // 노드 방문 확인
int ans = 0;
int N;
int endIdx; // 마지막 노드의 번호
bool endFlag = false; // 재귀함수를 끝내는 플래그


// 가장 오른쪽에 있는 노드의 번호를 찾음
int findEnd(int top){
    if(map[top].right == -1) return top;
    return findEnd(map[top].right);
}

 

위 코드는 기본적인 정의 부분과
끝나는 노드인 가장 오른쪽 노드를 찾는 함수이다.
인자로 루트 노드를 받는다.


방문했던 자식 노드를 다시 방문하지 않기 위해
visited이라는 배열로 방문을 확인하고,
마지막 노드를 방문했을 때 재귀함수를 끝내기 위해
endFlag라는 것을 만들어 재귀함수가 진행되지 못하게 한다.

 

 

// 중위 순회 재귀함수
void solution(int x,bool first){
    if(endFlag) return;
    
    // 왼쪽 자식 노드가 없거나 방문하지 않으면 해당 노드 재귀X
    if(map[x].left != -1 && !visited[map[x].left]){
        ans++;
        solution(map[x].left,false);
    }
    if(endFlag) return;
    // 오른쪽 자식 노드가 없거나 방문하지 않으면 해당 노드 재귀X
    if(map[x].right != -1 && !visited[map[x].right]){
        ans++;
        solution(map[x].right,false);
    }
    if(endFlag) return;
    
    // 해당 노드가 마지막 노드임을 체크
    if(x == endIdx) {
        endFlag = true;
        return;
    }
    // 해당 노드가 루트 노드가 아니면 이동횟수 +1
    if(!first) ans++;
    visited[x] = true;

}

중위순회를 돌리는 solution 함수이다.


매개변수로 해당 노드의 번호와,
루트 노드인지 확인하는 first가 들어온다.

함수 코드 자체는 간단하다.


자식이 없음을 뜻하는 -1이나
해당 자식을 이미 방문한 게 아니면, 그 번호로 재귀를 호출한다.


그리고 왼쪽노드, 오른쪽노드 재귀함수 호출 뒤에는
x == endIdx로 해당 노드가 마지막 노드인지를 확인하는데


재귀함수 호출 뒤에 두는 이유는,
해당 시점에서는 이미 왼쪽과 오른쪽의 방문이 끝난 상태이다.


그래서 이때 노드가 마지막 노드라면
이미 다녀올 곳은 다 다녀왔기 때문에 끝내도 된다.

그리고 마지막에 first는
원래 재귀함수가 끝나고 부모로 돌아갈 때도
이동으로 치기 때문에 이동 횟수를 더해준다.


그런데 루트 노드는 부모가 없기 때문에
재귀가 끝나도 이동 횟수를 더해주면 안 되기 때문에 구분해 줬다.

아래는 전체 코드인데,
전체 코드에서 parent 배열에 각 노드를 연결하는 것만
유의 깊게 보고 마무리하면 될 것 같다.

#include <iostream>
using namespace std;

struct Node{
    int left;
    int right;
};

    
Node map[100001]; // 각 노드
int parent[100001]; // 각 노드의 부모 정보
bool visited[100001]; // 노드 방문 확인
int ans = 0;
int N;
int endIdx; // 마지막 노드의 번호
bool endFlag = false; // 재귀함수를 끝내는 플래그


// 가장 오른쪽에 있는 노드의 번호를 찾음
int findEnd(int top){
    if(map[top].right == -1) return top;
    return findEnd(map[top].right);
}

// 중위 순회 재귀함수
void solution(int x,bool first){
    if(endFlag) return;
    
    // 왼쪽 자식 노드가 없거나 방문하지 않으면 해당 노드 재귀X
    if(map[x].left != -1 && !visited[map[x].left]){
        ans++;
        solution(map[x].left,false);
    }
    if(endFlag) return;
    // 오른쪽 자식 노드가 없거나 방문하지 않으면 해당 노드 재귀X
    if(map[x].right != -1 && !visited[map[x].right]){
        ans++;
        solution(map[x].right,false);
    }
    if(endFlag) return;
    
    // 해당 노드가 마지막 노드임을 체크
    if(x == endIdx) {
        endFlag = true;
        return;
    }
    // 해당 노드가 루트 노드가 아니면 이동횟수 +1
    if(!first) ans++;
    visited[x] = true;

}

int main(){
    scanf("%d",&N);
    for(int i = 0; i < N; i++){
    	// 왼쪽 자식 노드, 오른쪽 자식 노드, 자기 자신
        int left,right,cnt;
        scanf("%d %d %d",&cnt,&left,&right);
        // 왼쪽 자식 노드가 존재하면 자기 자신을 왼쪽 자식 노드 부모로 설정
        if(left != -1)parent[left] = cnt;
        
        // 오른쪽 자식 노드가 존재하면 자기 자신을 오른쪽 자식 노드 부모로 설정
        if(right != -1)parent[right] = cnt;
        map[cnt] = {cnt,left,right};
    }
    endIdx = findEnd(1);
    solution(1,true);
    if(N == 1) cout << "0";
    else printf("%d",ans);
}

 

 

시행착오

---

트리 순회를 직접 구현하는 문제를 풀어보는 건 처음인 것 같은데,
자료구조를 공부하면서 비슷한 구조를 봐서
 아이디어는 쉽게 떠올린 것 같다.


근데 역시 문제는 구현이었는데,
내가 짠 로직에서 예외적인 부분을 찾는 게 어려웠다.

게다가 루트 노드가 무조건 1이라는 조건을 못 봐서
루트 노드를 찾는 함수까지 구현했었다..


중위순회 종료 시점에서 말했던
오른쪽 노드 문제를 몰랐어서 한 3시간 헤맨 것 같다.


역시 예외 처리가 난 어려운 것 같다.

4시간이면 그래도 빠른 건가?
근데 골드 4인데 1시간 안엔 풀어야 하지 않을까?