섹션 8 DFS, BFS - 13. 섬나라 아일랜드(BFS)

문제 설명

N×N 크기의 격자판으로 이루어진 섬나라 아일랜드의 지도가 주어진다.
각 칸은 1(섬) 또는 0(바다)로 구성되어 있고, 섬은 상하좌우 + 대각선 방향으로 연결된 1들의 묶음이다.
이때 섬의 개수를 구하는 프로그램을 작성하라.

---

입력 & 출력

입력

• 첫 줄에 정수 N (3 ≤ N ≤ 20)
• 다음 N줄에 N개의 0 또는 1로 이루어진 격자판

출력

• 섬의 개수 출력

예시 입력

7
1 1 0 0 0 1 0
0 1 1 0 1 1 0
0 1 0 0 0 0 0
0 0 0 1 0 1 1
1 1 0 1 1 0 0
1 0 0 0 1 0 0
1 0 1 0 1 0 0

 

예시 출력

5

---

해결 방법 (BFS)

• 이 문제는 BFS(너비 우선 탐색)을 활용해서 해결할 수 있다.
• 격자판 전체를 순회하며 아직 방문하지 않은 섬(1)을 발견하면 그 지점을 시작점으로 BFS 탐색을 수행한다.
• BFS는 Queue를 사용해 8방향(상하좌우 + 대각선)을 모두 탐색하며 섬 전체를 방문 처리한다.
• 방문한 칸은 0으로 바꿔 다시 방문하지 않도록 한다.

---

코드 구현

import java.util.*;

class Point {
	public int x, y;
	Point(int x, int y){
		this.x = x;
		this.y = y;
	}
}

public class Main {
	static int n, answer = 0;
	static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
	static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};

	public void BFS(int x, int y, int[][] board) {
		Queue<Point> q = new LinkedList<>();
		q.add(new Point(x, y));
		board[x][y] = 0;

		while(!q.isEmpty()) {
			Point tmp = q.poll();
			for(int i = 0; i < 8; i++) {
				int nx = tmp.x + dx[i];
				int ny = tmp.y + dy[i];
				if(nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] == 1) {
					board[nx][ny] = 0;
					q.add(new Point(nx, ny));
				}
			}
		}
	}

	public void solution(int[][] board) {
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				if(board[i][j] == 1) {
					answer++;
					BFS(i, j, board);
				}
			}
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		int[][] arr = new int[n][n];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		T.solution(arr);
		System.out.print(answer);
		sc.close();
	}
}

---

코드 설명

• dx, dy: 8방향 탐색을 위한 이동 벡터
• Point 클래스: 좌표 관리를 위한 간단한 구조체 역할
• BFS():
  • 큐를 사용해서 탐색을 진행
  • 인접한 섬들을 모두 탐색하고 방문한 곳은 0으로 바꿈
• solution():
  • 전체 맵을 순회하면서 아직 방문하지 않은 섬(1)을 발견하면 BFS 실행
  • BFS 한 번 = 섬 하나를 모두 탐색 → 섬 개수 증가

---

시간 복잡도 분석

• 격자 전체 순회 : O(n²)
• BFS에서 각 칸 방문 : O(n²)
• 총 시간 복잡도 : O(n²)

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런