이거 푸는사람 천재

프로그래밍 갤러리

1/3

1학년에 여학생이 1명인 대구의 고등학교...jpg 작성자 : 설윤아기

프갤러(222.111) 2024.05.18 01:41:20

조회 84 추천 0 댓글 1

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 10

#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))

typedef struct GraphNode
{
    int vertex;
    struct GraphNode *link;
} GraphNode;

typedef struct GraphType
{
    int n; // 정점의 개수
    GraphNode *adj_list[MAX_VERTICES];
} GraphType;

// 그래프 초기화
void graph_init(GraphType *g)
{
    int v;
    g->n = 0;
    for (v = 0; v < MAX_VERTICES; v++)
        g->adj_list[v] = NULL;
}
// 정점 삽입 연산
void insert_vertex(GraphType *g, int v)
{
    if (((g->n) + 1) > MAX_VERTICES)
    {
        fprintf(stderr, "그래프: 정점의 개수 초과");
        return;
    }
    g->n++;
}
// 간선 삽입 연산, v를 u의 인접 리스트에 삽입한다.
void insert_edge(GraphType *g, int u, int v)
{
    GraphNode *node;
    if (u >= g->n || v >= g->n)
    {
        fprintf(stderr, "그래프: 정점 번호 오류");
        return;
    }
    node = (GraphNode *)malloc(sizeof(GraphNode));
    node->vertex = v;
    node->link = g->adj_list[u];
    g->adj_list[u] = node;
}

GraphType g;
void print_arr(int arr[], int in[], int s, int i, int size)
{
    for (int j = 0; j < g.n; j++)
        printf("%3d", in[j]);
    printf("\n");
    for (int j = 0; j < g.n; j++)
        printf("%3d", arr[j]);
    printf("  - s:%d, i:%d, size:%d\n", s, i, size);
}
void generate(int arr[], int s, int size, int *in)
{
    int i, tmp;
    int in_degree[MAX_VERTICES] = {0};
    for (i = 0; i < g.n; i++) // copy
        in_degree[i] = in[i];

    GraphNode *node = g.adj_list[arr[s]]; // 각 정점의 진입 차수를 변경
    while (node != NULL)
    {
        in_degree[node->vertex]--;
        node = node->link;
    }

    s++;
    if (s == g.n)
    {
        for (i = 0; i < g.n; i++)
            printf("정점%d->", arr[i]);
        printf("\n");
    }
    else
    {
        for (i = s; i < size; i++)
        {
            if (in_degree[arr[i]] == 0)
            {
                SWAP(arr[s], arr[i], tmp);
                generate(arr, s, size, in_degree);
                SWAP(arr[s], arr[i], tmp);
            }
        }
    }
}
// 위상정렬을 수행한다.
void topo_sort()
{
    int i, tmp;
    int arr[MAX_VERTICES], size;
    int in_degree[MAX_VERTICES];

    // 모든 정점의 진입 차수를 계산
    for (i = 0; i < g.n; i++) // 초기화
        in_degree[i] = 0;
    for (i = 0; i < g.n; i++)
    {
        GraphNode *node = g.adj_list[i]; // 정점 i에서 나오는 간선들
        while (node != NULL)
        {
            in_degree[node->vertex]++;
            node = node->link;
        }
    }
    // 진입 차수가 0인 정점을 배열에 삽입
    size = 0;
    for (i = 0; i < g.n; i++)
    {
        if (in_degree[i] == 0)
            arr[size++] = i;
    }
    // 모든 위상 순서를 생성
    for (i = 0; i < size; i++)
    {
        generate(arr, i, size, in_degree);
    }
}

