[구름 알고리즘 먼데이 챌린지] Week5 : 1. 개미와 진딧물

문제

한 변의 길이가 N인 정사각형 모양의 평면에 진딧물 집과 개미 집이 있다. 개미 집은 고유의 영역 범위 안의 모든 진딧물에게서 수액을 수집한다. 이 수액이 없으면, 개미 집은 부족한 식량으로 제거된다.

길이가 4인 정사각형 평면을 1*1 크기의 작은 정사각형으로 나누면 아래와 같은 그림으로 표현할 수 있다.

위와 같은 상태로 arr[i][j] 값들이 주어진다. arr[i][j]의 값은 0, 1, 2 중 하나이며, 1 은 개미 집이고, 2는 진딧물이다. 아래 조건에 따라 개미 집은 제거된다.

●arr[i][j]이 개미 집 이라면, M칸 안에 진딧물이 없을 때 제거된다.

●이때 거리를 측정하는 방법은 상하좌우 인접한 칸으로 한 번 이동할 때 마다 1칸 움직인 것으로 한다.

위의 규칙에 따라 개미 집이 제거되었을 때, 남아있는 개미 집의 개수를 출력하시오.

 

전형적인 BFS 문제이다. 초기 개미 집과 진딧물의 상태를 board에 입력 받을 시 개미 집들의 좌표를 antHoust에 미리 저장해 두고 이 후, 개미 집들에서 BFS 수행 탐색을 통해 M간 안에 진딧물 여부로 해당 개미 집의 생존, 파괴를 판단하도록 구현했다.

#include <iostream>
#include <queue>
using namespace std;

int n, m, board[101][101], ans;
int dir[2][4] = { {-1, 1, 0, 0}, {0, 0, -1, 1 } };

void bfs(int y, int x) {
	vector<vector<int>> visited(n, vector<int>(n, 0));
	int cy, cx, ny, nx;
	queue<pair<int, int>> q;
	visited[y][x] = 1;
	q.push({ y, x });
	while (!q.empty()) {
		cy = q.front().first;
		cx = q.front().second;
		q.pop();
		if (visited[cy][cx] <= m + 1 && board[cy][cx] == 2) {
			ans++;
			break;
		}
		if (visited[cy][cx] > m) continue;
		for (int i = 0; i < 4; i++) {
			ny = cy + dir[0][i];
			nx = cx + dir[1][i];
			if (ny < 0 || ny > n - 1 || nx < 0 || nx > n - 1)continue;
			if (visited[ny][nx]) continue;
			visited[ny][nx] = visited[cy][cx] + 1;
			q.push({ ny, nx });
		}
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	vector<pair<int, int>> antHouse;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];
			if (board[i][j] == 1) antHouse.push_back({ i, j });
		}
			
	for (int i = 0; i < antHouse.size(); i++) 
		bfs(antHouse[i].first, antHouse[i].second);
	
	cout << ans;
}