BFS - KimTaebin-ai/study_posts GitHub Wiki

BFS

: ๋‹ค์ฐจ์› ๋ฐฐ์—ด์—์„œ ๊ฐ ์นธ์„ ๋ฐฉ๋ฌธํ•  ๋•Œ ๋„ˆ๋น„๋ฅผ ์šฐ์„ ์œผ๋กœ ๋ฐฉ๋ฌธํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜

๋ฃจํŠธ ๋…ธ๋“œ(ํ˜น์€ ๋‹ค๋ฅธ ์ž„์˜์˜ ๋…ธ๋“œ)์—์„œ ์‹œ์ž‘ํ•ด์„œ ์ธ์ ‘ํ•œ ๋…ธ๋“œ๋ฅผ ๋จผ์ € ํƒ์ƒ‰ํ•˜๋Š” ๋ฐฉ๋ฒ•

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

#include <stdio.h>

#define MAX 502

typedef struct
{
    int x;
    int y;
} LocationPoint;

typedef struct
{
    LocationPoint data[MAX * MAX];
    int head;
    int tail;
} Queue;

int board[MAX][MAX] = {
    {1, 1, 1, 0, 1, 0, 0, 0, 0, 0},
    {1, 0, 0, 0, 1, 0, 0, 0, 0, 0},
    {1, 1, 1, 0, 1, 0, 0, 0, 0, 0},
    {1, 1, 0, 0, 1, 0, 0, 0, 0, 0},
    {0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};

int n = 7, m = 10;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1}; // ์ƒํ•˜์ขŒ์šฐ

int visit[MAX][MAX] = {0}; // ํ•ด๋‹น ์นธ ๋ฐฉ๋ฌธ ์—ฌ๋ถ€๋ฅผ ์ €์žฅ

void initQueue(Queue *q) // ํ์˜ head, tail ๊ฐ’์„ 0 ์œผ๋กœ ์ดˆ๊ธฐํ™”
{
    q->head = 0;
    q->tail = 0;
}

void push(Queue *q, LocationPoint p)
{
    q->data[q->tail++] = p;
}

int empty(Queue *q)
{
    return q->head == q->tail;
}

LocationPoint pop(Queue *q)
{
    return q->data[q->head++];
}

int main()
{
    Queue Q;
    initQueue(&Q);

    visit[0][0] = 1;                 // 1. ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์‹œ์ž‘ ์‹œ (0, 0) ๋ฐฉ๋ฌธ ํ‘œ์‹œ
    push(&Q, (LocationPoint){0, 0}); // 2. ํ•ด๋‹น ์นธ์„ ํ์— ๋„ฃ๋Š”๋‹ค.

    while (!empty(&Q))
    {
        LocationPoint current = pop(&Q); // 3. ์ดˆ๊ธฐ ์„ธํŒ… ํ›„ ํ๊ฐ€ ๋นŒ ๋•Œ๊นŒ์ง€ ํ์˜ head๋ฅผ ๋นผ์คŒ
        printf("(%d, %d) -> ", current.x, current.y);

        // 4. ํ•ด๋‹น ์ขŒํ‘œ์˜ ์ƒํ•˜์ขŒ์šฐ๋ฅผ ์‚ดํŽด๋ณด๋ฉฐ ํ์— ๋„ฃ๋Š”๋‹ค

        for (int dir = 0; dir < 4; dir++) // ์ƒํ•˜์ขŒ์šฐ ์‚ดํŽด๋ณด๊ธฐ
        {
            int nX = current.x + dx[dir];
            int nY = current.y + dy[dir]; // nx, ny์— dir์—์„œ ์ •ํ•œ ๋ฐฉํ–ฅ์˜ ์ธ์ ‘ํ•œ ์นธ์˜ ์ขŒํ‘œ๊ฐ€ ๋“ค์–ด๊ฐ

            if (nX < 0 || nX >= n || nY < 0 || nY >= m) // ๋ฒ”์œ„ ๋ฐ–์ผ ๊ฒฝ์šฐ ๋„˜์–ด๊ฐ
                continue;
            if (visit[nX][nY] || board[nX][nY] != 1) // ์ด๋ฏธ ๋ฐฉ๋ฌธํ•œ ์นธ์ด๊ฑฐ๋‚˜ 0์ธ ๊ฒฝ์šฐ
                continue;
            visit[nX][nY] = 1;                 // ์กฐ๊ฑด์— ๊ฑธ๋ฆฌ์ง€ ์•Š๋Š”๋‹ค๋ฉด ๋ฐฉ๋ฌธ ๊ฐ€๋Šฅ, ๋ฐฉ๋ฌธํ–ˆ์Œ์„ ์ €์žฅ
            push(&Q, (LocationPoint){nX, nY}); // ํ•ด๋‹น ์ขŒํ‘œ๋ฅผ ํ์— ๋„ฃ์–ด์คŒ
        }
    }

    return 0;
}

