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

섬을 true 바다를 false로 배열을 두었다.

배열을 돌다가 true이면, BFS로 인접한 true를 모두 조사해서 false로 만들어주고 회귀하는 식으로 갯수를 센다.

이런 식으로 어떤 영역과 관련된 영역을 찾는 알고리즘을

"플러드 필(flood fill)" 알고리즘이라고 하는데, 이문제가 대표적이다.

C++코드

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

bool arr[51][51];

void DFS(int i, int j) {
	if (arr[i][j] == false) return;

	arr[i][j] = false;
	DFS(i + 1, j);
	DFS(i + 1, j - 1);
	DFS(i + 1, j + 1);
	DFS(i, j - 1);
	DFS(i, j + 1);
	DFS(i - 1, j);
	DFS(i - 1, j - 1);
	DFS(i - 1, j + 1);
}

int main() {
	int w;
	int h;
	
	while (1) {
		cin >> w >> h;
		if (w == 0 && h == 0) break;
		int count = 0;
		for (int i = 1; i <= h; i++) {
			for (int j = 1; j <= w; j++) {
				cin >> arr[i][j];
			}
		}

		for (int i = 1; i <= h; i++) {
			for (int j = 1; j <= w; j++) {
				if (arr[i][j]) {
					count++;
					DFS(i, j);
				}
			}
		}
		
		cout << count << '\n';
	}
}

C# 코드

using System.Collections;
using System.Collections.Generic;
using static System.Console;
using System;

class Program
{
    static bool[][] arr = new bool[52][];		//초기화가 true, false로	
	static void DFS(int i, int j)
	{
		if (arr[i][j] == false) return;

		arr[i][j] = false;
		DFS(i + 1, j);
		DFS(i + 1, j - 1);
		DFS(i + 1, j + 1);
		DFS(i, j - 1);
		DFS(i, j + 1);
		DFS(i - 1, j);
		DFS(i - 1, j - 1);
		DFS(i - 1, j + 1);
	}
	public static void Main(string[] args)
    {
		int w, h;
		for(int i = 0; i< arr.Length; i++)
			arr[i] = new bool[52];

		while (true)
        {
			string[] input = ReadLine().Split(' ');
			w = int.Parse(input[0]);
			h = int.Parse(input[1]);
			if (w == 0 && h == 0) break;
			int count = 0;
			for(int i = 1; i<=h; i++)
            {
				input = ReadLine().Split(' ');
				for(int j = 1; j<=w; j++)
                {
					if (int.Parse(input[j - 1]) == 1) arr[i][j] = true;
					else arr[i][j] = false;
                }
            }

			for(int i = 1; i<=h; i++)
            {
				for(int j = 1; j<= w; j++)
                {
                    if (arr[i][j]) {
						count++;
						DFS(i, j);
					}
                }
            }
			WriteLine(count);
        }
    }
}

java코드

import java.io.*;
import java.util.*;

public class Main {
    static boolean[][] arr = new boolean[52][52]; // 초기값 true, false
    static void DFS(int i, int j) {
        if (arr[i][j] == false) return;

        arr[i][j] = false;
        DFS(i + 1, j);
        DFS(i + 1, j - 1);
        DFS(i + 1, j + 1);
        DFS(i, j - 1);
        DFS(i, j + 1);
        DFS(i - 1, j);
        DFS(i - 1, j - 1);
        DFS(i - 1, j + 1);
    }
    public static void main(String[] args) {
        int w,h,k;
        Scanner s = new Scanner(System.in);
        while(true){
            w = s.nextInt();
            h = s.nextInt();
            if(w == 0 && h == 0) break;
            int count = 0;
            for(int i = 1; i<=h; i++){
                for(int j = 1; j<=w; j++){
                    k = s.nextInt();
                    if(k == 1) arr[i][j] = true;
                }
            }
            for(int i = 1; i<=h ; i++){
                for(int j = 1; j<=w; j++){
                    if(arr[i][j]){
                        count++;
                        DFS(i, j);
                    }
                }
            }
            System.out.println(count);
        }

    }
}

kotlin 코드

import java.util.*
import kotlin.math.*

var arr = Array(52, {BooleanArray(52)})

fun DFS(i : Int, j : Int) {
    if (arr[i][j] == false) return;

    arr[i][j] = false;
    DFS(i + 1, j);
    DFS(i + 1, j - 1);
    DFS(i + 1, j + 1);
    DFS(i, j - 1);
    DFS(i, j + 1);
    DFS(i - 1, j);
    DFS(i - 1, j - 1);
    DFS(i - 1, j + 1);
}


fun main(args: Array<String>){
    val s = Scanner(System.`in`)
    var w = 0
    var h = 0
    var k = 0
    while(true){
        w = s.nextInt()
        h = s.nextInt()
        if(w == 0 && h == 0) break;
        var count = 0
        for( i in 1..h){
            for(j in 1..w){
                k = s.nextInt()
                if(k == 1) arr[i][j] = true;
            }
        }
        for(i in 1.. h){
            for( j in 1.. w){
                if(arr[i][j]){
                    count++;
                    DFS(i, j)
                }
            }
        }
        println(count)
    }
}

python 코드

arr = [[0 for _ in range(52)] for _ in range(52)]
def DFS(i, j):
    if arr[i][j] == 0:
        return
    arr[i][j] = 0
    DFS(i + 1, j)
    DFS(i + 1, j - 1)
    DFS(i + 1, j + 1)
    DFS(i, j - 1)
    DFS(i, j + 1)
    DFS(i - 1, j)
    DFS(i - 1, j - 1)
    DFS(i - 1, j + 1)

while(1):
    inpu = []
    w, h = map(int, input().split())
    if w == 0 & h == 0:
        break
    count = 0
    for i in range(1, h+1):
        inpu = list(map(int, input().split()))
        for j in range(1, w+1):
            arr[i][j]= inpu[j-1]

    for i in range(1, h+1):
        for j in range(1, w+1):
            if arr[i][j] == 1 :
                count += 1
                DFS(i,j)
    print(count)