[Baekjoon] #4963 섬의 개수

기본적인 그래프 문제, DFS 접근

풀이)

지도에서 현재 섬인 경우 해당 섬의 (위, 아래, 오른쪽, 왼쪽, 그리고 대각선 4방향) 확인. 

getDFS(x, y);

if) 해당 방향으로 섬인 경우 재귀탐색으로 다시 확인. // 단, 아직 방문하지 않은 섬인 경우

else) 바다인 경우 return.

--> 함수 return 경우 모든 인접 지역을 방문했거나 바다인경우로 섬+1

map[][] : 배열로 섬과 지도를 나타내는 지도 저장

visit[][] : 이미 방문한 지역 저장 // 1 : 방문, 0 : 미방문

DFS 그래프로 <위, 아래, 오른쪽, 왼쪽, 그리고 대각선 4 방향> 이동

  int[] xx = {-1, 0, 1, 1, 1, 0, -1, -1};

int[] yy = {-1, -1, -1, 0, 1, 1, 1, 0};

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static int w;
	static int h;
	static int[][] map;
	static int[][] visit;
	static int[] xx = {-1, 0, 1, 1, 1, 0, -1, -1};
	static int[] yy = {-1, -1, -1, 0, 1, 1, 1, 0};
	
	static ArrayList ar = new ArrayList<>();
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true){
			w = sc.nextInt();
			h = sc.nextInt();
			
			if(w == 0 && h == 0){
				break;
			}
			
			map = new int[w][h];
			visit = new int[w][h];
			int landCount =0;
			
			for(int i=0;i<h;i++){
				for(int j=0;j<w;j++){
					map[j][i] = sc.nextInt();
				}
			}
			
			for(int i=0;i<w;i++){
				for(int j=0;j<h;j++){
					if(map[i][j] == 1 && visit[i][j] == 0){
						getDFS(i, j);
						landCount++;
					}
				}
			}
			ar.add(landCount);
		}
		
		for(int i=0;i<ar.size();i++)
			System.out.println(ar.get(i));
	}
	
	public static void getDFS(int x, int y){
		visit[x][y] = 1;
		
		for(int i=0;i<8;i++){
			int ax = x+xx[i];
			int ay = y+yy[i];
			if(ax>=0 && ax<w && ay>=0 && ay<h){
				if(map[ax][ay] == 1 && visit[ax][ay] == 0){
					getDFS(ax, ay);
				}
			}
		}
	}
}