백준 4963번 섬의 개수(JAVA) - DFS

백준 4963번

 

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

4963번: 섬의 개수

 

문제설명

지도의 크기를 입력받고, 1(땅), 0(바다) 로 구분지어진 값들을 입력받아 섬의 개수를 세는 프로그램 작성.

섬이란 가로, 세로 또는 대각선 까지 연결되어있는 사각형을 말한다.

지도의 크기 0, 0 을 입력받으면 종료.

 

접근

1. 지도의 크기 w,h를 입력 받고 지도를 초기화 하면서 방문여부인 visit도 초기화 해준다.

2. 입력받은 w,h를 통해 0,1을 입력 받는다 ( 배열의 크기와 w,h는 순서가 반대)

3.  가로, 세로, 대각선 까지 체크를 위해 dx,dy를 총 8개 선언해준다. 

4. 각 정점들을 방문하며 1(땅) 이면서 방문하지 않은 점들을 dfs로 방문한다. 방문할 때마다 cnt(섬의 개수)를 1씩 증가 시켜준다.

 

 

코드

import java.util.*;
import java.io.*;

public class Main {
	
    static int dx[] = {0,0,1,-1,1,1,-1,-1};
    static int dy[] = {1,-1,0,0,1,-1,1,-1};
    static int w;
    static int h;
    static int cnt;
    static boolean[][] visit;
    static int[][] map ;

	public static void main(String[] args) throws IOException{
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        while(true){
        StringTokenizer tk = new StringTokenizer(bf.readLine());
         w = Integer.parseInt(tk.nextToken());
         h = Integer.parseInt(tk.nextToken());
        if(w == 0 && h==0)
            return;
		visit = new boolean[h][w];
		map = new int[h][w];
		
		// map 입력 받기
		for(int i=0;i<h;i++) {
            tk = new StringTokenizer(bf.readLine());
			for(int j=0;j<w;j++) {
				map[i][j] = Integer.parseInt(tk.nextToken());
			}
		}
		cnt = 0 ;
		
		for(int i=0;i<h;i++) {
			for(int j=0;j<w;j++) {
				if(map[i][j] == 1 && !visit[i][j]) {
					dfs(i,j);
                    cnt++;
				}
			}
		}
		System.out.println(cnt);
	}
    }
	
	public static void dfs(int x, int y) {
		visit[x][y] = true;
		
		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) {
				if(map[nx][ny] == 1 && !visit[nx][ny]) {
					dfs(nx,ny);
				}
			}
		}
	}

}

풀이

> 접근 방법과 동일.

> 대각선 까지 체크 되야하므로 주의

> 배열의 크기를 w,h순이아니라 h,w로 초기화 해줘야함.