[C++] 백준 14716번: 현수막

www.acmicpc.net/problem/14716

14716번: 현수막

그냥 전형적인 dfs/bfs문제였다. 섬 갯수 세는 문제와 매우 유사했다.

 

단, 4방향이 아닌 8방향을 고려하는 것만 조심하면 쉬운 문제였다.

 

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

queue<pair<int, int>> q;
int map[1000][250];
int ans, m, n;
int dx[8] = { -1,-1,-1,0,0,1,1,1 };
int dy[8] = { -1,0,1,-1,1,-1,0,1 };

void bfs(int x, int y) {
	q.push({ x, y });
	map[x][y] = 0;
	while (!q.empty()) {
		int a = q.front().first;
		int b = q.front().second;
		q.pop();
		for (int i = 0; i < 8; i++) {
			if (a + dx[i] >= 0 && a + dx[i] < m && b + dy[i] >= 0 && b + dy[i] < n
				&& map[a + dx[i]][b + dy[i]] == 1) {
				map[a + dx[i]][b + dy[i]] = 0;
				q.push({ a + dx[i], b + dy[i] });
			}
		}
	}
	ans++;
	return;
}

int main() {
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 1) {
				bfs(i, j);
			}
		}
	}
	cout << ans;
	return 0;
}