10. 10차시 수업

1. flood fill : 이날 피치 못할 사정으로 지각해서 이 부분은 듣지 못했습니다

2. dijkstra without Priority Queue

#include <stdio.h>

#define INF 0x7FFFFFFF

int start, finish, arr[1000][1000];

int node_num, edge_num;

int node_left;

int distance[1000];

int precedessor[1000];

int visited[1000];

void search(int cur){

    if (cur == start){

        printf("%d ", start);

        return;

    }

    search(precedessor[cur]);

    printf("%d ", cur);

}

void dijkstra(int cur){

    for (int i = 0; i < node_num; ++i){

        if (arr[cur][i]>0){

            if (distance[cur] + arr[cur][i] < distance[i]){

                distance[i] = distance[cur] + arr[cur][i];

                precedessor[i] = cur;

            }

        }

    }

    visited[cur] = 1;

}

int main(){

    scanf("%d %d", &start, &finish);

    printf("node num : ");

    scanf("%d", &node_num);

    node_left = node_num;

    printf("edge_num : ");

    scanf("%d", &edge_num);

    for (int i = 0; i < edge_num; ++i){

        int a, b, c;

        scanf("%d %d %d", &a, &b, &c);

        arr[a][b] = c;

    }

    //distance 초기화

    for (int i = 1; i <node_num; ++i){

        distance[i] = INF;

    }

    while (node_left > 0){

        int min;

        int first_experiment = 1;//첫번째 조건만족시엔 min에 수 집어넣어주기

        for (int i = 0; i < node_num; ++i){

            if (visited[i] == 1) continue;

            if (first_experiment){

                first_experiment = 0;

                min = i;

                continue;

            }

            if (distance[i] < distance[min]) min = i;

        }

        dijkstra(min);

        node_left--;

    }

    //다 끝났으면 역추적 ㄱ

    search(finish);

}

더 자세한건 11. 11차시 수업에서 확인하세요~