[BAEKJOON 백준] 4963 섬의 개수

www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

 

1로된 덩어리를 찾는 문제이다.

 

이 문제는 DFS를 이용을 해서 배열 전체를 탐색해야 한다.

 

LinkedList 를 이용을 해서 문제를 풀었다. 그리고 대각선도 하나의 섬으로 생각하기 때문에 8방 탐색으로 문제를 풀어야 한다.

 

그리고 visit 배열을 이용해서 한번 방문한 곳은 방문하지 않도록 한다.

 

그렇게 탐색을 통해 중복되는 땅을 0으로 만들고, 1의 수를 세어 주어 총 섬의 수를 계산한다.

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	static int dx[]= {-1,1,0,0,-1,-1,1,1};
	static int dy[]= {0,0,-1,1,-1,1,-1,1};
	static boolean visit[][];
	
	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		while(true) {
			int M=sc.nextInt();
			int N=sc.nextInt();
			visit=new boolean[N+1][M+1];
			Point1 p;
			int[][]arr=new int[N][M];
			p=new Point1(N,M);
			if(p.x==0&&p.y==0) {
				System.exit(0);
			}
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					arr[i][j]=sc.nextInt();
				}
				
			}
			Point1 xy;
			LinkedList <Point1>que=new LinkedList<>();

			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					
					if(arr[i][j]==1) {
						xy=new Point1(i,j);
						que.offer(xy);
						visit[i][j]=true;

					while(!que.isEmpty()) {
						Point1 n=que.poll();
						for(int k=0;k<8;k++) {
							int nx=n.x+dx[k];
							int ny=n.y+dy[k];

							if(nx>=0&&nx<N&&ny>=0&&ny<M&&arr[nx][ny]==1&&!visit[nx][ny]) {
								arr[nx][ny]=0;
								que.offer(new Point1(nx,ny));
								visit[nx][ny]=true;

							}
						}
					}


					}
				}
				
			}
			int count=0;
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					if(arr[i][j]==1) {
						count++;
					}
				}
				
			}
			System.out.println(count);
			
		
			
			
		}
	}

}
class Point1{
	int x,y;

	public Point1(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
}