bfs ์•Œ๊ณ ๋ฆฌ์ฆ˜์—์„œ๋Š” ์ขŒํ‘œ๋ฅผ ๋‹ด์„ ํ๊ฐ€ ํ•„์š”ํ•จ. ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์‹œ์ž‘๋˜๋ฉด ์šฐ์„  (0, 0)์— ๋ฐฉ๋ฌธํ–ˆ๋‹ค๋Š” ํ‘œ์‹œ -> ํ•ด๋‹น ์นธ์„ ํ์— ๋„ฃ๋Š”๋‹ค. ์ด ์ดˆ๊ธฐ์„ธํŒ…์ด ๋๋‚œ ํ›„์—๋Š” ํ๊ฐ€ ๋นŒ ๋•Œ๊นŒ์ง€ ๊ณ„์† ํ์˜ front ๋ฅผ ๋นผ๊ณ  ํ•ด๋‹น ์ขŒํ‘œ์˜ ์ƒํ•˜์ขŒ์šฐ๋ฅผ ์‚ดํŽด๋ณด๋ฉฐ ํ์— ๋„ฃ์–ด์ค€๋‹ค

bfs ์ง์ ‘ ๊ตฌํ˜„์‹œ ์ž์ฃผํ•˜๋Š” ์‹ค์ˆ˜๋“ค

  1. ์‹œ์ž‘์ ์— ๋ฐฉ๋ฌธํ–ˆ๋‹ค๋Š” ํ‘œ์‹œ๋ฅผ ๋‚จ๊ธฐ์ง€ ์•Š๋Š”๋‹ค.
  2. ํ์— ๋„ฃ์„ ๋•Œ ๋ฐฉ๋ฌธํ–ˆ๋‹ค๋Š” ํ‘œ์‹œ๋ฅผ ํ•˜๋Š” ๋Œ€์‹  ํ์—์„œ ๋นผ๋‚ผ ๋•Œ ๋ฐฉ๋ฌธํ–ˆ๋‹ค๋Š” ํ‘œ์‹œ๋ฅผ ๋‚จ๊ฒผ๋‹ค.
  3. ์ด์›ƒํ•œ ์›์†Œ๊ฐ€ ๋ฒ”์œ„๋ฅผ ๋ฒ—์–ด๋‚ฌ๋Š”์ง€์— ๋Œ€ํ•œ ์ฒดํฌ๋ฅผ ์ž˜๋ชปํ–ˆ๋‹ค.

bfs ์˜ˆ์‹œ ๋ฌธ์ œ 1 (๊ทธ๋ฆผ)

๊ทธ๋ฆผ 1926

image

์ฃผ์–ด์ง„ ๋„ํ™”์ง€์—์„œ ๋ชจ๋“  ๊ทธ๋ฆผ์„ ์ฐพ์•„์•ผํ•˜๊ณ  ์‹œ์ž‘์ ์ด ๊ณ ์ •๋˜์–ด์žˆ์ง€ ์•Š์Œ

