백준 2233 사과나무

문제

풀이

두 썩은 사과를 잘라내기 위해 가지를 잘라내되, 떨어지는 사과의 개수를 최소로 한다는 것은 두 썩은 사과의 최소 공통 조상을 찾아내라는 의미이다.
즉, LCA 알고리즘을 적용시키면 된다.

단, 이 문제에서는 문자열을 가지고 Tree를 생성하는 과정을 요구하고 있다.

Tree 생성

1) 스택 사용

0인 경우 level이 더 높아지고, 1인 경우 level이 낮아진다.
0으로 진입시 빠져나오는 1이 반드시 존재하므로 stack을 사용한다면 좀 더 쉽게 해결이 가능하다.

2) index 에 따른 node 번호 매핑

이 문제에서는 문자열을 가지고 Tree를 생성해야 하므로
문자열의 index에 따라 해당하는 node 번호를 매핑하는 과정이 필요하다.

3) 부모 node의 정보를 저장

해당 node의 부모 node 정보를 알고 있어야 나중에 LCA 알고리즘을 적용하는 과정에서 부모노드로 타고 올라가며 level을 끌어올리는게 가능하다.

4) level 정보 저장

LCA 알고리즘을 적용하는 과정에서 두 node의 level을 동등한 위치로 맞춰주기 위해 각 node의 level 정보가 필요하므로 각 node 마다 level 정보를 저장하는 과정이 필요하다.

ex) node1이 node2 보다 level이 높다면
level[node1] - level[node2] 만큼 node1의 level을 끌어올려주어야 한다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;
#define SIZE 2005

int parents[SIZE]; // node의 parent 저장
int levelMapping[SIZE]; // node의 level 저장
int mapping[2*SIZE]; // 문자열 index에 해당하는 node 번호 저장

int levelUp(int node,int d) { 
    // 현재 node 에서 d만큼 level을 끌어 올린 후의 node 번호 반환 
    for (int i = 0; i < d; i++) {
        node = parents[node];
    }
    return node;
}

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);


    stack<int> st;
    string s;
    int n, x, y;
    cin >> n >> s;
    cin >> x >> y;


    st.push(0);
    int idx = 0;
    int node = 1;
    int level = 1;
    while (idx != s.size()) {
        if (s[idx] == '0') {
            parents[node] = st.top();
            st.push(node);
            mapping[idx] = node;
            levelMapping[node] = level;

            level++;
            node++;
        }
        else {
            mapping[idx] = st.top();
            st.pop();
            level--;
        }
        idx++;
    }

    int node1 = mapping[x-1]; // x위치에 해당하는 node 번호
    int node2 = mapping[y-1]; // y위치에 해당하는 node 번호    
    int levelDiff = levelMapping[node1] - levelMapping[node2]; // node1, node2의 level 차이

    node1 = levelUp(node1, levelDiff); 
    node2 = levelUp(node2, -levelDiff); 
    // node1, node2의 level 높이 맞추기
    
    while (node1 != node2) {
        node1 = parents[node1];
        node2 = parents[node2];
    } //최소 공통 조상 위치까지 끌어올리기
        
    for (int i = 0; i < s.size(); i++) {
        if (mapping[i] == node1) {
            cout << i + 1 << ' ';
        }
    }
    return 0;
}