[C++] 백준 알고리즘 4963번 (섬의 개수)

문제

---

이번에 다뤄볼 문제는 4963번 문제 '섬의 개수'입니다.

섬의 개수 문제에서 연습해야하는 key-point는 재귀함수입니다.

 

재귀함수란 어떤 함수에서 자신을 다시 호출하여 작업울 수행하는 방식의 함수를 뜻합니다.

문제를 읽어봤을때 한 정사각형과 가로, 세로 또는 대각선으로 가는 방향 까지도 고려해야 하므로 총 8가지 방향을 탐색하게 합니다.

재귀를 통해 구현 했으며 최초로 발견되는 육지가 발생하면 i_count값을 증가시켜준뒤

재귀로 들어가 이어지는 육지들의 값을 2로 바꿔주어 다음번에 다시 탐색하지 않게 합니다.

 

 

 

아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다.

---

 

코드(C++)

#include <iostream>
using namespace std;
 
int map[52][52];
 
const int dsize = 8;
int dirX[8] = {0,0,-1,1,1,1,-1,-1}; 
int dirY[8] = {-1,1,0,0,-1,1,1,-1};
 
int i_count = 0;
 
int w = 1, h = 1;
int xx = 0, yy = 0;
 
 
void island(int x, int y) {
    map[x][y] = 2;
 
    for (int k = 0; k < 8; k++) {
        xx = x + dirX[k];
        yy = y + dirY[k];
        if (map[xx][yy] == 0 || map[xx][yy] == 2 || xx<0 || xx>h || yy<0 || yy>w) continue;
        else if (map[xx][yy] == 1) {
            island(xx, yy);
        }
    }
 
};
 
int main() {
 
    while (1) {
        cin >> w >> h;
        if (w == 0 && h == 0) return 0;
 
        for (int i = 1; i <= h; i++) {
            for (int j = 1; j <= w; j++) {
                cin >> map[i][j];
            }
        }
 
         
        for (int i = 1; i <= h; i++) {
            for (int j = 1; j <= w; j++) {
                if (map[i][j] == 1) {
                    i_count++;
                    island(i, j);
                }
            }
        }
 
        cout << i_count << endl;
        i_count = 0;
    }
    return 0;
     
}