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;
}

---

2024-07-12 문제를 다시 풀던 중,

BFS를 다르게 작성하여 푸는 과정에서 메모리 초과가 발생하였다

시도한 풀이는 BFS과정 외에는 다른점이 없었다

이전 풀이 방식

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));
		}

	}
}

• 방문했던 곳을 0으로 지우고, BFS를 시작한다
• 큐에 새로운 방문 가능한 구역을 넣기 전에 맵을 0으로 세팅하고 넣는다

새로 시도한 방식

void BFS(int yy, int xx) {
	queue<pair<int, int>> qu;
	qu.push(make_pair(yy, xx));

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

		map[now.first][now.second] = 0;

		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; 

			qu.push(make_pair(dy, dx));
		}
	}
}

• BFS를 시작하고 큐에서 원소를 꺼낼 때 마다 맵을 0으로 지운다
• 큐에 추가된 노드들이 중복 될 수 있다는 문제가 있다
  • 예를들어 [1,1]에서 [1,2]를 큐에 넣었는데,
    [1,3]에서도 [1,2]가 아직 1이라면 큐에 또 넣을 수 있는 문제가 발생할 수 있다
• 즉 이 방법은 중복된 노드가 큐에 많이 추가될 수 있으므로, 이 방법은 안쓰는게 좋겠다