[BOJ] 4963. 섬의 개수(BFS, DFS)

#. Problem

https://www.acmicpc.net/problem/4963

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

단지번호 붙이기 문제와 섬나라 아일랜드 문제와 유사한 문제다.

나는 이런 좌표 탐색에서는 Queue를 사용하는게 더 직관적이고 편해서

주로 Queue를 사용해서 하게 된다.

#. bfs Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

#include <cstdio> #include <queue> #include <cstring> using namespace std; #define pos pair<int, int> #define x first #define y second   int w, h; int map[55][55]; int dx[] = { -1, -1, -1, 0, 1, 1, 1, 0 }; int dy[] = { -1, 0, 1, 1, 1, 0, -1, -1 };   void process()  {     int i, j, k, res = 0;     memset(map, 0, sizeof(map));       for (i = 1; i <= h; i++) {         for (j = 1; j <= w; j++) {             scanf("%d", &map[i][j]);         }     }       queue<pos> Q;     for (i = 1; i <= h; i++) {         for (j = 1; j <= w; j++) {             if (map[i][j]) {                 Q.push({ i, j });                 map[i][j] = 0;                   while (!Q.empty()) {                     pos now = Q.front();                     Q.pop();                       for (k = 0; k < 8; k++) {                         int xx = now.x + dx[k];                         int yy = now.y + dy[k];                           if (map[xx][yy]) {                             Q.push({ xx, yy });                             map[xx][yy] = 0;                         }                     }                 }                   res++;             }         }     }          printf("%d\n", res); }   int main(void) {     //freopen("input.txt", "rt", stdin);       while (scanf("%d %d", &w, &h), w && h)          process();       return 0; } Colored by Color Scripter

cs

좌표 탐색 문제 코드는 다 유사해서 PASS

#. dfs Code

#include <cstdio>
#include <cstring>
using namespace std;
 
int w, h;
int map[55][55];
bool ck[55][55];
int dx[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
int dy[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
 
void dfs(int x, int y)
{
    ck[x][y] = 1;
    for (int i = 0; i < 8; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
 
        if (map[xx][yy] && !ck[xx][yy])
            dfs(xx, yy);
    }
}
 
void process()
{
    int i, j, res = 0;
    memset(map, 0, sizeof(map));
    memset(ck, 0, sizeof(ck));
 
    for (i = 1; i <= h; i++) {
        for (j = 1; j <= w; j++) {
            scanf("%d", &map[i][j]);
        }
    }
 
    for (i = 1; i <= h; i++) {
        for (j = 1; j <= w; j++) {
            if (map[i][j] && !ck[i][j]) {
                dfs(i, j);
                res++;
            }
        }
    }
 
    printf("%d\n", res);
}
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    while (scanf("%d %d", &w, &h), w && h)
        process();
 
    return 0;
}