[백준]2573번 빙산 - C/C++

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

2573번: 빙산

문제

지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.

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

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

빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 따라서 그림 1의 빙산은 일년후에 그림 2와 같이 변형된다.

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

		2	4	1
	1		1	5
	5	4	1	2

그림 2

			3
				4
	3	2

그림 3

한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.

입력

첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.

출력

첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.

---

 

1. 빙산이 녹고

2.  덩어리 확인

두 단계를 진행하면 되는 문제였다. 

 

1. 녹이기 과정에서 반복문으로 순차적으로 빙산을 녹여 한 지점이 녹게 되어 다른 빙산에 영향을 줄 수도 있다는 점이다. 그렇기 때문에 배열을 복사해두고 복사해둔 배열로 값을 조정한 다음 원본에다가 다시 옮기는 방식을 활용해야 한다.

 

2. 덩어리 확인은 DFS로 동일 한 덩어리들을 체크하는 방식으로 진행하여 방문하지 않은 빙산인 지점만 DFS를 호출하여 단 한 번만 진행되는 경우에만 다음번 tick으로 넘어가면 된다. 

#include <iostream>
#include <string.h>

using namespace std;
int mat[301][301] = { 0 };
int temp[301][301] = { 0 };
bool vis[301][301] = { 0 };

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

int n, m,tick=0;

void melt() {
	for (int i = 1; i < n-1 ; i++) {
		for (int j = 1; j < m - 1; j++) {
			temp[i][j] = mat[i][j];
			vis[i][j] = false;
		}
	}
	for (int i = 1; i < n-1; i++) {
		for (int j = 1; j < m - 1; j++) {
			for (int k = 0; k < 4; k++) {
				if (!mat[i + dx[k]][j + dy[k]]) {
					temp[i][j] -= 1;
				}
			}
		}
	}
	for (int i = 1; i < n - 1; i++) {
		for (int j = 1; j < m - 1; j++) {
			mat[i][j] = temp[i][j];
			if (mat[i][j] < 0) mat[i][j] = 0;
		}
	}
}

void dfs(int x, int y) {
	vis[x][y] = true;

	for (int k = 0; k < 4; k++) {
		if(mat[x + dx[k]][y + dy[k]] && !vis[x + dx[k]][y + dy[k]])
			dfs(x + dx[k], y + dy[k]);
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> mat[i][j];
		}
	}
	while (1) {
		bool flag= false;
		int chunk = 0;

		tick++;
		melt();

		for (int i = 1; i < n - 1; i++) {
			for (int j = 1; j < m - 1; j++) {
				if (mat[i][j] && !vis[i][j]) {
					dfs(i,j);
					chunk++;
				}
			}
		}
		if (chunk == 0) {
			tick = 0;
			break;
		}
		else if (chunk >= 2) break;
		
	}
	cout << tick;
	return 0;
}

---

    처음에는 DFS를 위해 vis 배열과 같은 덩어리 인지 확인하기 위해 mark 배열을 활용하였다. DFS를 단 한번만 호출하기 위해 배열에서 첫 빙산인 지점에서 DFS 를 진행하여 인접한 빙산들을 mark 한 다음 첫 빙산부터 다시 반복문을 돌아가며 빙산이지만 mark 되지 않은 지점이 있으면 두 덩어리로 나누어졌다고 생각했다. 이렇게 주어진 예시와 질의응답의 반례들을 쉽게 통과했지만 테스트 케이스가 계속 6%에서 틀렸다고 나왔다. 구글링을 조금 해보았는데 다른 사람들은 vis 배열 하나만 쓰길래 생각해 보았더니 vis와 mark 둘이 같은 일을 하는 것 같아 코드를 고치고 ( 시작 지점 찾기 -> DFS -> mark 안되어 있는 지점 찾기) 였는데 그냥 반복문 한 번에 DFS로 덩어리를 찾을 수 있긴 했다. 이렇게 코드를 바꾸니 성공하였다. 하지만 이전 코드와 논리적으로 같은 것 같은데 이전 코드는 왜 안됐는지 잘 모르겠다.

    반례를 찾는 능력이 조금 떨어지는 것 같다. 코드를 짜는 중간에 이상한 부분이 느껴지면 그 부분을 고려해서 짤 수 있겠는데 코드를 완성하고 나면 반례를 찾기가 너무 힘들다. 내가 잘 캐치하지 못하는 반례의 유형이 있나 생각해보아야겠다!

   

    종강을 하고 1일 1 백준만 하며 잘 쉬고 있다. 다음 주 부터는 1일 1백준 말고도 다른 공부를 좀 해보아야 할 것 같다. 시도해 볼 만한 것들로는 

- 자바 공부하기

- 현업의 분야에 대해 알아보기

- 혼자 앱 만들어 보기

- 팀으로 앱 만들어 보기

- SWEA 한번 더하기

정도 생각이 나는데 생각을 좀 해봐야겠다!