알고리즘: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;
}