사용자 도구

사이트 도구


알고리즘:bfs

목차

BFS

개요

  • 현재 위치에서 한 단계씩 갈 수 있은 곳을 다 감
  • 현재 시점에서 출발 위치를 큐에 넣고 하나씩 방문하면서 조건 체크
  • 필요한 것
    • Queue
    • 방문 여부를 저장할 수 있는 공간

코드

| 전역변수 선언
typedef struct Q {
    int r, c;
};
Q queue[MAX * MAX + 10]; // 다음 위치들을 저장
int wp, rp; // 큐의 Write Point, Read Point
int visit[MAX + 10][MAX + 10]; // 방문 여부를 저장
int map[MAX + 10][MAX + 10]; // 실제 데이터 저장
int R; // 지도 세로 크기
int C; // 지도 가로 크기
 
int sr, sc, er, ec; // 시작 지점, 종료 지점
| BFS
int bfs() {
    Q p;
    register int i, nr, nc;
    wp = rp = 0;
    queue[wp++] = { sr, sc };
    visit[sr][sc] = 1;
 
    while(rp < wp) {
        p = queue[rp++];
 
        for(i = 0; i < 4; i++) {
            nr = p.r + dr[i];
            nc = p.c + dc[i];
 
 
            // 값이 범위를 벗어나는가? → continue
            if( nr < 0 || nr >= N || nc < 0 || nc >= N) {
                continue;
            }
 
            // 이미 방문한 곳인가? → continue
            if(visit[nc][nr] > 0) {
                continue;
            }
 
            // 조건에 맞는 경우라면 큐에 넣음 → 다음 시작점이 될 수 있도록 저장
            queue[wp++] = { nr, nc }
            visit[nr][nc] = 1;
    }
}
알고리즘/bfs.txt · 마지막으로 수정됨: 2018/06/26 15:33 저자 trsprs