[BOJ] 2573 : 빙산

Question

---

Solution

• map을 입력받을때 newMap에도 같이 받아준다. (newMap은 years가 카운팅되며 빙하가 깎이는 map이다.)
• 현재 노드에서 다음 노드가 0이면 newMap 현재 노드에 -1을 해준다.
• dfs 탐색시 두 덩어리가 탐색되면 바로 종료시키고 years를 출력한다.
• while문으로 years 카운팅하며 초기화할때 map에 newMap을 입혀준다.

---

Cord

#include <iostream>
#include <memory.h>

#define MAX 301

using namespace std;

int n, m;
int years;

int map[MAX][MAX];
int newMap[MAX][MAX];
bool visited[MAX][MAX];

int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };

void dfs(int _x, int _y)
{
	visited[_y][_x] = true;

	for (int i = 0; i < 4; i++)
	{
		int nextX = _x + dx[i];
		int nextY = _y + dy[i];

		if (0 <= nextX && nextX < m && 0 <= nextY && nextY < n)
		{
			if (!visited[nextY][nextX] && map[nextY][nextX])
			{
				dfs(nextX, nextY);
			}
			else if (!map[nextY][nextX] && newMap[_y][_x] > 0)
			{
				newMap[_y][_x]--;
			}
		}
	}
}

int main()
{
	// 행과 열 : n x m
	cin >> n >> m;

	// 맵 입력
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			int temp;
			cin >> temp;
			map[i][j] = temp;
			newMap[i][j] = temp;
		}
	}

	while (true)
	{
		int cnt = 0;
		// dfs 실행
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (!visited[i][j] && map[i][j])
				{
					cnt++;

					if (cnt >= 2) { cout << years; return 0; }
					dfs(j, i);
				}
			}
		}

		if (cnt == 0) { cout << 0; return 0; }
		
		years++;
		// 초기화
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				map[i][j] = newMap[i][j];
			}
		}
		memset(visited, false, sizeof(visited));
	}

	return 0;
}

---

Result