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

문제 설명

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

---

해결 방법

이 문제는 DFS(깊이 우선 탐색)를 활용하여 해결할 수 있다.

• 지도 전체를 순회하면서 아직 방문하지 않은 섬(1)을 발견하면 섬의 개수를 1 증가시킴
• 그 좌표부터 8방향(상하좌우 + 대각선)으로 연결된 1들을 DFS를 통해 재귀적으로 방문 처리
• 방문한 섬은 0으로 바꿔서 다시 방문하지 않도록 처리함

---

코드 구현

public class Problem13 {
	static int n, answer = 0;
	static int[][] arr;
	static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
	static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
	
	public void DFS(int x, int y, int[][] board) {
		for(int i=0; i<8; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] == 1) {
				board[nx][ny] = 0;
				DFS(nx, ny, board);
			}
		}
	}
	
	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++;
					board[i][j] = 0;
					DFS(i, j, board);
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Problem13 T = new Problem13();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		arr = new int[n][n];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				arr[i][j] = kb.nextInt();
			}
		}
		T.solution(arr);
		System.out.println(answer);
		kb.close();
	}
}

---

코드 설명

• dx, dy 배열로 8방향 탐색을 가능하게 구성
• DFS에서 방문한 섬은 0으로 바꿔 방문 처리
• solution()에서 전체 격자판을 순회하면서 1을 만나면 DFS 시작
• main()에서는 입력을 받고, solution() 호출 후 결과 출력

---

시간 복잡도 분석

• 최악의 경우 격자판 전체 탐색: O(N^2)
• DFS는 각 섬에 대해 한 번만 수행됨 → 실질적으로 O(N^2) 내에서 충분히 수행 가능

---

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

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

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