int main(void)
{
    graph_init(&g);
    // 문제에 주어진 그래프에 대한 인접리스트를 완성하시오.
    insert_vertex(&g, 0);
    insert_vertex(&g, 1);
    insert_vertex(&g, 2);
    insert_vertex(&g, 3);
    insert_vertex(&g, 4);
    insert_vertex(&g, 5);

    // 정점 0의 인접 리스트 생성
    insert_edge(&g, 0, 2);
    insert_edge(&g, 0, 3);

    // 정점 1의 인접 리스트 생성
    insert_edge(&g, 1, 3);
    insert_edge(&g, 1, 4);

    // 정점 2의 인접 리스트 생성
    insert_edge(&g, 2, 3);
    insert_edge(&g, 2, 5);

    // 정점 3의 인접 리스트 생성
    insert_edge(&g, 3, 5);

    // 정점 4의 인접 리스트 생성
    insert_edge(&g, 4, 5);

    // 위상 정렬
    topo_sort();
    // 동적 메모리 반환 코드 생략
    return 0;
}
/*실제출력

*/
/*출력예시
정점0->정점1->정점2->정점4->정점3->정점5->
정점0->정점1->정점2->정점3->정점4->정점5->
정점0->정점1->정점4->정점2->정점3->정점5->
정점0->정점2->정점1->정점4->정점3->정점5->
정점0->정점2->정점1->정점3->정점4->정점5->
정점1->정점0->정점4->정점2->정점3->정점5->
정점1->정점0->정점2->정점4->정점3->정점5->
정점1->정점0->정점2->정점3->정점4->정점5->
정점1->정점4->정점0->정점2->정점3->정점5->
계속하려면 아무 키나 누르십시오 . . .
*/

아무리 생각해도 안됨

고정닉 0

전체 댓글 0개

