백준 4963 : 섬의 개수 (BFS)

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

1.접근

• 단지번호 붙이기와 마찬가지로, BFS 탐색을 사용한다. (DFS 사용해도 무관)
• ★ 높이가 h, 너비가 m이지만 배열의 최댓값은 i가 h, j가 m 이다.
  (이것때문에 한참 더 걸렸다..)
• BFS의 경우 Queue를 사용하게 되면서 추가 메모리를 쓰게 되어 메모리 초과 에러가 날 수 있다. 따라서 MAX 값을 50으로 설정해야 한다.(51로 했다가 메모리 초과를 겪음)

2. 나의 풀이

#include <iostream>
#include <queue>
#define MAX 50
using namespace std;

int w, h;
bool graph[MAX][MAX];
bool visited[MAX][MAX];
queue<pair<int, int>> q;

void init() {
	for (int i = 0; i < h; i++) {
		for (int j = 0; j <w; j++) {
			visited[i][j] = false;
			graph[i][j] = false;
		}
	}
}

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

	while (!q.empty()) {
		x = q.front().first;
		y = q.front().second;
		q.pop();

		if (y > 0 && graph[x][y - 1] && !visited[x][y - 1]) { //상
			visited[x][y - 1] = true;
			q.push(make_pair(x, y - 1));
		}
		if (y <w-1 && graph[x][y +1] && !visited[x][y +1]) { //하
			visited[x][y + 1] = true;
			q.push(make_pair(x, y +1));
		}
		if (x > 0 && graph[x - 1][y] && !visited[x - 1][y]) { //좌
			visited[x - 1][y] = true;
			q.push(make_pair(x-1, y));
		}		
		if (x < h-1 && graph[x + 1][y] && !visited[x + 1][y]) { //우
			visited[x + 1][y] = true;
			q.push(make_pair(x + 1, y));
		}
		if (x < h-1 &&y>0&& graph[x + 1][y-1] && !visited[x + 1][y-1]) { //오른쪽위
			visited[x + 1][y - 1] = true;
			q.push(make_pair(x + 1, y-1));
		}
		if (x < h &&y<w-1 && graph[x + 1][y + 1] && !visited[x + 1][y +1]) { //오른쪽아래
			visited[x + 1][y + 1] = true;
			q.push(make_pair(x + 1, y + 1));
		}
		if (x >0 &&y >0 && graph[x - 1][y - 1] && !visited[x - 1][y -1]) { //왼쪽위
			visited[x - 1][y - 1] = true;
			q.push(make_pair(x - 1, y -1));
		}
		if (x > 0 && y<w-1 && graph[x - 1][y + 1] && !visited[x - 1][y + 1]) { //왼쪽아래
			visited[x - 1][y + 1] = true;
			q.push(make_pair(x - 1, y + 1));
		}
	}
}


int main() {

	while (1) {
		cin >> w >> h;
		if (w == 0 && h == 0) return 0;
		init();
		for (int i = 0; i < h; i++) { //섬 입력
			for (int j = 0; j < w; j++) {
				cin >> graph[i][j];
			}
		}

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


	return 0;
}

3. 다른 사람의 풀이

https://hunidev.tistory.com/4
BFS와 DFS를 모두 구현한 예시

나처럼 if 조건문을 사용해서 인접한 경우를 구하지 않고,
배열의 값에 x값과 y값의 변화를 저장해놓고 반복문을 사용하여 풀었다.
훨씬 간결하고 좋은듯