트리를 이용한 알고리즘 문제풀이

트리 - hello70825.tistory.com/163

트리의 순회 - (작성중)

트리를 이용한 알고리즘 문제풀이 - hello70825.tistory.com/164

 

 

 

 

문제를 미리 풀고 봐주세요

================================================================

 

문제 구성

 

1. 트리 순회(www.acmicpc.net/problem/1991)

2. 트리의 부모 찾기(www.acmicpc.net/problem/11725)

3. 트리(4803)(www.acmicpc.net/problem/4803)

4. 트리(1068)(www.acmicpc.net/problem/1068)

5. 트리의 높이와 너비(www.acmicpc.net/problem/2250)
6. 트리(4256)(www.acmicpc.net/problem/4256)

7. 트리의 순회(www.acmicpc.net/problem/2263)

8. 양 구출 작전(www.acmicpc.net/problem/16437)

9. 사회망 서비스(SNS)(www.acmicpc.net/problem/2263)

 

 

 

문제 모음 출처: blog.naver.com/kks227/220788265724 일부분 + 1문제 추가함

================================================================

 

 

 

 

1. 트리 순회 - www.acmicpc.net/problem/1991

 

 

트리의 종류는 이진트리, A노드가 항상 루트노드가 되고, 각각 노드를 연결한 후에 전위 순회, 중위 순회, 후위 순회를 출력하면 되는 기초적인 문제입니다.

 

이진트리이므로 벡터가 lc(left_children), rc(right_children) 2개를 만들고, 입력이 알파벳이므로 아스키코드를 이용하여 벡터에 넣어줍니다.

 

그리고 트리에 써먹는 함수는 lc, rc에 자식 노드를 넣어주는 함수(add_sub_tree)과 각각의 순회를 출력하는 함수(preorder, inorder, postorder) 총 4가지로 만들 수 있습니다.

 

입력을 받을 때는 A의 아스키 코드가 65이므로 입력 받는 변수에 65를 빼주면 0부터 시작합니다.

그리고 출력을 할 때는 65만큼 더해주고 char형으로 바꿔줘야합니다.

 

#include <bits/stdc++.h>
using namespace std;
 
class Tree{
private:
    int N;
    vector<int> lc;
    vector<int> rc;
public:
    Tree(): N(0){}
    Tree(int n): N(n){
        lc.resize(n,-1);
        rc.resize(n,-1);
    }
    void add_sub_tree(int p, int l, int r){
        if(l>0) lc[p] = l;
        if(r>0) rc[p] = r;
    }
    void preorder(int x){
        cout << (char)(x+65);
        if(lc[x] != -1) preorder(lc[x]);
        if(rc[x] != -1) preorder(rc[x]);
    }
    void inorder(int x){
        if(lc[x] != -1) inorder(lc[x]);
        cout << (char)(x+65);
        if(rc[x] != -1) inorder(rc[x]);
    }
    void postorder(int x){
        if(lc[x] != -1) postorder(lc[x]);
        if(rc[x] != -1) postorder(rc[x]);
        cout << (char)(x+65);
    }
};
 
int main(){
    int n;
    char x, y, z;
 
    cin >> n;
    Tree T(n);
    for(int i=0; i<n; i++){
        cin >> x >> y >> z;
        T.add_sub_tree(x-65,y-65,z-65);
    }
 
    T.preorder(0);
    cout << endl;
    T.inorder(0);
    cout << endl;
    T.postorder(0);
 
    return 0;
}

 

 

 

 

 

2. 트리의 부모 찾기 - www.acmicpc.net/problem/11725

 

 

루트 노드의 번호가 1이고, 1번을 제외한 각 노드의 부모 노드의 번호를 출력하는 문제입니다.

 

1번 문제와 다르게 fast io를 사용해야합니다.

main함수 바로 아래에 아래 사진과 같은 내용을 입력하고, endl대신 "\n"을 사용하면 됩니다.

 

여기서는 자식노드의 번호를 저장해두는 벡터없이 입력 값으로 받은 각 노드의 연결만을 사용하여 parent 벡터에만 값을 넣어주면 됩니다.

parent에 값을 넣어줄때는 BFS나 DFS를 사용하여 각 노드의 부모노드가 누구인지 메모를 해주면 됩니다.

 

