[백준_4963번] 섬의 개수

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

4963번: 섬의 개수

[문제]

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

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

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

 

[입력 조건]

• 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.
• 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.
• 입력의 마지막 줄에는 0이 두 개 주어진다.

 

[코드]

import java.util.*;

public class BaekJoon_4963 {
	static int w,h,result;
	static int[][] map;
	static boolean[][] visited;
	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) {
			w=sc.nextInt();
			h=sc.nextInt();
			
			if(w==0&&h==0)
				return;
			
			map=new int[h][w];
			visited=new boolean[h][w];
			
			for(int i=0;i<h;i++)
				for(int j=0;j<w;j++)
					map[i][j]=sc.nextInt();
			
			result=0;
			for(int i=0;i<h;i++) {
				for(int j=0;j<w;j++) {
					// 시작되는 점의 좌표로 부터 이어져 있는 모든 섬 방문처리
					if(map[i][j]==1&&!visited[i][j]) {
						DFS(i,j);
						result++;
					}
				}
			}
			System.out.println(result);
		}
	}
	
	static void DFS(int x, int y) {
		visited[x][y]=true;
		
		// 8방향 탐색
		for(int i=0;i<8;i++) {
			int nx=x+dx[i];
			int ny=y+dy[i];
			
			if(nx>=0&&ny>=0&&nx<h&&ny<w) {
				// 방문하지 않았고, 섬인 곳을 기준으로 다시 DFS
				if(!visited[nx][ny]&&map[nx][ny]==1) {
					DFS(nx,ny);
				}
			}
		}
	}

}

 

[고찰]

 이번 문제는 이전에 많이 풀어봤던 맵에서 이어져 있는 덩어리를 찾는 문제였다. 이전 문제와 다른점은 대각선 방향도 포함해야 한다는 것으로 쉽게 해결할 수 있었다.