[Algorithm] 섬의 개수

Jong Min ·2025년 4월 7일

Algorithm

목록 보기

22/30

🏝️ 섬의 개수 (백준 4963)

📌 문제 설명

정사각형으로 이루어진 지도에서 1은 땅, 0은 바다를 의미한다.
상하좌우뿐 아니라 대각선 방향으로도 연결된 땅은 하나의 섬으로 본다.
주어진 지도에서 섬이 총 몇 개인지 구하는 프로그램을 작성하라.

⛓️ 연결 조건

상, 하, 좌, 우
대각선(좌상, 우상, 좌하, 우하)

🛑 입력 종료 조건

0 0이 입력되면 프로그램은 종료된다.

🎯 입력 조건

지도의 너비 W, 높이 H (1 ≤ W, H ≤ 50)
이어서 H줄에 걸쳐 W개의 정수로 지도 정보가 주어짐 (0 또는 1)
여러 개의 테스트 케이스가 주어짐

📝 예제 입력 및 출력

💡 해결 방법

이 문제는 그래프 탐색(DFS or BFS) 을 통해 해결할 수 있습니다.
지도에서 1이 있는 좌표를 기준으로, 연결된 모든 땅을 방문 처리하며 섬의 개수를 세면 정답입니다.

방문한 땅은 0으로 바꾸어 중복 탐색을 방지합니다.
8방향 탐색을 통해 연결된 모든 땅을 하나의 섬으로 봅니다.

✅ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		while (true) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			int W = Integer.parseInt(st.nextToken());
			int H = Integer.parseInt(st.nextToken());
			
            // 무한 루프 탈출
			if (W == 0 && H == 0) {
				break;
			}
			
            // 입력
			int[][] 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());
				}
			}

			int count = 0;
            
            // 좌표가 1인 값을 찾는 반복문
			for (int i = 0; i < H; i++) {
				for (int j = 0; j < W; j++) {
					if (map[i][j] == 1) {
						dfs(map, i, j, H, W);
						count++;
					}
				}
			}

			System.out.println(count);
		}
	}

	static void dfs(int[][] map, int x, int y, int H, int W) {
		int[] dx = {-1, -1, -1, 0, 1, 1, 1, 0}; // 대각선, 가로, 세로 
		int[] dy = {-1, 0, 1, 1, 1, 0, -1, -1};

		map[x][y] = 0; // 방문 처리

		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 && map[nx][ny] == 1) {
				dfs(map, nx, ny, H, W);
			}
		}
	}
}