1번 코드는 class를 이용하여 트리를 구현하고, 부모노드 기록은 BFS를 사용하였습니다.

2번 코드는 DFS 함수만을 사용하여 부모노드를 기록하고 문제를 풀었습니다.

여기 글에서는 1번 코드처럼 class로 풀은 문제도 있고, 2번 코드처럼 class없이 간단하게 풀은 코드도 있습니다.

 

1번 코드

#include <bits/stdc++.h>
using namespace std;
 
class Tree{
private:
    int N;
    vector<int> parent;
    vector<vector<int>> adj;
    vector<bool> visited;
public:
    Tree(): N(0){}
    Tree(int n): N(n){
        parent.resize(N,-1);
        adj.resize(N);
        visited.resize(N,false);
    }
    void connect_node(int x, int y){
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    void find_parent(){
        queue<int> q;
        q.push(0);
        visited[0] = true;
        while(!q.empty()){
            int x = q.front(); q.pop();
            for(int nx: adj[x]){
                if(!visited[nx]){
                    visited[nx] = true;
                    q.push(nx);
                    parent[nx] = x;
                }
            }
        }
    }
    void print(int x){
        printf("%d\n",parent[x]+1);
    }
};
 
int main(){
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    int n,x,y;
 
    cin >> n;
    Tree T(n);
 
    for(int i=0; i<n-1; i++){
        cin >> x >> y;
        T.connect_node(x-1,y-1);
    }
    T.find_parent();
    for(int i=1; i<n; i++) T.print(i);
 
    return 0;
}
 

2번 코드

#include <bits/stdc++.h>
using namespace std;
 
vector<int> parent;
vector<vector<int>> adj;
 
void DFS(int x, int prev){
    for(auto nx: adj[x]){
        if(parent[nx] == -1 && nx!=prev){
            parent[nx] = x;
            DFS(nx,x);
        }
    }
}
 
int main(){
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    int n,x,y;
    cin >> n;
 
    parent.resize(n, -1);
    adj.resize(n);
 
    for(int i=1; i<n; i++){
        cin >> x >> y;
        x--;y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
 
    DFS(0,-1);
 
    for(int i=1; i<n; i++){
        cout << parent[i] + 1 << "\n";
    }
}

 

 

 

 

 

 

3. 트리 - www.acmicpc.net/problem/4803

 

예제를 그려보면서 문제를 이해하면 좋습니다.

 

예제의 입력은 위 사진과 같이 3가지로 나눠지므로 각각 따로따로 그림을 그려보겠습니다.

1번 입력을 그림으로 그려보면 {1,2,3,4}, {5}, {6}으로 트리는 총 3개가 있다는 것을 알 수 있습니다.

 

2번 입력은 하나로 전부 연결되어 있어서 트리는 딱 하나만 있다는 것을 알 수 있습니다.

 

3번 입력은 {1,2,3}, {4,5,6} 두 개가 있지만 2개 전부 싸이클을 돌 수 있기 때문에 트리가 아니므로 트리가 없습니다.

 

 

 

위와 같이 트리가 될 수 있는 모든 갯수를 더해주면 되는 문제입니다.

트리가 될 수 있는지 없는지 확인하는 함수를 find_tree함수로 구현을 하였는데요.

 

트리가 있다면 어느 정점을 루트노드로 정해서 만들어도 트리는 만들 수 있으니 for문, BFS, visited배열을 이용하여 BFS로 트리를 만들어주고, visited함수로 방문했다는 것을 기록합니다. 여기에 추가로 싸이클을 확인하기 위해 노드끼리 연결되어 있는 것을 끊어주면서 BFS를 돌립니다.(DFS로 만들어도 됩니다.)

 

만약 BFS를 돌리다가 visited = 1인 좌표를 만나면 이것은 싸이클이 있다는 것이므로 return 0을 ans += 0이 되도록 만들어줍니다.(바로 return 0을 하면 아직 연결그래프에서 덜 탐색한 부분이 있겠지만 어차피 그 부분도 다시 탐색하게되면 visited = 1인 노드를 만나게 되므로 상관없습니다.)

 

하지만 BFS를 끝까지 돌릴 수 있다면 이것은 트리라는 것이므로 return 1을 하여 ans에 1을 더합니다.

 

이렇게하여 입력 결과에 ans를 출력하면 됩니다.

노드를 연결할 때 vector를 사용하다가 이번엔 n의 수가 작아서 인접리스트를 이용해 만들었습니다.

 

쉬운 문제지만 정답률이 낮은 이유가 출력하는 부분에 알파벳 소문자/대문자, 점(.)을 추가하는 부분을 실수해서 틀린 사람이 많을 것 같습니다.

#include <bits/stdc++.h>
using namespace std;
 
class Tree{
public:
    int N;
    vector<int> visited;
    int adj[500][500] = {0};
 
    Tree():N(0){}
    Tree(int n):N(n){
        visited.resize(N,0);
    }
    void connect_node(int x, int y){
        adj[x][y] = 1;
        adj[y][x] = 1;
    }
    int find_tree(int a){
        queue<int> q;
        q.push(a);
        visited[a] = 1;
        while(!q.empty()){
            int x = q.front(); q.pop();
            for(int i=0; i<N; i++){
                if(adj[x][i]){
                    if(visited[i] > 0) return 0;
                    adj[x][i] = 0; adj[i][x] = 0;
                    q.push(i);
                    visited[i] = 1;
                }
            }
        }
        return 1;
    }
};
 
int main(){
    int n,m,a,b,z=1;
    while(1) {
        cin >> n >> m;
        if(n==0 && m==0) break;
 
        Tree T(n);
        for(int i=0; i<m; i++){
            cin >> a >> b;
            T.connect_node(a-1,b-1);
        }
        int ans = 0;
        for(int i=0; i<n; i++){
            if(!T.visited[i]) ans+=T.find_tree(i);
        }
 
        cout << "Case " << z <<": ";
        if(ans==0) cout << "No trees.";
        else if(ans==1) cout << "There is one tree.";
        else cout << "A forest of " << ans << " trees.";
        cout << endl;
        z++;
    }
}

 

 

4. 트리 - www.acmicpc.net/problem/1068

 

 

트리의 삭제를 구현하고, 리프노드의 개수를 구하면 통과하는 간단한 문제입니다.

N의 최대값이 50이므로 인접리스트로 충분히 풀 수 있는 문제입니다.

 

코드에 구현한 함수가 좀 많습니다.

• find_root : 입력에서 -1인 부분이 루트 노드이므로 값을 입력받다가 -1이 나오면 그때 루트 노드의 변수를 지정해줘야합니다.
• connect_node : adj 벡터에 번호를 추가하여 노드를 서로 연결시켜줍니다.

• make_tree : 트리를 만들어줍니다.(필자는 BFS를 사용하여 구현)

• leaf : 리프노드의 개수를 구하는 함수입니다.
• erase : 노드를 삭제하는 함수입니다.

이걸 다 합치면 아래와 같은 코드가 나옵니다.

 

#include <bits/stdc++.h>
using namespace std;
 
class Tree{
private:
    int N;
    vector<int> parent;
    vector<vector<int>> children;
    vector<vector<int>> adj;
    vector<bool> visited;
public:
    int root;
    int val = 0;
 
    Tree():N(0){}
    Tree(int n):N(n){
        parent.resize(n,-1);
        children.resize(n);
        adj.resize(n);
        visited.resize(n,false);
    }
 
    void find_root(int x){
        root = x;
    }
 
    void connect_node(int x, int y){
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
 
    void make_tree(){
        queue<int> q;
        q.push(root);
        visited[root] = true;
        while(!q.empty()){
            int x = q.front(); q.pop();
            for(auto nx: adj[x]){
                if(!visited[nx]){
                    visited[nx] = true;
                    parent[nx] = x;
                    children[x].push_back(nx);
                    q.push(nx);
                }
            }
        }
    }
 
 
    void leaf(int x){
        if(children[x].empty()){
            val++;
        }
        else{
            for(auto nx:children[x]){
                leaf(nx);
            }
        }
    }
 
    void erase(int x){
        int p = parent[x];
        for(auto nx: children[p]){
            if(nx==x){
                children[p].erase(remove(children[p].begin(),children[p].end(),x), children[p].end());
                return;
            }
        }
    }
};
 
int main(){
    int n,m,l;
    cin >> n;
 
    Tree T(n);
    for(int i=0; i<n; i++){
        cin >> m;
        if(m==-1) T.find_root(i);
        else T.connect_node(i,m);
    }
    T.make_tree();
 
    cin >> l;
    if(l == T.root){
        cout << 0 << endl;
        return 0;
    }
    T.erase(l);
 
    T.leaf(T.root);
 
    cout << T.val;
 
}

 

 

 

5. 트리의 높이와 너비 - www.acmicpc.net/problem/2250

 

문제에 나와있는 그림을 보면 번호를 매겨진 순서가 중위 순회인 것을 알 수 있습니다.

그리고 너비를 구할 때는 레벨 순회를 이용하여 너비의 최대값을 구할 수 있다는 것을 캐치하였으면 이제 구현하는 것만 남았습니다.

 

함수는 총 5개로 만들었습니다.

• connect_node : 이진 트리이므로 lc, rc, parent에 값을 넣어줍니다.
• find_root : 루트노드의 번호가 무조건 1이라는 보장이 없습니다. 입력에서 주어지는 그래프는 무조건 트리이므로 정점 아무거나 인자로 넣어서 DFS를 이용해 부모노드의 번호가 기록되어 있지 않은 노드까지 거슬러 올라가서, 그 번호를 루트노드로 지정해줍니다.
• set_level : 루트노드를 찾았으니 레벨 순회를 이용하여 각 노드에 격자의 행의 위치를 부여해주면 됩니다.
• set_pos : 중위 순회를 이용하여 각 노드에 격자의 열의 위치를 부여해줍니다.
• find_max : level과 pos를 정해주었으니 이제 레벨 순회를 하여 너비가 가장 넓은 레벨과 그 너비를 찾아 출력을 합니다.

find_max함수를 구현할 때는 배열 2칸을 만들어서 같은 level인 노드를 for문으로 돌려 [열의 최소값, 열의 최대값]을 구하도록 만들었습니다.

 

#include <bits/stdc++.h>
using namespace std;
 
class Tree{
private:
    int N, pos=1;
    vector<int> lc;
    vector<int> rc;
    vector<int> level;
    vector<int> position;
public:
    int root;
 
    Tree():N(0){}
    Tree(int n):N(n){
        lc.resize(n,-2);
        rc.resize(n,-2);
        level.resize(n,0);
        position.resize(n,-1);
    }
    void connect_node(int x, int y, int z){
        if(y!=-2){
            lc[x] = y;
            parent[y] = x;
        }
        if(z!=-2){
            rc[x] = z;
            parent[z] = x;
        }
    }
    void find_root(int x){
        if(parent[x] == -1) root = x;
        else find_root(parent[x]);
    }
    void set_level(){
        queue<int> q;
        q.push(root);
        level[root] = 1;
        while(!q.empty()){
            int x = q.front(); q.pop();
            if(lc[x]!=-2){
                level[lc[x]] = level[x]+1;
                q.push(lc[x]);
            }
            if(rc[x]!=-2){
                level[rc[x]] = level[x]+1;
                q.push(rc[x]);
            }
        }
    }
    void set_pos(int x){
        if(lc[x]!=-2) set_pos(lc[x]);
        position[x] = pos; pos+=1;
        if(rc[x]!=-2) set_pos(rc[x]);
    }
    void find_max(){
        queue<int> nq;
        nq.push(root);
        int max_lv = 1, max_dia[2] = {0,0}, lv=2;
        while(1){
            queue<int> q;
            int dia[2] = {10001,-1};
            while(!nq.empty()) {
                int x = nq.front();nq.pop();
                for (auto nx: {lc[x], rc[x]}) {
                    if (nx != -2) {
                        if (position[nx] < dia[0]) dia[0] = position[nx];
                        else if (position[nx] > dia[1]) dia[1] = position[nx];
                        q.push(nx);
                    }
                }
            }
            if (dia[1] - dia[0] > max_dia[1] - max_dia[0]) {
                max_dia[0] = dia[0];
                max_dia[1] = dia[1];
                max_lv = lv;
            }
            if(q.empty()) break;
            nq = q;
            lv+=1;
        }
        cout << max_lv << " " << max_dia[1] - max_dia[0] + 1;
    }
};
 
int main(){
    int n,x,y,z;
    cin >> n;
 
    Tree T(n);
    for(int i=0; i<n; i++){
        cin >> x >> y >> z;
        T.connect_node(x-1,y-1,z-1);
    }
    T.find_root(0);
 
    T.set_level();
    T.set_pos(T.root);
 
    T.find_max();
 
}

 

6. 트리 - www.acmicpc.net/problem/4256

 

전위 순회, 중위 순회, 후위 순회중 순회 2가지를 알고 있다면 트리는 하나로 확정지을 수 있다는 내용을 토대로 풀 수 있는 문제입니다.

 

예시를 통해 설명하는게 편하니 예제1의 두번째 입력으로 설명을 해보겠습니다.

아래 내용이 이해가 안가시면 직접 트리를 그려보면서 확인해보세요.

두번째 줄은 전위 순회이고, 세번째 줄은 중위 순회입니다.

전위 순회는 첫번째 값이 무조건 루트 노드임을 알 수 있습니다.

그리고 중위 순회를 통해 루트노드의 번호의 왼쪽은 왼쪽 서브트리, 오른쪽은 오른쪽 서브트리임을 알 수 있습니다.

 

그리고 중위 순회의 왼쪽이 4개의 숫자를 가지고 있으므로 전위 순회에서 루트노드의 다음 4개의 번호는 오른쪽 서브트리임을 알 수가 있습니다. 그리고 다음 3개의 숫자는 왼쪽 서브트리임을 알 수 있습니다.

그럼 이제 전위순회의 {6, 5, 4, 8}과 {7, 1, 2}를 두 개로 쪼개서 봅니다.

먼저 {6, 5, 4, 8}부터 확인해봅시다.

전위 순회의 첫번째는 노드는 무조건 루트 노드입니다. 그래서 여기서는 6이 루트노드가 됩니다.

그리고 중위 순회에서 루트노드의 왼쪽은 왼쪽 서브트리가 나오고, 오른쪽은 오른쪽 서브트리가 나옵니다.

중위 순회에서 루트노드의 왼쪽은 숫자 하나 밖에 없으므로 전위 순회에서 루트노드 다음 한 칸의 노드는 왼쪽 서브트리임을 알 수 있고, 중위 순회에서 루트노드의 오른쪽은 숫자가 2개 있으므로 전위 순회에서 왼쪽 서브트리를 구한 숫자 다음 두 칸이 오른쪽 서브트리를 구성하는 숫자임을 알 수 있습니다.

여기서 {5}와 {4,8}로 나뉘는데 5는 6의 왼쪽 자식으로 끝납니다. 그러므로 {4,8}만 보면 됩니다.

전위순회에서 맨 앞의 값은 루트노드임을 알 수 있습니다.

그리고 중위순회에서 루트노드의 왼쪽은 왼쪽 서브트리이고, 루트노드의 오른쪽은 오른쪽 서브트리임을 알 수 있습니다. 여기서는 4의 오른쪽이 없으니 오른쪽 서브트리가 없다는 것을 알 수 있습니다.

{6,5,4,8}로 만들어진 트리는 다 보았으므로 이제 {7, 1, 2}로 만들어진 트리를 확인하면 되는데 위에 {6, 5, 4, 8}로 만든 트리를 구할 때 처럼 만들면 됩니다.

 

전위 순회에서 맨 앞의 값인 7은 루트 노드임을 알 수 있고, 이것을 이용하여 중위 순회를 살펴보면 7의 오른쪽 서브트리는 존재하지 않고, {1,2}로 만들어진 왼쪽 서브트리가 있다는 것을 알 수 있습니다.

마지막으로 {1,2}를 확인해봅시다.

전위 순회의 맨 앞의 값인 1은 루트 노드임을 알 수 있고, 1의 왼쪽 서브트리는 존재하지 않고, {2}로 만들어진 오른쪽 서브트리가 있다는 것을 알 수 있습니다.

 

이걸 한 그림으로 전부 담아서 표현하면 아래와 같습니다.

 

 

이렇게 DFS로 문제를 풀면 됩니다.

 

#include <bits/stdc++.h>
using namespace std;
 
int pre[1001],in[1001],lc[1001],rc[1001];
 
void go(int px,int pe, int ix, int ie){
    int root_post = pre[px], root_in = -1;
 
    if(px==pe || px>pe) return;
    for(int i=0; i<=ie-ix; i++){
        if(in[ix+i] == root_post){
            root_in = ix+i;
            break;
        }
    }
 
    if(root_in - ix != 0) lc[root_post] = pre[px+1];
    if(root_in - ie != 0) rc[root_post] = pre[px+(root_in-ix)+1];
 
    go(px+1,px+root_in-ix,ix,root_in-1);
    go(px+root_in-ix+1,pe,root_in+1,ie);
}
 
void print_post(int x){
    if(lc[x]!=-1) print_post(lc[x]);
    if(rc[x]!=-1) print_post(rc[x]);
    cout << x+1 << " ";
}
 
int main(){
    int t;
    cin >> t;
 
    while(t--){
        int n, x;
        cin >> n;
        memset(pre,-1,sizeof(pre));
        memset(in,-1,sizeof(in));
        memset(lc,-1,sizeof(lc));
        memset(rc,-1,sizeof(rc));
 
        for(int i=0; i<n; i++){
            cin >> x;
            pre[i] = x - 1;
        }
        for(int i=0; i<n; i++){
            cin >> x;
            in[i] = x-1;
        }
 
        go(0,n-1, 0,n-1);
        print_post(pre[0]);
        cout << endl;
    }
}

 

 

 

 

7. 트리의 순회 - www.acmicpc.net/problem/2263

 

6번 문제에서는 전위 순회와 중위 순회로 트리를 만든다음 후위 순회를 출력하는 것이였지만, 7번 문제에서는 중위 순회와 후위 순회로 트리를 만든다음 전위 순회를 출력하는 문제입니다.

 

이 문제도 6번에서 사용한 예시의 트리를 이용하여 설명하겠습니다.

먼저 두번째 줄은 중위 순회, 세번째 줄은 후위 순회입니다.

 

후위 순회에서 마지막 노드의 번호는 루트 노드입니다.

그리고 중위 순회에서 루트 노드의 번호의 왼쪽은 왼쪽 서브트리이고, 루트 노드의 번호의 오른쪽은 오른쪽 서브트리인 것을 알 수 있습니다.

 

중위 순회에서 왼쪽 서브트리는 {5, 6, 8 , 4}이므로 후위순회에 적힌 수에서 맨 앞부터 4번째 수까지는 왼쪽 서브트리의 숫자들일 것이고, 5번째 수부터 7번째 수까지는 오른쪽 서브트리의 숫자들일 것입니다.

이러면 여기서 {5, 6, 8, 4}, {1, 2, 7}인 서브트리들이 생기는걸 또 나눠서 구하면 됩니다.

6번 문제랑 똑같습니다.

다 정리하면 아래 사진처럼 한 그림으로 표현이 가능합니다.

이걸 그대로 구현하시면 통과합니다.

 

#include <bits/stdc++.h>
using namespace std;
 
vector<int> lc;
vector<int> rc;
vector<int> in;
vector<int> post;
 
void DFS(int isx, int iex, int psx, int pex){
    if(isx >= iex) return;
    int root = post[pex], in_root, rc_len, lc_len;
 
    for(int i=isx; i<=iex; i++){
        if(in[i] == root){
            in_root = i;
            lc_len = i - isx;
            rc_len = iex - i;
            break;
        }
    }
 
    if(in_root != isx) lc[root] = post[psx + lc_len - 1];
    if(in_root != iex) rc[root] = post[psx + lc_len + rc_len -1];
 
    DFS(isx, in_root-1, psx, psx + lc_len - 1);
    DFS(in_root + 1, iex, psx + lc_len, pex - 1);
}
 
void print_pre(int x){
    cout << x+1 << " ";
    if(lc[x] != -1) print_pre(lc[x]);
    if(rc[x] != -1) print_pre(rc[x]);
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, x;
    cin >> n;
 
    lc.resize(n,-1);
    rc.resize(n,-1);
    in.resize(n);
    post.resize(n);
 
    for(int i=0; i<n; i++){
        cin >> x;
        in[i] = --x;
    }
    for(int i=0; i<n; i++){
        cin >> x;
        post[i] = --x;
    }
 
    DFS(0,n-1,0,n-1);
    print_pre(post[n-1]);
}

 

 

 

 

 

8. 양 구출 작전 - www.acmicpc.net/problem/16437

 

 

문제를 읽어보면 1번 섬이 무조건 루트 노드임을 알 수 있습니다.

 

대충 어떻게 구현해야할지 구상을 해보면 만약 트리가 있을 때, 각각의 리프 노드로부터 거슬러 올라가면서 양이 있을 때는 더해주고, 늑대가 있을 경우엔 그만큼 빼주는데 늑대의 수가 현재 양보다 클 경우 부모노드에는 더해주는 것이 없게 만들어서 최종적으로 루트노드의 값을 바꿔주면 될 것 같습니다.

 

예제 2번을 그림으로 그려서 봐보겠습니다.

 

가장 아래에 있는 7번 섬부터보면 7번 섬에서 6번 섬으로 양 900마리가 가는데 늑대가 1000마리가 있어서 6번 섬엔 양이 0마리 입니다.

5번 섬에 있는 양 1000마리와 6번 섬에 있는 양 0마리가 2번 섬으로 이동합니다.

그러면 2번 섬에 있는 양은 총 1100마리가 됩니다.

 

2번 섬엔 양 1100마리, 3번 섬엔 양 100마리, 4번 섬에는 양 0마리가 1번 섬으로 가서 1번 섬으로 갈 수 있는 양은 총 1200마리가 됩니다.

이걸 DFS로 풀면 됩니다.

 

아래 전체 코드에서는 resque함수에 집중하시면 됩니다.

자식 노드들로 DFS를 하다가 리프노드를 만나면 for문이 작동을 안합니다.

이때 리프노드에서 양이 있으면 value[x] > 0이 될 것이고, 늑대가 있으면 음수로 값을 넣어 value[x] < 0이 나오게 값을 넣었습니다.

 

#include <bits/stdc++.h>
using namespace std;
 
class Tree{
private:
    int N;
    vector<int> parent;
    vector<vector<int>> children;
    vector<vector<int>> adj;
    vector<long long> value;
    vector<bool> visited;
public:
    Tree():N(0){}
    Tree(int n):N(n){
        parent.resize(N,-1);
        children.resize(N);
        adj.resize(N);
        value.resize(N,0);
        visited.resize(N,false);
    }
    void make_land(int a, long long b, int c){
        adj[a].push_back(c);
        adj[c].push_back(a);
        value[a] = b;
    }
 
 
    void make_tree(){
        queue<int> q;
        q.push(0);
        visited[0] = true;
        while(!q.empty()){
            int x = q.front();q.pop();
            for(auto nx: adj[x]){
                if(!visited[nx]){
                    visited[nx] = true;
                    q.push(nx);
                    parent[nx] = x;
                    children[x].push_back(nx);
                }
            }
        }
    }
 
    long long resque(int x){
        for(auto nx: children[x]){
            value[x]+=resque(nx);
        }
        if(value[x] < 0) return 0;
        return value[x];
    }
 
};
 
int main(){
    int n,z;
    long long y;
    char x;
 
    cin >> n;
    Tree T(n);
 
    for(int i=1; i<n; i++){
        cin >> x >> y >> z;
        if(x=='S') T.make_land(i,y,z-1);
        else T.make_land(i,-y,z-1);
    }
 
    T.make_tree();
    
    cout << T.resque(0) << endl;
}

 

 

 

 

9. 사회망 서비스(SNS) - www.acmicpc.net/problem/2533

문제를 읽어보시면 조건이 하나 있습니다.

'얼리 아답터(일반인)가 아닌 사람은 자신의 모든 친구가 얼리 아답터여야 한다.'

근데 얼리 아답터인 경우에는 어떠한 조건이 없습니다.

 

그러면 구현을 3개로 나눌 수가 있어요

1) 부모 노드가 일반인일 때 => 자식 노드는 모두 얼리 아답터이다.

2) 부모 노드가 얼리 아답터일 때 => 자식 노드는 일반인이 될 수 있다.

3) 부모 노드가 얼리 아답터일 때 => 자식 노드는 얼리 아답터가 될 수 있다.

 

