4963 : 섬의 개수 ( 백준 / java )

www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

 

 

*해결 과정

BFS를 통해서 섬을 계속 확인하면서, visited를 이용해 섬을 방문했는지 안했는지 확인합니다. 특히, 상 하 좌 우 4방향을 살피는 것 뿐만 아니라 대각선도 포함하기 때문에 같이 세주어야 합니다.

 

import java.util.*;
public class Main {

	static int N;
	static int M;
	static int[][] array;
	static boolean[][] visited;
	static int land;
	static int[] dx = {0,0,1,-1,-1,-1,1,1};
	static int[] dy = {1,-1,0,0,-1,1,-1,1};
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		while(true) {
			M = sc.nextInt();
			N = sc.nextInt();
			if(N==0 && M==0) break;
			array = new int[N][M];
			visited = new boolean[N][M];
			land=0;
			
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					array[i][j] = sc.nextInt(); //1은 땅, 0은 바다
				}
			}
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					if(visited[i][j]==false && array[i][j]==1) {
						move(i,j);
						land++;
					}
				}
			}
			System.out.println(land);
		}
	}
	
	public static void move(int x, int y) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] {x,y});
		
		while(!queue.isEmpty()) {
			int[] set = queue.poll();
			
			for(int i=0;i<8;i++) {
				int newX = set[0] + dx[i];
				int newY = set[1] + dy[i];
				if(newX<0 || newY<0 || newX>=N || newY>=M) continue;
				if(visited[newX][newY]==true) continue;
				
				if(array[newX][newY]==1) {
					visited[newX][newY] = true;
					queue.add(new int[] {newX,newY});
				}
			}
		}
	}

}