[백준]4963번 섬의 개수(JAVA)

0. 문제 링크

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

4963번: 섬의 개수

 

1. 문제 설명

1) 한 정사각형에서 다른 정사각형으로 가로, 세로, 대각선으로 걸어갈 수 있으면 같은 섬

2) 섬의 개수 출력하기

 

2. 입출력

// input
1 1 // 너비 w, 높이 h
0 // 지도
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 // 종료

// output
0
1
1
3
1
9

 

3. 코드

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

public class b4963 {
	static int[] dr = {-1, -1, 0, 1, 1, 1, 0, -1};
	static int[] dc = {0, 1, 1, 1, 0, -1, -1, -1};
	private static int w;
	private static int h;
	private static int[][] map;
	private static boolean[][] v;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();
		int t = 1; // 테스트 케이스
		
		while(true) {
			st = new StringTokenizer(br.readLine());
			w = Integer.parseInt(st.nextToken()); // 너비
			h = Integer.parseInt(st.nextToken()); // 높이
			if(w == 0 && h == 0) break; // 0 0이 주어지면 끝
			map = new int[h][w]; // 지도
			for (int i = 0; i < h; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < w; j++) {
					map[i][j] = Integer.parseInt(st.nextToken()); // 1은 땅, 0은 바다
				}
			}
			v = new boolean[h][w]; // 방문 여부
			int ans = 0; // 섬의 개수
			
			for(int i = 0; i < h; i++) { // 탐색
				for(int j = 0; j < w; j++) {
					if(!v[i][j] && map[i][j] == 1) {
						v[i][j] = true;
						dfs(i, j);
						ans++;
					}
				}
			}
			
			sb.append(ans + "\n"); // 섬의 개수 출력
			t++; // 테스트 케이스 개수 추가
		}
		System.out.println(sb.toString());
	}

	private static void dfs(int r, int c) {
		// basis part
		
		// inductive part
		for (int d = 0; d < 8; d++) { // 8방탐색
			int nr = r + dr[d];
			int nc = c + dc[d];
			if(nr >= 0 && nr < h && nc >= 0 && nc < w && !v[nr][nc]) {
				if(map[nr][nc] == 1) {
					v[nr][nc] = true;
					dfs(nr, nc);
				}
			}
		}
	}

}

실행 결과

 

4. 회고

1) 테스트 케이스가 주어지지 않고 마지막에 0 0이 입력되는 것을 통해 테스트 케이스의 개수를 세고, 입력을 닫아야 함

2) 바다가 아닌 땅인 부분에 대해 8방탐색을 통해 갈 수 있는 곳이 있는지 판단한 후 섬의 개수를 1개씩 추가

 

5. Github

https://github.com/iihye/Algorithm/blob/main/Baekjoon/b4963.java