백준 4963번 섬의 개수(JAVA)

by

백준 4963호

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

4963:섬의 수

'추천 관련글,

입력은 여러 테스트 케이스로 구성됩니다.

각 테스트 케이스의 첫 번째 줄은 맵의 너비 w와 높이 h를 제공합니다.

w와 h는 50보다 작거나 같은 양의 정수입니다.

두 번째 행부터 h-line은 카드입니다.

www.acmicpc.net



문제

지도의 크기를 입력하고 1(육지)과 0(바다)으로 분류된 값을 입력하여 섬의 개수를 세는 프로그램을 작성하세요.

섬은 가로, 세로 또는 대각선으로 연결된 직사각형입니다.

맵의 크기가 0이면 0을 입력하면 끝납니다.

입장

1. 지도의 크기 w, h를 받아 지도를 초기화함과 동시에 방문 여부를 나타내는 방문을 초기화합니다.

2. w,h를 입력하여 0.1을 얻음(배열 크기와 w,h는 역순임)

3. 총 8 dx,dy 를 말하여 가로, 세로, 대각선으로 확인합니다.

4. 각 꼭짓점을 방문하고 dfs로 1(land)을 사용하여 방문하지 않은 점을 방문하십시오. 방문할 때마다 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로 초기화되어야 합니다.