[BOJ] 2573_빙산 with cpp

# 생각

영역구하기 처럼 이중 for문으로 bfs 탐색을 돌려

빙산이 이어져있는지 나눠져 있는지 영역의 개수를 구할 수 있다

빙산이 분리되는 최초의 시간을 출력해야 하므로 영역의 개수가 2가 되는 순간

시간을 출력하고 종료하면 된다

 

단, 각 정점마다 녹아서 줄어들게끔 하면 안되므로 tmp를 새로 선언하여

graph를 복사한 값으로 녹는 부분을 실행해주고 원본에 다시 저장해주면 된다

 

 

# 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
bool OOB(int x, int y, int n, int m) { return x < 0 or x >= n or y < 0 or y >= m; }

int N, M;
int graph[333][333], vis[333][333];

void input()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> graph[i][j];
		}
	}
}
void bfs(int i, int j)
{
	queue<pair<int, int>> q;
	vis[i][j] = 1;
	q.push({ i,j });
	while (!q.empty())
	{
		int x, y;
		tie(x, y) = q.front();
		q.pop();
		for (int dir = 0; dir < 4; dir++)
		{
			int nx = x + dx[dir], ny = y + dy[dir];
			if (OOB(nx,ny,N,M) or vis[nx][ny] == 1 or graph[nx][ny] == 0) continue;
			vis[nx][ny] = 1;
			q.push({ nx,ny });
		}
	}
}
void melt()
{
	int tmp[333][333] = {};
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (graph[i][j] == 0) continue;
			int cnt = 0;
			for (int dir = 0; dir < 4; dir++)
			{
				int nx = i + dx[dir], ny = j + dy[dir];
				if (graph[nx][ny] == 0) cnt++;
			}
			tmp[i][j] = max(0, graph[i][j] - cnt);
		}
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			graph[i][j] = tmp[i][j];
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	input();
	int year = 0;
	while (true)
	{
		int state = 0;
		for (int i = 0; i < N; i++)
		{
			fill(vis[i], vis[i] + M, 0);
		}
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				if (graph[i][j] != 0 and vis[i][j] == 0)
				{
					state++;
					bfs(i, j);
				}
			}
		}
		if (state == 0) { cout << 0; break; }
		if (state >= 2) { cout << year; break; }
		melt();		
		year++;
	}
}

 

---

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

2573번: 빙산