백준 - 4963번 - 섬의 개수

4963번

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

public class Main{

	static boolean[][] check;
	static int[][] graph;
	static int[] dx = {0, 0, 1, -1, 1, -1, 1, -1};
	static int[] dy = {1, -1, 0, 0, 1, 1, -1, -1};
	static int n, m, count;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		while (true) {
			st = new StringTokenizer(bf.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());

			if (n == 0 && m == 0) {
				break;
			}

			graph = new int[m+1][n+1];
			check = new boolean[m+1][n+1];
			int[] land = new int[65];
			count = 0;

			for (int i = 1; i<=m; i++) {
				st = new StringTokenizer(bf.readLine());
				for (int j = 1; j<=n; j++) {

					graph[i][j] = Integer.parseInt(st.nextToken());
//					System.out.println(graph[i][j]);
				}
			}

			for (int i = 1; i<=m; i++) {
				for (int j = 1; j<=n; j++) {
					if (graph[i][j] == 1 && !check[i][j]) {
						count++;
						dfs(i, j);
					}
				}
			}

			System.out.println(count);
		}
	}

	static void dfs(int x, int y) {
		check[x][y] = true;

		for (int i = 0; i<8; i++) {
			int newX = x + dx[i];
			int newY = y + dy[i];
			if (newX > 0 && newY >0 && newX <= m && newY <= n) {
				if (graph[newX][newY] == 1 && !check[newX][newY]) {
					dfs(newX, newY);
				}
			}
		}
	}

}

풀이

---

0과 1로 표현한 2차원 배열에서 상 하 좌 우 대각선까지 1이 있다면 섬으로 보고 섬이 몇개 주어졌는지 구하는 문제다.

저번에 상 하 좌 우를 판별하는 문제를 풀었어서 거기에 대각선을 나타내줄 수 있게 변형하여 간단하게 탐색할 수 있었다.

static int[] dx = {0, 0, 1, -1, 1, -1, 1, -1};
static int[] dy = {1, -1, 0, 0, 1, 1, -1, -1};