4963 섬의 개수

4963 섬의 개수

4방향 탐색이 아닌 8방향 탐색문제

대각선으로도 이동할 수 있다

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

1. 문제

---

간단 설명

섬의 개수를 세는 문제

기존의 2667 단지번호붙이기 문제가

4방향으로만 체크 가능했다면

이 문제는 대각선도 같은 덩어리로 판별한다

그것만 제외하면 완전 같은 문제

2. 문제 분석

---

필요변수

• 높이 int h, 너비 int w
• 최대 크기 50인 맵 int map[51][51] . 방문 배열은 따로 사용하지 않고 map에 바로 처리했음
• 8방향을 표시할 변수 int direct[8][2]
• BFS 탐색을 위한 Queue
• BFS를 몇번 돌렸는지 = 섬의 덩어리가 몇개인지 체크할 int cnt

주의점

• w, h가 0 0 일때 반복문을 종료한다
• 8방향이므로 BFS에서 for문을 4번이 아닌 8번 돌린다.

알고리즘

1. w, h 를 입력받는다
	1-1. w, h가 0, 0 이면 종료한다
2. 기존의 맵을 모두 0으로 초기화한다
3. 맵의 각 셀 정보를 입력받는다.
4. 2중 For문을 통해 셀이 1인 곳을 찾아 그 지점부터 BFS를 시작한다
	4-1. BFS를 통해 연결된 섬들을 맵에서 0으로 만든다
		4-1-1. 큐에 시작 지점을 넣고, map 배열에서 방문처리한다 (0으로 덮어씌움)
		4-1-2. 큐가 빌때까지 탐색을 계속한다
			4-1-2-1. 큐의 맨 앞을 꺼낸다
			4-1-2-2. 8방향으로 탐색한다
			4-1-2-3. 경계를 벗어났다면 패스
			4-1-2-4. 바다라면 패스
			4-1-2-5. 위 조건들을 통과했다면, 방문처리하고, 큐에 삽입한다
	4-2. BFS가 종료되면 섬의 개수를 + 1 해준다

3. 소스코드

---

#include <iostream>
#include <queue>
#include <string.h> // for memset

#define MAX 51

using namespace std;

int w, h;
int map[MAX][MAX];
int direct[8][2] = {  // ← ↑ → ↓ 순으로 시도하고, ↖ ↗ ↙ ↘ 순으로 시도한다
	{0,-1},
	{-1,0},
	{0,1},
	{1,0}, 
	{-1,-1}, 
	{-1,1}, 
	{1,-1}, 
	{1,1} 
};

void BFS(int y, int x) {
	queue< pair<int, int> > qu;
	map[y][x] = 0;
	qu.push(make_pair(y, x));

	while (!qu.empty()) {
		pair<int, int> now = qu.front();
		qu.pop();

		for (int t = 0; t < 8; t++) {
			int dy = direct[t][0] + now.first;
			int dx = direct[t][1] + now.second;
		
			if (dy < 0 || dx < 0 || dy >= h || dx >= w) continue;
			if (map[dy][dx] == 0) continue;

			map[dy][dx] = 0;
			qu.push(make_pair(dy, dx));
		}

	}
}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	while (1) {
		// 0. 각 변수 초기화
		memset(map, 0, sizeof(map));

		cin >> w >> h;
		if (w == 0 && h == 0) break;

		// 1. 입력
		for (int y = 0; y < h; y++) {
			for (int x = 0; x < w; x++) {
				cin >> map[y][x];
			}
		}


		// 2. BFS로 섬의 개수 체크
		int cnt = 0;
		for (int y = 0; y < h; y++) {
			for (int x = 0; x < w; x++) {
				if(map[y][x] == 1){
					BFS(y, x);
					cnt++;
				}
			}
		}

		cout << cnt << '\n';
	}

	return 0;
}