등록순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	제목	글쓴이	작성일	조회	추천
설문	시세차익 부러워 부동산 보는 눈 배우고 싶은 스타는?	운영자	24/05/27	-	-
2705594	AI로 유튜브에 올릴 동영상은 어떻게 만드는 건가요?	☆단비☆	06.01	15	0
2705593	ㅈ같이 돈 모으기 힘들다 ㅅㅂ [6]	ㅇㅇ(118.235)	06.01	65	1
2705592	자바에서 열받는거 한가지. JSON. [1]	프갤러(59.16)	06.01	48	0
2705591	Html 코드 주고 코딩해달라니까 기가막히누	프갤러(39.7)	06.01	27	0
2705590	요즘 최소 3백억은 있어야 사람답개 살수있는듯	♥끙르가즘냥덩♥	06.01	22	0
2705588	연봉 6000 입니다. [2]	프갤러(59.16)	06.01	86	0
2705587	Ai대체되서 해고되고 택배뛰는중 [2]	ㅇㅇ(118.235)	06.01	53	1
2705586	연봉 6천이면 누가봐도 ㅅㅌㅊ임? [1]	ㅇㅇ(220.76)	06.01	33	0
2705584	오오.. 나님 기분 ㄱㅆㄱㅌㅊ !!	♥끙르가즘냥덩♥	06.01	19	0
2705582	근데 진짜 요즘 국비들 개좆소도 취업몬함??? [5]	프갤러(125.128)	06.01	117	0
2705581	50쳐먹은 프리랜서가 리얼돌로봇 가지고 싶다는데	ㅇㅇ(118.235)	06.01	21	0
2705579	클라우드 RX	프갤러(121.172)	06.01	15	0
2705578	ㅈ됐네요 코틀린 이거 왜이런지 아직도 이해못했어 [4]	ㅇㅇ(125.242)	06.01	36	0
2705577	나 왔다-	프갤러(121.172)	06.01	27	0
2705576	야이놈들아 완전 개판이넹 ㅇㅅㅇ	Kat	06.01	20	0
2705575	조현병, ADHD 환자 개 많네 [1]	ㅇㅇ(121.129)	06.01	33	0
2705574	오늘은 m16분해 개잘함	딱지(211.234)	06.01	12	0
2705572	영점 사격할때 [1]	딱지(211.234)	06.01	17	0
2705570	ㅆ발 내 유일한 도파민 삶의 대피구 rx좌가!!!!	ㅇㅇ(223.39)	06.01	21	0
2705569	야비군 1조되면 무조건 조기퇴소 아닌가요? [2]	쇼팬하우어	06.01	22	0
2705567	예비군 조기퇴소하면 집 가서 머 먹지 [7]	딱지(211.234)	06.01	38	0
2705566	메모리 버그 = 돈) 러스트 쓰면 돈 못 벌어요 [6]	☆단비☆	06.01	35	0
2705563	배에서 꼬르륵 소리가.. 어서 빨리..	♥끙르가즘냥덩♥	06.01	16	0
2705562	진짜 개발자는 매일 똑같은 음삭만 먹는다 [4]	♥끙르가즘냥덩♥	06.01	54	0
2705561	교통정리하러옴 [5]	Kat	06.01	44	0
2705559	예비군은 왜 점심시간 2시간이냐 [7]	딱지(211.234)	06.01	38	0
2705558	요즘 추세가 다 래거시 버리는것임 1년만 지나도 바로 구형기기되어버림 [1]	♥끙르가즘냥덩♥	06.01	27	0
2705557	RX학문 이식이 요새 뭐하냐 [4]	130@(117.111)	06.01	30	0
2705556	배달 온 달걀에서 토냄새가 납나다 [5]	쇼팬하우어	06.01	27	0
2705555	27인치 2개 + 22인치 vs. 32인치 1개 -- 뭐가 좋을까? [1]	프갤러(23.240)	06.01	14	0
2705553	맘마 ㅇ	♥끙르가즘냥덩♥	06.01	14	0
2705552	스마트티비 잘 아는사람 있어? [3]	소쿠	06.01	44	0
2705551	러스트 굳이 안써도되는이유 [5]	멍청한유라ㅋ	06.01	162	6
2705550	오늘 야비군 조기퇴소각 노린다 [4]	딱지(211.234)	06.01	25	0
2705548	러스트를 굳이 안 써도 되는 현실적 이유) 메모리 버그 = 돈	☆단비☆	06.01	22	0
2705547	rust 문자열 진짜 이럼?	프갤러(49.165)	06.01	28	0
2705546	개인 비즈니스앱 혼자 하면 좋은 점 [4]	AppHiki	06.01	38	0
2705545	까다로운 취향은 축복인가 저주인가	♥끙르가즘냥덩♥	06.01	14	0
2705544	나님만의 맛집은 ㄹㅇ 나님밖애 모름	♥끙르가즘냥덩♥	06.01	13	0
2705542	50중반까지 어떤 삶을 살아야 할지 말야 [2]	버거띠	06.01	30	0
2705541	나님만의 확고한 취향 철학이 있는자들애겐 특히나	♥끙르가즘냥덩♥	06.01	16	0
2705540	돈이 있어도 모든걸 누릴순 없어	♥끙르가즘냥덩♥	06.01	15	0
2705539	나님 선택장애 미찰것같애	♥끙르가즘냥덩♥	06.01	17	0
2705538	히진씨 처음 회견때 3일 안 씻고 나왔다던데 [4]	쇼팬하우어	06.01	35	0
2705536	옛 어르신 성현들의 조언에 귀를 귀울여라	♥끙르가즘냥덩♥	06.01	15	0
2705535	치킨은 천박한 음식물쓰레기이다	♥끙르가즘냥덩♥	06.01	16	0
2705534	끝없는 자유는 자유가 아니다	♥끙르가즘냥덩♥	06.01	14	0
2705533	이런 미소가 한녀의 매력 아닐까요? [3]	헬마스터	06.01	31	0
2705532	윤 정부의 끝없는 '원전' 고집... "어리석다" [3]	프갤러(49.165)	06.01	33	1
2705530	반주와 함깨 먹을만한 음식..	♥끙르가즘냥덩♥	06.01	13	0