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

#4963 섬의 개수
https://www.acmicpc.net/problem/4963

📝문제 포인트

가로, 세로, 대각선까지 하나의 섬으로 판단한다.
주어진 크기를 벗어나면 안된다

시작점이 주어지던 bfs dfs문제를 주로 접했던 나는
적잖이 당황했다

일단 의문이 생겼던 점

1. 대각선 떨어져 있는 곳을 어떻게 가는가 ?
: '상, 하, 좌, 우 + 대각선 네 방향'으로 갈 수 있는 값을 미리 준비해두고 bfs나 dfs를 또 진행하면 된다

2. 끝난건 어떻게 아는가 ?
: 범위 안에서 갈 곳이 없을 때 끝났다고 볼 수 있다

3. 시작점은 뭔데요 ??
: 정보가 들어있는 배열의 처음부터 끝까지 다 탐색하는 거고, 시작점은 graph[0][0]이 되더라..

4. 섬의 개수 세기
: dfs(bfs)를 진행하기 전에 개수를 세어줄 변수를 만든다(LandNum). dfs(bfs)가 한 번 진행되었다는건 그 점에서 갈 수 있는 주변은 다 돌았다는 말이다 !!! 새로운 점으로 dfs(bfs)를 진행해야 된다 => 섬의 개수를 세는 과정

✍코드

#include <iostream>
#include <string.h>
#include <queue>
#define MAX 50

using namespace std;
queue<pair<int,int>> q;
int w, h;
int LandNum=0;
bool visited[MAX][MAX];
int graph[MAX][MAX];
int cnt = 0;
//우 하 좌 상 우상 우하 좌상 좌하
int dw[8] = { 1,0,-1,0,1,1,-1,-1 };
int dh[8] = { 0,1,0,-1,-1,1,-1,1 };

void bfs(int h, int w) {
	visited[h][w] = true;
	q.push(make_pair(h, w));

	while (!q.empty()) {
		h = q.front().first;
		w = q.front().second;
		q.pop();

		for (int i = 0; i < 8; i++) {
			int nh = h + dh[i];
			int nw = w + dw[i];
			if (0 <= nw && 0 <= nh && nw < MAX && nh < MAX) {
				visited[nh][nw] = true;
				q.push(make_pair(nh, nw));
			}
		}
	}
}

void dfs(int h, int w) {
	visited[h][w] = true;
	for (int i = 0; i < 8; i++) {
		int nh = h + dh[i];
		int nw = w + dw[i];

		if (0 <= nw && 0 <= nh && nw < MAX && nh < MAX) {
			if (graph[nh][nw] && !visited[nh][nw]) {
				visited[nh][nw] = true;
				dfs(nh, nw);
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	while (1) {
		cin >> w >> h;
		if (w==0 && h==0) break;

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> graph[i][j];
			}
		}

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (graph[i][j] && !visited[i][j]) {
					LandNum++;
					bfs(i, j);
				}
			}
		}

		cout << LandNum << '\n';
		memset(graph, 0, sizeof(graph));
		memset(visited, false, sizeof(visited));
		LandNum = 0;
	}
}

다음엔 비슷한 문제도 풀 수 있겠지 ^^???
이번엔 전적으로 구글링에 의존했다.......속상..

참고 : https://jdselectron.tistory.com/53