[백준/C++] 4963번: 섬의 개수

문제

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

4963번: 섬의 개수

---

문제 요약

정사각형으로 이루어져 있는 섬과 바다 지도가 주어졌을 때, 섬의 개수를 출력한다.

 

한 정사각형과 가로, 세로, 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다.

---

코드

#include <iostream>
#include <cstring>
using namespace std;

// board는 입력 받은 지도 (섬: 1, 바다: 0)
// visit은 방문 여부를 체크한  지도 (방문함: 1, 방문하지 않음: 0)
int board[50][50], visit[50][50]; 

// 이동할 수 있는 방향 배열
int dx[8] = { 0, 0, 1, -1, 1, -1, 1, -1 };
int dy[8] = { 1, -1, 0, 0, 1, -1, -1, 1 };

int w, h, cnt;

// dfs 탐색
void dfs(int x, int y) {
	for (int d = 0; d < 8; d++) {
		int nx = x + dx[d];
		int ny = y + dy[d];

		if ((0 <= nx && nx < h) && (0 <= ny && ny < w) && !visit[nx][ny] && board[nx][ny]) {
			visit[nx][ny] = 1;
			dfs(nx, ny);
		}

	}
}

int main() {

	while (true) {
		cnt = 0;
		cin >> w >> h;

		// 종료 조건
		if (!w && !h) break;

		// 입력 받은 값 board에 저장
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> board[i][j];
			}
		}

		// 완전 탐색으로 방문하지 않은 땅을 모두 확인하여 dfs탐색
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (!visit[i][j] && board[i][j]) {
					visit[i][j] = 1;
					dfs(i, j);
					cnt++;
				}
			}
		}

		cout << cnt << endl;
		memset(visit, 0, sizeof(visit)); // 배열을 0으로 초기화 (cstring 필요)
	}
	return 0;
}

---

코드 설명

1. 지도의 정보를 2차원 배열 board에 입력 받는다.

 

2. 완전 탐색을 이용해 방문하지 않은 땅을 모두 확인하여 dfs탐색을 진행한다.

 

3 - 1. 어떤 땅에서부터 한 번 dfs을 진행할 때마다 이동할 수 있는 칸들은 모두 방문한 것으로 체크되므로, 결과값을 1개 출력한다.

 

3 - 2. 탐색을 한 번 종료되면 방문을 체크한 배열을 다시 초기화한다.

+ memset을 이용한다. (cstring include가 필요하다.)

 

4. 결과값을 출력한다.