[백준] 4963번 섬의 개수

4963번: 섬의 개수

왼쪽 오른쪽 위 아래 뿐만 아니라 대각선까지 되는 DFS, BFS 문제는 처음 봤다. 하지만 푸는 방법은 똑같으니 쉽게 풀 수 있었다.

#include <iostream> 
#include <vector> 
#include <queue> 
#include <tuple>
#include <algorithm>
using namespace std;

int main() {
	while (true) {
		int w, h;
		cin >> w >> h;
		if (w == 0 && h == 0) break;
		vector<vector<int>> v(h);
		vector<vector<bool>> visited(h);
		for (int i = 0; i < h; i++) {
			v[i] = vector<int>(w);
			visited[i] = vector<bool>(w);
		}
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> v[i][j];
			}
		}
		int count = 0;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (v[i][j] == 1 && !visited[i][j]) {
					count++;
					queue<pair<int, int>> q;
					q.push(make_pair(i, j));
					while (!q.empty()) {
						pair<int, int> cur = q.front();
						q.pop();
						if (!visited[cur.first][cur.second]) {
							visited[cur.first][cur.second] = true;
							if (cur.first + 1 < h && cur.second + 1 < w && !visited[cur.first + 1][cur.second + 1] && v[cur.first + 1][cur.second + 1] == 1) {
								q.push(make_pair(cur.first + 1, cur.second + 1));
							}
							if (cur.first + 1 < h && cur.second - 1 >= 0 && !visited[cur.first + 1][cur.second - 1] && v[cur.first + 1][cur.second - 1] == 1) {
								q.push(make_pair(cur.first + 1, cur.second - 1));
							}
							if (cur.first - 1 >= 0 && cur.second + 1 < w && !visited[cur.first - 1][cur.second + 1] && v[cur.first - 1][cur.second + 1] == 1) {
								q.push(make_pair(cur.first - 1, cur.second + 1));
							}
							if (cur.first - 1 >= 0 && cur.second - 1 >= 0 && !visited[cur.first - 1][cur.second - 1] && v[cur.first - 1][cur.second - 1] == 1) {
								q.push(make_pair(cur.first - 1, cur.second - 1));
							}
							if (cur.first + 1 < h && !visited[cur.first + 1][cur.second] && v[cur.first + 1][cur.second] == 1) {
								q.push(make_pair(cur.first + 1, cur.second));
							}
							if (cur.first - 1 >= 0 && !visited[cur.first - 1][cur.second] && v[cur.first - 1][cur.second] == 1) {
								q.push(make_pair(cur.first - 1, cur.second));
							}
							if (cur.second + 1 < w && !visited[cur.first][cur.second + 1] && v[cur.first][cur.second + 1] == 1) {
								q.push(make_pair(cur.first, cur.second + 1));
							}
							if (cur.second - 1 >= 0 && !visited[cur.first][cur.second - 1] && v[cur.first][cur.second - 1] == 1) {
								q.push(make_pair(cur.first, cur.second - 1));
							}
						}
					}
				}
			}
		}
		cout << count << endl;
	}
	return 0;
}