๊ทธ๋Ÿฌ๋‚˜ ๊ฒฐ๊ตญ ํ•ด์•ผํ•  ์ผ์€

  1. ์ƒํ•˜์ขŒ์šฐ๋กœ ์—ฐ๊ฒฐ๋œ ๊ทธ๋ฆผ์˜ ํฌ๊ธฐ๋ฅผ ์•Œ์•„๋‚ด๊ธฐ
  2. ๋„ํ™”์ง€์— ์žˆ๋Š” ๋ชจ๋“  ๊ทธ๋ฆผ์„ ์ฐพ์•„๋‚ด๊ธฐ

4๊ฐœ์˜ ๊ทธ๋ฆผ ์‹œ์ž‘์ ์€ ์ด์ค‘ for๋ฌธ์„ ๋Œ๋ฉด์„œ ์‹œ์ž‘์ ์„ ์ฐพ์œผ๋ฉด ๋œ๋‹ค.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SIZE 502

// ํ์—์„œ ์‚ฌ์šฉํ•  ๊ตฌ์กฐ์ฒด ์ •์˜
typedef struct {
    int x;
    int y;
} Point;

// ํ ๊ตฌํ˜„
typedef struct {
    Point* data;
    int front;
    int rear;
    int size;
} Queue;

Queue* createQueue(int size) {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->data = (Point*)malloc(sizeof(Point) * size);
    q->front = 0;
    q->rear = -1;
    q->size = 0;
    return q;
}

void enqueue(Queue* q, Point p) {
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->data[q->rear] = p;
    q->size++;
}

Point dequeue(Queue* q) {
    Point p = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    q->size--;
    return p;
}

bool isEmpty(Queue* q) {
    return q->size == 0;
}

// ์ „์—ญ ๋ณ€์ˆ˜ ์„ ์–ธ
int board[MAX_SIZE][MAX_SIZE];
bool vis[MAX_SIZE][MAX_SIZE];
int n, m;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    scanf("%d %d", &n, &m);
    
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            scanf("%d", &board[i][j]);
    
    int mx = 0;  // ๊ทธ๋ฆผ์˜ ์ตœ๋Œ“๊ฐ’
    int num = 0; // ๊ทธ๋ฆผ์˜ ์ˆ˜
    
    Queue* q = createQueue(MAX_SIZE * MAX_SIZE);
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(board[i][j] == 0 || vis[i][j]) continue;
            
            num++; // ๊ทธ๋ฆผ์˜ ์ˆ˜ 1 ์ฆ๊ฐ€
            vis[i][j] = true;
            Point start = {i, j};
            enqueue(q, start);
            
            int area = 0; // ๊ทธ๋ฆผ์˜ ๋„“์ด
            
            while(!isEmpty(q)) {
                area++;
                Point cur = dequeue(q);
                
                for(int dir = 0; dir < 4; dir++) {
                    int nx = cur.x + dx[dir];
                    int ny = cur.y + dy[dir];
                    
                    if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                    if(vis[nx][ny] || board[nx][ny] != 1) continue;
                    
                    vis[nx][ny] = true;
                    Point next = {nx, ny};
                    enqueue(q, next);
                }
            }
            
            mx = max(mx, area);
        }
    }
    
    printf("%d\n%d\n", num, mx);
    
    free(q->data);
    free(q);
    
    return 0;
}

bfs ์˜ˆ์‹œ ๋ฌธ์ œ ์‘์šฉ 1 ๊ฑฐ๋ฆฌ ์ธก์ • (๋ฏธ๋กœ ํƒ์ƒ‰)

๋ฏธ๋กœ ํƒ์ƒ‰ 2178

image

โš ๏ธ **GitHub.com Fallback** โš ๏ธ