[SWEA] 1267 작업순서

출처: SWEA

Approach

선행 조건이 있으면 사이클이 존재하지 않는다고 명시되어 있다.

이는 위상정렬을 구현하는 문제이다.

위상정렬 (Topological sort) 

위상정렬 (Topological sort)

 

코드에서는 DFS할 때, 후속 작업이면서 아직 방문하지 않은 정점을 DFS 탐색하고

아직 처리되지 않은 선행 정점(작업)이 존재하는 경우 분기한정 처리하였다.

DFS (depth-first search, 깊이 우선 탐색) 

깊이 우선 탐색(depth-first search, DFS)

 

그래프 구조를 인접행렬로 간단히 표현하였다.

그래프  정의 및 구현 방식 (인접 행렬 & 인접 리스트) 

그래프 정의 및 구현 방식 (인접 행렬 & 인접 리스트)

---

#include <stdio.h>

const int MAX_V = 1e3 + 5;
int vertex, edge, from, to;
bool map[MAX_V][MAX_V];
int visited[MAX_V];

void init()
{
    for (int i = 0; i <= MAX_V; i++)
    {
        visited[i] = 0;
        for (int j = 0; j <= MAX_V; j++)
        {
            map[i][j] = 0;
        }
    }
}

void DFS(int v)
{
    // 이미 방문한 경우
    if (visited[v]) return;
    for (int i = 1; i <= vertex; ++i)
    {
        // 선행 정점들이, 아직 처리(방문)하지 않은 경우
        // 모든 선행 노드가 처리되어 있어야 한다.
        if (!visited[i] && map[i][v] == 1) return;
    }
    // 방문 표시
    visited[v] = 1;
    printf("%d ", v);
    // 현재 노드 v에서 연결된 다른 노드 탐색
    for (int i = 1; i <= vertex; i++)
    {
        // 아직 방문하지 않으면서 후행 노드인 경우
        if (!visited[i] && map[v][i] == 1)
        {
            DFS(i);
        }
    }
}

int main()
{
    // freopen("input.txt", "r", stdin);
    for (int tc = 1; tc <= 10; tc++)
    {
        init(); // 각 TC 초기화
        scanf("%d %d", &vertex, &edge); // 정점, 간선 개수
        for (int i = 0; i < edge; i++)
        {
            scanf("%d %d", &from, &to); // from -> to
            map[from][to] = 1; // 간선 표시 (인접 행렬)
        }
        // 정답 출력
        printf("#%d ", tc);
        for (int i = 1; i <= vertex; i++)
        {
            if (!visited[i]) DFS(i);
        }
        printf("\n");
    }
    return 0;
}