[ 백준 / 2573 ] 빙산 (C++)

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

 

난이도 : 골드 4 
알고리즘 유형 : 구현, BFS 
풀이 시간 : 32분 

문제 풀이 

빙산의 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하자.

 

문제는 매 해마다 두가지 동작을 반복한다.

1. 빙산이 두 덩어리로 분리되었는지 체크(BFS)

2. 빙산의 녹는 정도 계산(구현)

 

먼저, 빙산이 두 덩어리로 분리되었는지 체크하기 위해서는 BFS를 사용할 것이다. 빙산이 아직 떨어지지 않았다면 BFS는 한 번만 실행하고 끝날 것이다. 하지만, 만약 BFS를 한 번 실행했는데도 불구하고 또다른 BFS를 실행한다면, 이는 두 덩어리로 갈라졌다는 의미이기 때문에 즉시 answer를 return하면 된다.

문제의 조건 중 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다. 라는 조건이 있다. 이를 판단하는 것은 간단하다. 그냥 BFS를 한 번도 실행하지 않은 경우가 된다. 이 경우에는 0을 리턴해주면 된다.

 

두번째로, 빙산의 녹는 정도를 계산해야 한다. 주의해야 할 점은 빙산은 동시에 녹는다는 점이다. 따라서, 새로운 정적 배열을 하나 생성해둔 뒤, 값을 복사하고, 배열을 녹인 뒤 다시 원래 배열에 복사하는 방식을 거쳐야 한다. 

이 과정에서 바다와 인접한 빙산들에 대해서 동적 배열에 넣어 처리하는 방법도 존재한다. 하지만, 동적 메모리를 할당하는 시간과 별 차이가 없기 때문에, 정적 배열에 모든 빙산을 체크하는 방법을 사용해도 무방하다.

 

시간복잡도는 최악의 경우, $O(n * m * 4)$만큼 소요된다.

 

코드

/*
빙산

바닷물과 접해있는 면 만큼 줄어든다.
빙산이 두 덩어리 이상으로 분리되는 최초의 시간을 구하기
전부 다 녹을 때까지 분리되지 않으면 0 출력

풀이 : 빙산 가장자리 저장
시간 지난 뒤 전체에 대해 bfs
*/

#include <iostream>
#include <queue>
#include <iostream>
#include <cstring>

using namespace std;

int n, m;
int grid[301][301];
int visited[301][301];

int dr[4] = { 0, 1, 0, -1 };
int dc[4] = { 1, 0, -1, 0 };


bool isValid(int r, int c) {
	return 0 <= r && r < n && 0 <= c && c < m;
}


void bfs(int sr, int sc) {
	queue<pair<int, int>> q;
	q.push({ sr, sc });
	visited[sr][sc] = 1;

	while (!q.empty()) {
		int r = q.front().first;
		int c = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++) {
			int nr = r + dr[d], nc = c + dc[d];
			if (isValid(nr, nc) && !visited[nr][nc] && grid[nr][nc]) {
				q.push({ nr, nc });
				visited[nr][nc] = 1;
			}
		}
	}
}


void check_side() {
	int new_grid[301][301] = { 0, };

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			new_grid[i][j] = grid[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (grid[i][j]) {
				int melt = 0;
				for (int d = 0; d < 4; d++) {
					int ni = i + dr[d], nj = j + dc[d];
					if (isValid(ni, nj) && !grid[ni][nj])
						melt++;
				}
				new_grid[i][j] -= melt;
				if (new_grid[i][j] <= 0) 
					new_grid[i][j] = 0;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			grid[i][j] = new_grid[i][j];
		}
	}
}


void init() {
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			cin >> grid[i][j];
	}
}


int solution() {
	int answer = 0;

	while (1) {
		
		// 겹치는 빙산 찾기
		int separate = 0;
		int endflag = 1;
		memset(visited, 0, sizeof(visited));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (!visited[i][j] && grid[i][j]) {
					if (separate)
						return answer;
					bfs(i, j);
					separate = 1;
					endflag = 0;
				}
			}
		}
		if (endflag)
			return 0;
		answer++;

		// 빙산 가장자리 체크
		check_side();

	}


	return answer;
}


int main() {
	init();
	cout << solution() << '\n';
	return 0;
}

배운 점 

최적화를 계속 고민했지만, 일단 타임어택을 목표로 했기 때문에 그냥 풀어냈다.

시간 최적화를 시키는 경우에 대해 항상 먼저 고민을 하면서 문제를 풀어나가야겠다..