# 백준 : 섬의 개수 (4963)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_4963_numberofislands)

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdlib>

using namespace std;

int map[51][51];
int visit[51][51];
int W, H;
int cnt;

void DFS(int h, int w) {
visit[h][w] = 1;

if ((h > 0) && map[h - 1][w] && !visit[h - 1][w]) {
DFS(h - 1, w);
}
if ((h < H - 1) && map[h + 1][w] && !visit[h + 1][w]) {
DFS(h + 1, w);
}
if ((w > 0) && map[h][w - 1] && !visit[h][w - 1]) {
DFS(h, w - 1);
}
if ((w < W - 1) && map[h][w + 1] && !visit[h][w + 1]) {
DFS(h, w + 1);
}
if (h > 0) {
if ((w > 0) && map[h - 1][w - 1] && !visit[h - 1][w - 1]) {
DFS(h - 1, w - 1);
}
if ((w < W - 1) && map[h - 1][w + 1] && !visit[h - 1][w + 1]){
DFS(h - 1, w + 1);
}
}
if (h < H - 1) {
if ((w > 0) && map[h + 1][w - 1] && !visit[h + 1][w - 1]) {
DFS(h + 1, w - 1);
}
if ((w < W - 1) && map[h + 1][w + 1] && !visit[h + 1][w + 1]) {
DFS(h + 1, w + 1);
}
}
}

int main(void)
{
W = 1;
H = 1;

while (1) {
cin >> W >> H;
if ((W == 0) && (H == 0)) break;
cnt = 0;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
cin >> map[i][j];
}
}

for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (map[i][j] && !visit[i][j]) {
DFS(i, j);
cnt+=1;
}
}
}
cout << cnt << endl;
cnt = 0;
memset(map, 0, sizeof(map));
memset(visit, 0, sizeof(visit));
}
return 0;
}

풀이

DP로 풀까 고민하다가 손에 익은 백트래킹을 이용했다.
문제의 유형이 비슷해서 이전 포스팅과 같이 전체 비교 후 cnt를 증가하는 방법을 사용했다.