[BOJ] 4963. 섬의 개수

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

4963번: 섬의 개수

DFS나 BFS를 사용해서 연결 요소를 구하는 문제이다.

1. 땅이고 아직 방문하지 않은 곳을 DFS를 통해서 모두 방문해줬다.
2. 새로 DFS를 실핼해줄때마다 count값을 증가시킨다.

 

import java.util.*;

public class Main {
	static int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
	static int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int w = sc.nextInt();
			int h = sc.nextInt();
            
			if(w ==0 && h ==0) //종료 조건
				break;
			
            int count = 0;
			int square[][] = new int[h][w];
			boolean check[][] = new boolean[h][w];
            
			for(int i=0; i<h; i++) {
				for(int j=0; j<w; j++) {
					square[i][j] = sc.nextInt();
				}
			}
            
			for(int i=0; i<h; i++) {
				for(int j=0; j<w; j++) {
					if(square[i][j] == 1 && check[i][j] == false){ //땅인데 아직 방문하지 않았다.
						dfs(i, j, square, check, h, w);	
						count++;
					}
				}
			}
			System.out.println(count);
		}
	}
	static void dfs(int i, int j, int[][] square, boolean[][] check, int h, int w) {
		check[i][j] = true; //방문 체크
		for(int k=0; k<8; k++) {
			int x = i+dx[k];
			int y = j+dy[k];
			if(x >= 0 && y >= 0 && x &lt h && y &lt w)
				if(square[x][y] == 1 && check[x][y] == false) //땅인데 방문하지 않은 곳 방문
					dfs(x, y, square, check, h, w);
		}
	}

}