[백준 4963] 섬의 개수

문제 링크 : https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

격자상에서 dfs를 활용하여 푸는 문제이다

 

dfs를 사용하는 방식은 아래의 문제와 매우 유사하다

 

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

11724번: 연결 요소의 개수

위의 문제와 다른 점이라면 노드가 격자로 대체되었고

 

간선을 통한 이동이 인접한 격자를 통한 이동 이라는 점

---

main함수에서 격자의 모든 칸을 순회하며 땅이 발견되면 dfs를 호출한다

 

dfs 호출된 땅에서부터 인접한 땅들 (섬을 이루는 땅)

 

을 전부 바다로 바꿔준다

 

이런식으로 한번의 dfs가 main함수에서 호출되면

 

하나의 섬이 지도에서 지워진다

 

즉, main함수에서 dfs 호출 횟수가 섬의 갯수이다

---

#include <stdio.h>
#include <string.h>

int arr[55][55];
int n, m, cnt = 0;

// dfs를 재귀함수로 구현
void tamsek(int x, int y) {
	arr[x][y] = 0;	// 탐색한 땅은 물로 바꿈 (check 배열과 똑같은 기능)
	for (int i = 0; i < 3; i++) {	// 상하
		for (int j = 0; j < 3; j++) {	// 좌우
			int nx = x - 1 + i;	// 다음 격자의 x 좌표
			int ny = y - 1 + j;	// 다음 격자의 y 좌표
			// 범위 이탈했으면 탐색 안함
			if (nx == -1 || ny == -1 || nx == m || ny == n) continue;	

			if (arr[nx][ny]) {	// 새로운 땅이면 탐색
				tamsek(nx, ny);
			}
		}
	}
	return;
}

int main(void) {
	while (true) {
		cnt = 0;
		scanf("%d %d", &n, &m);
		if (n == 0 && m == 0)break;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				scanf("%d", &arr[i][j]);
			}
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (arr[i][j]) {
					tamsek(i, j);
					cnt++;
				}
			}
		}
		printf("%d\n", cnt);
	}
}