1267번 작업순서

※ 이 글의 모든 문제와 사진, 자료 등은 SW Expert Academy에 있음을 말씀드립니다.

문제 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18TrIqIwUCFAZN

풀이 : https://www.swexpertacademy.com/main/learn/course/lectureVideoPlayer.do

처음에 아무런 생각없이 단순히 DFS로 방문한 정점부터 출력하는 줄 알았는데 그게 아니었다.

예를 들어, 아래와 같은 노드들이 있다고 하자.

우리가 원하는 답은

8, 9, 4, 1, 5, 2, 3, 7, 6 이거나 4, 1, 2, 3, 8, 5, 7, 6, 9 이다.

4, 1, 2, 3, 8, 5, 7, 6, 9을 보면 출력 순서를 빨간 색으로 표시했다.

잘 보면, 자식이 없는 노드에서 부모 노드로 거슬러 올라가(파란 색) 출력 순서를 그 부모 노드부터 하고 있음을 알 수 있다.

따라서, 의사 코드는 아래와 같다.

DFS(현재 노드)
{
    while (부모 노드가 없어질 때 까지)
    {
        DFS(부모 노드);
    }
 
    현재 노드 처리(printf)
}

하지만, 예외가 발생할 수 있음을 알 수 있는데, 예를 들어

노드(정점)가 3개 있는데, 1의 오른쪽 자식을 3, 1의 왼쪽 자식을 2라고 하자.

2와 3은 서로 관계가 없다.

이럴 때, DFS(2)가 DFS(1)을 호출하고, DFS(3)이 DFS(1)을 호출하므로, 방문 여부를 통해 중복을 방지해야 한다.

1. [DFS] 4, 1, 2, 3, 8, 5, 7, 6, 9 순서로 출력하는 코드(leaf 노드부터 부모 노드로 올라가는 방식)

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
bool visit[1001] = { false, };
 
int child[1001] = { 0, };
int info[1001][1001] = { 0, };
// info[a][b] : 자식 노드인 a의 부모 수가 b 그리고 그 값 자체가 순서대로 부모
int parent_count[1001] = { 0, }; // 부모 수
 
void DFS(int node)
{
    if (visit[node]) return;
 
    visit[node] = true;
 
    for (int i = 0; i < parent_count[node]; i++) // node의 부모 수 만큼 실행
    {
        DFS(info[node][i]); // 그 node의 부모를 DFS로 실행
    }
 
    printf("%d ", node); 
    // 끝까지 올라갔다가, 그 정상부터 아래로 출력(부모 → 자식)
}
 
int main(void)
{
    for (int tc = 1; tc <= 10; tc++)
    {
        int V = 0, E = 0, p = 0, c = 0;
 
        memset(visit, false, sizeof(visit));
        memset(child, 0, sizeof(child));
        memset(info, 0, sizeof(info));
        memset(parent_count, 0, sizeof(parent_count));
 
        scanf("%d %d", &V, &E);
 
        for (int i = 0; i < E; i++)
        {
            scanf("%d %d", &p, &c);
            // p → c 이므로 p가 부모, c는 자식
 
            child[p]++;
            // p의 자식 수를 검사
            // child[p]가 0이면 p는 leaf 노드이다.(자식 수가 0이므로)
 
            info[c][parent_count[c]++] = p;
            // 자식 기준으로 부모를 추가
            // info[자식 노드][그 자식 노드의 부모 수를 센다. 실행될 수록 1씩 증가] = 그 부모
            // parent_count[c]의 값은 c의 부모 수
        }
 
        printf("#%d ", tc);
 
        for (int i = 1; i <= V; i++)
        {
            if (child[i] == 0 && !visit[i]) // 자식이 없고 방문하지 않았다면
            {
                DFS(i);
            }
        }
    }
 
    return 0;
}

2. [DFS] 8, 9, 4, 1, 5, 2, 3, 7, 6 순서로 출력하는 코드 (루트 노드부터 leaf 노드로 내려가는 방식)

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
bool visit[1001] = { false, };
 
int child[1001] = { 0, };
int info[1001][1001] = { 0, };
int Stack[1001] = { 0, };
int Top;
int parent[1001] = { 0, };
 
void DFS(int node)
{
    if (visit[node]) return;
 
    visit[node] = true;
 
    for (int i = 0; i < child[node]; i++) // node의 자식 수 만큼 실행
    {
        DFS(info[node][i]); // 그 node의 자식을 DFS 실행
    }
 
    Stack[Top++] = node;
    // 맨 처음에 맨 아래 leaf 노드부터 삽입이 되므로,
    // 출력할 때는 역순으로 출력해야한다. Top - 1 ~ 0
}
 
int main(void)
{
    for (int tc = 1; tc <= 10; tc++)
    {
        int V = 0, E = 0, p = 0, c = 0;
 
        memset(visit, false, sizeof(visit));
        memset(child, 0, sizeof(child));
        memset(info, 0, sizeof(info));
        memset(Stack, 0, sizeof(Stack));
        memset(parent, 0, sizeof(parent));
 
        scanf("%d %d", &V, &E);
 
        for (int i = 0; i < E; i++)
        {
            scanf("%d %d", &p, &c);
            // p → c 이므로 p가 부모, c는 자식
 
            info[p][child[p]++] = c;
            parent[c]++; 
            // c의 부모 수 조사
            // child[p]는 p의 자식 수
        }    
 
        Top = 0;
 
        for (int i = 1; i <= V; i++)
        {
            if (parent[i] == 0 && !visit[i]) // 부모가 없고, 방문하지 않았다면
            {
                DFS(i);
            }
        }
 
        printf("#%d ", tc);
 
        for (int i = Top - 1; i >= 0; i--)
        {
            printf("%d ", Stack[i]);
        }
    }
 
    return 0;
}

3. [BFS] 부모 모드가 없는 경우'만' queue에 push 한다.

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
bool visit[1001] = { false, };
 
int child[1001] = { 0, };
int info[1001][1001] = { 0, };
int Stack[1001] = { 0, };
int parent[1001] = { 0, };
 
queue<int> q;
 
int main(void)
{
    for (int tc = 1; tc <= 10; tc++)
    {
        int V = 0, E = 0, p = 0, c = 0;
 
        memset(visit, false, sizeof(visit));
        memset(child, 0, sizeof(child));
        memset(info, 0, sizeof(info));
        memset(Stack, 0, sizeof(Stack));
        memset(parent, 0, sizeof(parent));
 
        scanf("%d %d", &V, &E);
 
        for (int i = 0; i < E; i++)
        {
            scanf("%d %d", &p, &c);
            // p → c 이므로 p가 부모, c는 자식
 
            info[p][child[p]++] = c;
 
            parent[c]++; 
            // c의 부모 수 조사
        }    
 
        for (int i = 1; i <= V; i++)
        {
            if(parent[i] == 0) q.push(i);
        }
 
        printf("#%d ", tc);
 
        while (!q.empty())
        {
            int qSize = q.size();
 
            while (qSize--)
            {
                int here = q.front();
 
                q.pop();
 
                if (visit[here]) continue;
 
                visit[here] = true;
 
                printf("%d ", here);
 
                for (int i = 0; i < child[here]; i++)
                {
                    int ch = info[here][i];
 
                    parent[ch]--;
 
                    if(parent[ch] == 0) q.push(ch);
                    // 부모가 없는 경우에만 push
                }
            }
        }
    }
 
    return 0;
}

위의 풀이에 DFS와 BFS 구현 방식 및 각 단계 별로 그림을 설명해주신다. 

시간이 날 때 마다 꼭 보자.