BOJ 2573 빙산

📎Problem Link

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

2573번: 빙산

 

📋 문제 정리

• 각 칸에는 빙산의 각 부분별 높이 정보가 저장됨. 0은 바다를 뜻함.
• 1년 마다 줄어드는 빙산의 높이 : 상하좌우로 접해있는 바다 면 수
• 아무리 줄어들어도 0보다 더 줄어들진 않는다.
• 첫 줄에는 이차원 배열의 행과 열을 나타내는 N, M 입력 (3 ≤ N ≤ 300)
• 그 다음부터 N개의 줄에는 빙산의 높이 입력
• 빙산 덩어리가 최소 2개 이상으로 쪼개지는 최소 시간(년) 구하기

📌 예제 1

예제를 그림으로 나타내면 다음과 같다.

 

🧐 Idea

• DFS 함수로 전체를 한번 훑을 때 마다 각 칸 주변의 바다를 계산해서 -계산하기
• 전체 훑어보면서 빙산 덩어리 수와 년 수 계산하기
• 덩어리 수가 2 이상이 되면 모든 계산을 바로 종료하고 현재 년 수 출력하기 

---

💻 Code

int main() {
	map iceberg;
	int iceberg_count, year_count = 0;

	cin >> iceberg.N >> iceberg.M;

	for (int i = 0; i < iceberg.N; i++) {
		for (int j = 0; j < iceberg.M; j++) {
			cin >> iceberg.board[i][j];
		}
	} // 빙산 입력

	while (1) {
		iceberg_count = 0; 
		for (int i = 0; i < iceberg.N; i++) {
			for (int j = 0; j < iceberg.M; j++) {
				if (iceberg.board[i][j] && !iceberg.visited[i][j])
				{
					iceberg.visited[i][j] = true;
					iceberg.Timepass(i, j);
					iceberg_count++;
				}
			}
		}
		if (iceberg_count >= 2) 
		{
			cout << year_count; 
			return 0; 
		}
		else if (iceberg_count == 0) { 
			cout << 0;
			return 0;
		}

		iceberg.reset();

		year_count++;
	}
}

빙산 입력 후 while 문을 살펴보자.

현재 칸이 방문한 적이 없는 육지라면 현재 칸을 시작점으로 DFS를 시작한다. 이런 방식으로 전체를 한 번 다 훑고 나왔을 때 빙산 덩어리가 2 이상이라면 더 이상 DFS를 돌릴 필요가 없기 때문에 현재 년 수를 출력하고 프로그램을 종료한다.

여기서 중요한 점이 있다면 바로 그 다음에 있는 else if문이다. 만약 n년이 흘러 더 이상 녹을 빙산이 없다면 빙산 덩어리(iceberg_count)는 0이 된다. 그 뜻은 더 이상 시간을 더 지체하면 DFS를 돌릴 필요가 없다는 뜻이므로 0을 출력하고 프로그램을 종료한다. 9번의 제출 중 7번의 시간 초과가 났는데 이 코드 작성으로 '맞았습니다!'를 볼 수 있었다. 껄껄

 

 

void Timepass(int sy, int sx) {
		q.push(make_pair(sy, sx));

		while (!q.empty()) {
			int cy = q.front().first;
			int cx = q.front().second;
			visited[sy][sx] = 1;
			q.pop();
			visited[cy][cx] = 1;


			for (int i = 0; i < 4; i++) {
				int ny = cy + my[i];
				int nx = cx + mx[i];

				if (ny < 0 || ny >= N || nx < 0 || ny >= M) continue;

				if (!board[ny][nx])
				{
					watercount[cy][cx]++;
				}
				else
				{
					if (!visited[ny][nx])
					{
						q.push(make_pair(ny, nx));
						visited[ny][nx] = 1;
					}
				}
			}
		}
	}
    
    
    void reset() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				board[i][j] = max(0, board[i][j] - watercount[i][j]);
				visited[i][j] = false;
				watercount[i][j] = 0;
			}
		}
	}

다음으로 Timepass와 reset함수를 살펴보자.

현재 칸을 기준으로 상하좌우에 있는 바다면을 확인하고 watercount라는 배열에 바다인 칸 수를 저장한다. 이렇게 전체를 한 번 싹 다 돌고 나와 reset함수를 호출한 후, 현재 값에서 바다면 수만큼 빼기 연산을 해준다. 이 때 유의해야할 점은 연산 값이 0 미만으로 내려가지 않도록 max 함수를 이용해 연산 결과가 0 미만이라면 그 칸의 값은 0이 되도록 한다. 그리고 다음 해에 전체를 훑기 위해 visited와 watercount 배열을 초기화한다.

 

---