알고리즘:bfs 색칠하기

알고리즘:bfs 색칠하기

0으로 둘러 쌓인 1로 이루어진 곳에 다른 숫자 채우기

bfs3.txt

7
0 1 1 0 1 0 0
0 1 1 0 1 0 1
1 1 1 0 1 0 1
0 0 0 0 1 1 1
0 1 0 0 0 0 0
0 1 1 1 1 1 0
0 1 1 1 0 0 0

------------------------------------------------

#include <stdio.h>

typedef struct _path{
    int x;
    int y;
    int length;
} Path;

Path que[100];

int n;
int map[100][100];
int front = 0;
int rear = 0;
int count = 1;
int ans = 100;
void enque(int x, int y, int c){
    que[rear].x = x;
    que[rear].y = y;
    que[rear].length = c +1;
    rear ++;

    map[y][x] = c;

}
void bfs3(int x, int y, int c){
        map[y][x] = c;

        que[rear].x = x;
        que[rear].y = y;
        que[rear].length = count;

        rear++;
        Path path;
        while(front < rear){
            path  = que[front++];

            if (path.y -1 >= 0 && map[path.y -1][path.x] == 1){
                enque(path.x, path.y -1, c);
            }
            if (path.y +1 < n && map[path.y +1][path.x] == 1){
                enque(path.x, path.y+1, c);
            }
            //left
            if (path.x-1 >= 0 && map[path.y][path.x-1] == 1){
                enque(path.x-1, path.y,c);
            }
            //right
            if (path.x+1 < n  && map[path.y ][path.x+1] == 1){
                enque(path.x+1, path.y, c);
            }
        }
}

void printmap(){
    printf("-------------------------------\n");
     for(int i =0 ; i < n; i++){
        for(int j = 0 ; j < n ; j++){
                printf("%d", map[i][j]);
        }
        printf("\n");
    }
}
int main()
{
    int start;
    int v1, v2;


    freopen("bfs3.txt","r",stdin);

    scanf("%d", &n);


    for(int i =0 ; i < n; i++){
        for(int j = 0 ; j < n ; j++){
                scanf("%d", &map[i][j]);
        }
    }

    printmap();

    int color = 2;
    for (int i = 0; i < n ; i ++){
        for(int j = 0; j < n ; j++){
            if(map[i][j] == 1){
                bfs3(j,i, color++);
            }
        }
    }

    printf("answer %d\n", color-2);
    printmap();

    return 0;
}

알고리즘:bfs 길찾기

알고리즘:bfs 길찾기

bfs2.txt

6
1 1 1 1 1 1
0 0 1 0 0 1
1 1 1 0 1 1
1 0 0 0 1 0
1 1 1 0 1 0
0 0 1 1 1 1

---------------------------------------------------
#include <stdio.h>

typedef struct _path{
    int x;
    int y;
    int length;
} Path;

Path que[100];

int n;
int map[100][100];
int front = 0;
int rear = 0;
int count = 1;
int ans = 100;
void enque(int x, int y, int len){
    que[rear].x = x;
    que[rear].y = y;
    que[rear].length = len +1;
    rear ++;

    map[y][x] = 0;

}
void bfs2(int x, int y){
    //map에 방문 표시
    //que에 넣기
    enque(x,y, 0);

    // if que != empty 까지 loop
    while(front < rear){
        //que에서 하나 꺼내기
        Path path  = que[front++];

        // end에 도착 했으면 break;
        //ans update
        if(path.x == n-1 && path.y == n-1){
            ans = path.length;
            break;
        }

        //up
        if (path.y -1 >= 0 && map[path.y -1][path.x] == 1){
            enque(path.x, path.y -1, path.length);
        }
        //down
        if (path.y +1 < n && map[path.y +1][path.x] == 1){
            enque(path.x, path.y+1, path.length);
        }
        //left
        if (path.x-1 >= 0 && map[path.y][path.x-1] == 1){
            enque(path.x-1, path.y, path.length);
        }
        //right
        if (path.x+1 < n  && map[path.y ][path.x+1] == 1){
            enque(path.x+1, path.y, path.length);
        }
    }
    printf("ans = %d \n", ans);
}
void printmap(){
    printf("-------------------------------\n");
     for(int i =0 ; i < n; i++){
        for(int j = 0 ; j < n ; j++){
                printf("%d", map[i][j]);
        }
        printf("\n");
    }
}

int main()
{
    int start;
    int v1, v2;


    freopen("bfs2.txt","r",stdin);

    scanf("%d", &n);


    for(int i =0 ; i < n; i++){
        for(int j = 0 ; j < n ; j++){
                scanf("%d", &map[i][j]);
        }
    }

    printmap();
    bfs2(0,0);

    return 0;
}

알고리즘:BFS node 순회 하기

BFS node 순회 하기

bfs.txt

6 9
1 2 1 3 2 4 2 5 3 4 3 6 4 5 4 6 5 6

----------------------------------------------

#include <stdio.h>

int n;
int link;
int que[30];
int visit[30];
int map[30][30];
int front = 0;
int rear = 0;

void bfs(int v){
    // visit 표시
    visit[v] = 1;
    //que에 v 삽입
    que[rear++] = v;
    // que가 빌때까지
    while(front < rear){
            // v 값에 연결된 값 검색
        int node = que[front++];
        // node와 연결된 v를 찾는다.
        for(int i = 0; i <= n; i ++ ){
                // 연결 되어 있고 방문하지 않았다면
            if(map[node][i] == 1 && visit[i] == 0 ){
                // 방문표시 하고 que에 넣는다.
                visit[i] = 1;
                que[rear++] = i;
                printf("%d -> %d \n", node, i);
            }
        }
    }
}


int main()
{
    int start;
    int v1, v2;


    freopen("bfs.txt","r",stdin);

    scanf("%d%d", &n, &link);


    for(int i =0 ; i < link; i++){
        scanf("%d%d", &v1, &v2);

        map[v1][v2] = map[v2][v1] = 1;
    }

    bfs(1);

    return 0;
}