이 부분은 DFS로 구현 가능합니다.

 

그런데 이렇게 구현하고 끝내면 시간 초과가 나옵니다.

 

만약 아래 사진과 같은 트리가 있다고 가정합시다.

그리고 루트노드가 얼리 아답터일 때를 가정하고, DFS를 돌려 화살표까지 도착해서 얼리 아답터의 최소값인 k를 얻었다고 합시다. 그림에서 k = 2 겠네요.

 

 

그리고 만약 루트 노드가 얼리 아답터가 아닐때를 가정하고 DFS를 돌리다가 해당 정사각형 부분의 값을 구해야한다고 가정해봅시다.

여기서 단순히 DFS로만 구현해서 짠다면 우리는 이미 k라는 것은 알지만 프로그램은 DFS를 해야하기 때문에 저길 들어가서 k = 2라는 결론을 가져올 것입니다.

이건 너무 비효율적이에요.

 

그래서 저 네모안에 있는 검은색 노드의 번호가 x일 때, x번 노드가 얼리 아답터면 x번 노드가 루트노드인 서브트리에서 얼리 아답터의 최소값이 k인 것을 기록해둡시다. 여기서 메모이제이션이 쓰입니다.

 

x번 노드가 얼리 아답터일 때 혹은 일반인일때 두가지로 나뉘니 arr[x][0], arr[x][1]로 나눠서 저장을 해야겠죠

