예제

아래에서 구현한 코드는 이 문제의 해답이다.

4963번: 섬의 개수

개념

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

Python

graph를 dict, set 으로 저장한다.

queue를 구현할 때 list 를 사용하면 시간복잡도가 $O(N)$이기 때문에 손해이다. collections 모듈의 deque 를 사용하면 시간을 절약할 수 있다.

인접 노드 중 방문하지 않은 노드를 큐에 넣을 때 set 데이터 타입을 사용하면 편하다.

Graph를 Dict로 구현했을 때 Pyton Pseudo코드

예제에서는 그래프가 $w\times h$인 필드이므로를 list에 저장한다.

from collections import deque

def BFS(graph, root):
    visited = []
    queue = deque([root])
    while queue:
        n = queue.popleft()
        if n not in visited:
            print("visit {}".format(n))
            visited.append(n)
            queue += graph[n] - set(visited)
    return visited

graph = {
    1: {2, 3},
    2: {3, 4},
    3: {4, 5},
    4: {2},
    5: set()
}
BFS(graph, 1)

예제

from collections import deque

dx = [1, -1, 0, 0, 1, 1, -1, -1]
dy = [0, 0, 1, -1, 1, -1, 1, -1]

def bfs(i, j):
    field[i][j] = 0
    queue = deque([(i, j)])
    while queue:
        x, y = queue.popleft()
        for i in range(8):
            nx, ny = x+dx[i], y+dy[i]
            if 0 <= nx < h and 0 <= ny < w:
                if field[nx][ny]:
                    field[nx][ny] = 0
                    queue.append((nx, ny))

w, h = map(int, input().split())
while w != 0 and h != 0:
    field = []
    for _ in range(h):
        tmp = list(map(int, input().split()))
        field.append(tmp)
    island = 0
    for i in range(h):
        for j in range(w):
            if field[i][j]:
                island += 1
                bfs(i, j)
    print(island)
    w, h = map(int, input().split())

C

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

#define qtype coord
#define MAX 50

typedef struct _coord {
    int x;
    int y;
} coord;

typedef struct _node {
    qtype data;
    struct _node *next;
} node;

typedef struct _linkedQueue {
    node *front, *rear;
    int len;
} queue;

queue q;

void init();
void push(qtype data);
qtype pop();

int map[MAX][MAX];
int island;
int w, h;

int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
int dy[] = {0, 0, 1, -1, 1, -1, 1, -1};

void bfs(int i, int j) {
    int nx, ny, k;
    init();
    coord root = {i, j};
    push(root);
    while (q.len) {
        coord pos = pop();
        for (k = 0; k < 8; k++) {
            nx = pos.x + dx[k];
            ny = pos.y + dy[k];
            if (0 <= nx && nx < h && 0 <= ny && ny < w) {
                if (map[nx][ny]) {
                    map[nx][ny] = 0;
                    coord n = {nx, ny};
                    push(n);
                }
            }
        }
    }
}

int main() {
    int i, j;
    scanf("%d %d", &w, &h);
    while (w != 0 && h != 0) {
        for (i = 0; i < h; i++) {
            for (j = 0; j < w; j++) {
                scanf("%d", &map[i][j]);
            }
        }
        island = 0;
        for (i = 0; i < h; i++) {
            for (j = 0; j < w; j++) {
                if (map[i][j]) {
                    island++;
                    bfs(i, j);
                }
            }
        }
        printf("%d\\n", island);
        scanf("%d %d", &w, &h);
    }
}

void init() {
    q.front = q.rear = NULL;
    q.len = 0;
}

void push(qtype data) {
    node *n = (node *)malloc(sizeof(node));
    n->data = data;
    n->next = NULL;
    if (!q.len) {
        q.front = q.rear = n;
    } else {
        q.rear->next = n;
        q.rear = q.rear->next;
    }
    q.len++;
}

qtype pop() {
    if (!q.len) {
        printf("- empty -\\n");
        exit(1);
    }
    node *del = q.front;
    qtype ret = q.front->data;
    q.front = q.front->next;
    free(del);
    q.len--;
    return ret;
}