| 문제
주어진 그래프가 만약 DAG(Directed Acyclic Graph, 방향성 비사이클 그래프)라면, 그 그래프의 꼭짓점들을 위상 정렬 하는 프로그램을 구현하라. DFS(Depth-First Search, 깊이 우선 탐색) 과정을 진행하는 동안, 작은 숫자의 꼭짓점들을 먼저 방문하도록 설계해야 한다.
입력(표준 입력)
첫 번째 에는 꼭짓점의 개수를 입력한다.
다음 줄부터, 그래프 G의 인접 리스트가 서로 연결되어 있는 꼭짓점인 x와 y로 표현되어야 한다. 이 것은 꼭짓점 x에서 꼭짓점 y로 나아가는 간선이 존재함을 의미한다.
출력(표준 출력)
첫 번째 줄에는, 주어진 그래프 G가 DAG라면 1을 출력하고, 아니면 0을 출력하게 한다.
그리고 그래프가 DAG이면 그 다음 줄에, 위상 순서대로 꼭짓점들을 출력해야 한다.
example)
입력 |
출력 |
9 1 4 1 5 2 5 4 5 4 6 6 9 7 6 7 8 8 9 EOF 입력(윈도우에서는 Ctrl+Z) |
1 7 8 3 2 1 4 6 9 5 |
| 소스 코드
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define TREE_EDGE 1
#define BACK_EDGE 2
#define FORWARD_EDGE 3
#define CROSS_EDGE 4
#define TRUE 1
#define FALSE 0
typedef struct _vertex{
int color;
int f;
int d;
} Vertex;
typedef struct _VertexInfo{
int out_degree;
int * list;
} VertexInfo;
Vertex * vertex;
VertexInfo * vertexInfo;
int numV, time;
int * topoList;
int topo_num=0;
int isDAG = TRUE;
void addEdge(int fromV, int toV){
int i=0;
int cur=0;
for(i=0; i < numV; i++)
{
if(vertexInfo[fromV].list[i] == 0)
break;
cur ++;
}
vertexInfo[fromV].list[cur] = toV;
}
void DFS_Visit(int fromV){
int i=0, toV;
/* DISCOVERED */
time++;
vertex[fromV].color = GRAY;
vertex[fromV].d = time;
for(i=0; i < vertexInfo[fromV].out_degree; i++){
toV = vertexInfo[fromV].list[i];
switch(vertex[toV].color)
{
case WHITE:
DFS_Visit(toV);
break;
case GRAY:
isDAG = FALSE;
break;
case BLACK:
break;
default:
break;
}
}
/* FINISHED */
vertex[fromV].color = BLACK;
topoList[numV-(topo_num++)] = fromV;
time ++;
vertex[fromV].f = time;
}
void Sort(int * list, int num)
{
int i=0, j=0, tmp;
for(i=0; i < num; i++)
{
for(j=i+1; j < num; j++)
{
if(list[i] > list[j])
{
tmp = list[i];
list[i] = list[j];
list[j] = tmp;
}
}
}
}
void DFS(void)
{
int i;
for(i=1; i <=numV; i++)
{
vertex[i].d = 0;
vertex[i].f = 0;
vertex[i].color = WHITE;
Sort(vertexInfo[i].list, vertexInfo[i].out_degree);
}
time = 0;
for(i=1; i <=numV; i++)
{
if(vertex[i].color == WHITE)
{
DFS_Visit(i);
}
}
}
int main(void)
{
int i=0, j=0;
int fromV, toV;
scanf("%d", &numV);
/* INITIALIZATION START! */
vertexInfo = (VertexInfo*)malloc(sizeof(VertexInfo)*(numV+1));
for(i=1; i <=numV; i++){
vertexInfo[i].list = (int*)malloc(sizeof(int)*numV);
vertexInfo[i].out_degree = 0;
}
for(i=1; i <=numV; i++){
for(j=0; j < numV; j++){
vertexInfo[i].list[j] = 0;
}
}
vertex = (Vertex*)malloc(sizeof(Vertex)*(numV+1));
topoList = (int*)malloc(sizeof(int)*(numV+1));
/* INITIALIZATION END! */
// INPUT
while(scanf("%d %d", &fromV, &toV)!=EOF){
addEdge(fromV, toV);
vertexInfo[fromV].out_degree ++;
}
DFS();
// OUTPUT
printf("%d\n", isDAG);
if(isDAG)
{
for(i=1; i <=numV; i++)
printf("%d ", topoList[i]);
}
return 0;
}'컴퓨터 프로그래밍' 카테고리의 다른 글
| 다차원 배열 할당시 '인접한 메모리 할당하기' (0) | 2014.02.20 |
|---|---|
| 배열의 이름은 포인터가 아니다? (0) | 2014.02.16 |
| 알고리즘 - Connected Component (0) | 2014.02.15 |
| 알고리즘 - Priority Queue(우선순위 큐를 구현하라) (0) | 2014.02.15 |
| 알고리즘 - Heap Sort (힙 소트(힙 정렬)를 구현하라) (0) | 2014.02.15 |