이러면 만약 어찌저찌해서 다른 방법으로 DFS돌려 x번 노드에 도착하였고, x번 노드가 얼리 아답터일 때 arr[x]에 있는 값을 꺼내어서 바로 최소값이 k임을 알면 시간이 매우 단축될 것입니다.

 

이렇게 배열을 만들어 기록을하고 DFS를 짠다면 코드가 통과됩니다.

 

아래 DFS함수에서 필요한 인자가 3개가 나와있는데요. x는 현재 노드의 번호, ea는 x번 노드가 얼리 아답터인지 확인, prev는 자식 노드를 짜지 않고 풀려고 x번 노드의 부모노드가 누구인지 저장해두었습니다.

여기서 기록을 해두는 배열이 ans입니다. 배열안에 값은 -1로 전부 초기화해두었습니다.

if(ans[x][ea] != -1)은 ans[x][ea]의 값이 -1이 아닌 경우 이미 계산을 했던 서브트리이므로 바로 return ans[x][ea]를 해주면 됩니다.

하지만 배열의 값이 -1이 된다면 최소값을 직접 구해야겠지요.

for문 안 if안에 있는 if-else문을 읽어보시면 x번 노드가 얼리 아답터일 때(ea = 1), 얼리 아답터가 아닐 때로 나누어져 있습니다.

