C++ / 2573 / 빙산 ( 깊이 우선 탐색 )

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

문제 요약

지구 온난화로 인하여 북극의 빙산이 녹고 있습니다.

빙산을 그림 1과 같이 2차원 배열에 표시한다고 합니다.

빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장됩니다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장됩니다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각합니다.

그림 1. 행의 개수가 5이고 열의 개수가 7인 2차원 배열에 저장된 빙산의 높이 정보

빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어듭니다다.

단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않습니다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있습니다.

따라서 그림 1의 빙산은 일년후에 그림 2와 같이 변형됩니다.

그림 3은 그림 1의 빙산이 2년 후에 변한 모습을 보여줍니다. 2차원 배열에서 동서남북 방향으로 붙어있는 칸들은 서로 연결되어 있다고 말합니다. 따라서 그림 2의 빙산은 한 덩어리이지만, 그림 3의 빙산은 세 덩어리로 분리되어 있습니다.

한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성해야합니다.

그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.

문제 풀이

어떻게 접근할까 하다가 정공법이라 생각하는 dfs로 접근하였습니다.

빙산의 개수를 세는 과정과, 빙산을 녹이는 과정 각각 2개가 필요하고,

그 2개의 진행 시간 ( 날짜 )를 세어주는 전체 과정이 필요합니다.

 

1. 빙산을 입력받습니다.

2. 빙산들을 복사해서 저장합니다.

3. 큰 while문을 만듭니다. ( 날짜를 세기 위함 )

4. while문 안에선 추후 빙산들을 재탐색 해야하기 때문에 방문 체크를 초기화 해주고, 빙산 개수를 셀 변수와 남아있는 빙산들( v[x][y] >0 다 녹았는지 확인 위해 )을 세어줄 변수를 초기화 합니다.

5. dfs 탐색으로 빙산 개수들을 세어줍니다. 

6. 빙산이 다 녹거나, 2개이상으로 분리되면 종료합니다.

7. 빙산을 녹이기 위해 함수를 만듭니다. 함수에선 현재 빙산의 각 칸별 4방향으로 바다를 세어주고 그 바다 개수만큼 임시 빙산에 빼줍니다.

8. 빙산이 0보다 작아지면 0으로 만듭니다.

9. 만들어진 임시 빙산  배열을 현재 빙산 배열으로 덮어 씌웁니다.

10. 날짜를 증가시킵니다.

11. 빙산이 다녹았는데도 개수가 2미만이면 0출력, 아니면 날짜를 출력합니다.

주의할 점

빙산을 녹이는 과정에서 현재 빙산에 바로 적용시키면 다음 칸에서 전칸이 바다가 되었을경우 그 칸까지 새게 됩니다.

모든 빙산칸이 동시에 주변 바다의 영향을 받아야 하기 때문에

현재 빙산 배열과 임시로 저장할 빙산 배열을 만들어 

현재 빙산  배열의 주변 바다의 개수만큼 빼서 임시 배열에 빙산에 입력해주었습니다.

 

아래 링크는 질문 게시판에  있는 반례입니다.

문제 풀면서 도움이 되었기에 첨부 합니다.

https://www.acmicpc.net/board/view/153496

코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

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

int n, m, cnt =0,t=0, ice = 0, top= 0;
vector<vector<int>>v, temp;
bool visit[301][301];
void dfs(int y, int x)
{
	visit[y][x] = true;
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny >= n || ny < 0 || nx >= m || nx < 0)
		{
			continue;
		}
		if (v[ny][nx] == 0)
		{
			continue;
		}
		if (visit[ny][nx])
		{
			continue;
		}
		visit[ny][nx] = true;
		dfs(ny, nx);
	}

}
void checkIce(int y, int x)
{
	// 4방향으로 빙산 주변 바다 탐색
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny >= n || ny < 0 || nx >= m || nx < 0)
		{
			continue;
		}
		// 바다 개수 증가
		if (v[ny][nx] == 0)
		{
			ice++;
		}
	}
}
int main()
{
	cin >> n >> m;
	v.resize(n, vector<int>(m));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m ; j++)
		{
			cin >> v[i][j];
		}
	}
	// 빙산 녹는걸 적용시킬 임시 빙산
	temp = v;
	while (top <= n*m) // 모든 빙산이 녹기 전 까지 반복
	{
		cnt = 0;  // 빙산 개수
		top = 0; // 남아 있는 빙산 개수
		memset(visit, 0, sizeof(visit));
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (!visit[i][j] && v[i][j] != 0)
				{
					dfs(i, j);
					cnt++;
				}
				else
				{
					top++;
				}
			}
		}
		// 빙산이 다 녹으면 반복문 종료
		if (top == n * m)
		{
			break;
		}
		// 빙산이 2개 이상으로 분리되면 종료
		if (cnt >= 2)
		{
			break;
		}

		// 빙산 녹이기
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (v[i][j] != 0)
				{
					// 주변 바다 개수
					ice = 0;
					// 주변 바다 개수 체크
					checkIce(i, j);

					// 빙산이 0보다 작아지면 0으로 초기화
					// 모든 빙산을 현재 기준으로 녹여야하기 때문에 현재 빙산 기준으로 임시 빙산들 만듬
					temp[i][j] = max(temp[i][j] - ice, 0);
				}
			}
		}
		// 만들어진 빙산들을 현재 빙산으로 덮어쓰기
		v = temp;
		// 날짜 증가
		t++;
	}
	// 빙산이 다 녹았는데도 빙산 개수가 2개 미만이면 0 출력
	if (cnt < 2)
	{
		cout << 0;
	}
	else
	{
		cout << t;
	}

	return 0;
}

예제 1

5 7
0 0 0 0 0 0 0
0 2 4 5 3 0 0
0 3 0 2 5 2 0
0 7 6 2 4 0 0
0 0 0 0 0 0 0

결과 1

예제 2

5 5
0 0 0 0 0
0 10 10 0 0
0 0 5 10 0
0 0 0 10 0
0 0 0 0 0

결과 2

예제 3

40 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0 
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0 
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 10 10 10 10 1 10 10 10 10 10 10 10 10 10 10 10 10 10 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
19

결과 3