Algo 03 - 탐색 알고리즘 - 1 DAG

탐색 알고리즘 - 1 DAG

난이도 별 3개?

탐색 알고리즘 -0 선행 개념 에서 DAG에 대한 개념을 설명 했다.

여기서 다시 요약해서 말하자면

DAG은 tree를 포함하는 개념으로 위상이라는 다시 말해 순서가 있는 그래프 이다.

DAG에 관한 문제를 풀어보며 어떤 특이 점이 DAG이라고 하는지 확인 해보자.

문제 풀이

문제 : https://www.acmicpc.net/problem/2623

문제 설명

문제의 예를 문제에 적용해서 설명 하자면

1->4->3, 6->2->5->4, 2->3 처럼 순서가 정해져 있을 때 어떤 순서 규칙도 깨지 않고 이를 일렬로 정렬 가능 하냐는 문제이다.

전 포스트 글을 빌려 설명을 하자면

각 노드(1~6)들에 대해서 부모의 개수와 내가 가리키는 자식을 가리키도록 하는 구조로 문제를 만들으면 편하다.

위상 정렬은 주어진 순서 조건만 맞으면 다수의 정답이 될 수도 있다.

하지만 주어진 순서대로 성립이 안될 수도 있는 경우도 존재한다. (그러면 문제가 되니 미리 DAG을 통해서 확인하자!)

왜 이런 구조를 생성 해야 하는지 설명 하자면..

풀이

1. 임이의 상태에서 출력 할 수 있는 노드들은 부모가 없거나 부모가 모두 사용된 노드이다. 이를 체크 하기 위해서 부모의 수를 체크하는 기능이 필요하다.

2. x라는 숫자가 부모 수 가 0 혹은 모두 체크 되어서 출력된다면 x의 자식들에게 부모 x는 체크 됨을 알려야 한다.

이를 가능케 하려는 로직을 발전하는 순서대로 설명 하자면

1. 우선 노드 자신의 자식을 표시 하는 기능을 생성 한다.

myChild[6][6] : mychild[1][4] = mychild[4][3] = 1;

노드는 자기의 부모를 체크하는 배열을 가지게 한다.

myParent[6][6] : myParent[4][1] = myParent[3][4] =1;

위의 두배열은 사실 하나만 만들어도 된다는 것을 알 수 있다. 첫번재와 두번재 인자를 바꿔서 검색하면 다른 배열의 값을 나타 내게 됨으로.

• myParent[][] 배열 삭제

2. 나의 부모 수 측정

조금 생각 해보면 매번 내 부모가 이미 나갔는지 1~6을 다 도는 행위 보다 나의 부모가 몇명인지만 측정해도 문제가 없다는 것을 알 수 있다.

• int myParent[node]

Code

``` c++

#include 

``` 

이런식으로 md 형식으로 올리는데 자꾸 그냥 텍스트 형식으로 들어가서 사진 첨부 합니다..

해결 방안 아시면 알려주세요 ㅜ.ㅜ

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N, M;
queue<int> qu;
vector<vector<int>> myChild(1001); //2차원 배열 N*N을 만드는 것보다 벡터를 이용해서 만들면 공간 절약 된다.
int myParent[1001]; // 부모 수 cnt

int ans[1001];
int main(){
    scanf("%d %d", &N, &M);
    
    int ex, cur, tc;
    
    for(int i =0; i<M; i++){
        scanf("%d", &tc);
        ex = 0;
        for(int j =0; j<tc; j++){
            scanf("%d",&cur);
            if(ex!=0){
                myParent[cur]++;
                myChild[ex].push_back(cur);
            }
            ex = cur;
        }
    }
    
    for(int i=1; i<=N; i++){
        if(myParent[i]==0){
            qu.push(i); // 혹시 위에서 나오지 않은 부모가 없는 수를 큐에 추가
        }
    }
    
    vector<int> ans;
    
    while(!qu.empty()){
        cur = qu.front();
        qu.pop();
        ans.push_back(cur);
        for(auto nxt : myChild[cur]){ //nxt = 자신의 모든 자식들을 순회한다.
            if(--myParent[nxt]==0){ // 자식의 부모 수가 0이면 큐에 집어 넣는다.
                qu.push(nxt);
            }
        }
    }
    if(ans.size()!=N){
        printf("0");
        return 0;
    } else{
        for(int i=0; i<N; i++){
            printf("%d\n", ans[i]);
        }
    }
    
    return 0;

정리

DAG(위상 정력)의 특징을 제대로 이해 하고 응용 되서 말이 바뀌더라도 바로 알아 볼 수 있는 안목을 기르는게 중요하다.

• 순서 조건, 답이 여러개

중복되게 저장하지 않고 풀이에 알맞는 구조화 시키는 연습이 중요하다고 생각한다.