x번 노드가 얼리 아답터일 떄는 자식노드가 얼리 아답터이든 일반인이든 상관이 없지만, 우리는 최소값을 구해야하므로 min함수를 통해 최소값을 저장하게 만듭니다.

하지만 x번 노드가 일반인인 경우 자식 노드는 무조건 얼리 아답터이므로 자식 노드가 루트 노드일 떄의 서브 트리의 최소 얼리 아답터의 수를 더해주면 됩니다.

 

#include <bits/stdc++.h>
using namespace std;
#define MAX 1000001
vector<int> adj[MAX];
int ans[MAX][2];
 
void make_node(int x, int y){
    adj[x].push_back(y);
    adj[y].push_back(x);
}
 
int DFS(int x, int ea, int prev){
    if(ans[x][ea] != -1) return ans[x][ea];
    if(ea) ans[x][ea] = 1;
    else ans[x][ea] = 0;
    for(auto nx: adj[x]){
        if(nx != prev)
        {
            if(ea) ans[x][ea] += min(DFS(nx,0,x),DFS(nx,1,x));
            else ans[x][ea] += DFS(nx,1,x);
        }
    }
    return ans[x][ea];
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n,u,v;
 
    cin >> n;
    for(int i=1; i<n; i++){
        cin >> u >> v;
        make_node(--u,--v);
    }
 
    memset(ans,-1,sizeof(ans));
 
    cout << min(DFS(0,0,-1),DFS(0,1,-1));
}