BOJ 2573 빙산

문제출처 : https://www.acmicpc.net/problem/2573

1. 문제요약

- 물과 상하좌우 4방향으로 인접한 빙하는 접하는 면 갯수 만큼 1년 뒤 녹음

- 빙하가 두 덩어리 이상으로 분리되는 최초시간

- 빙하가 다 녹을 때 까지 두 덩어리 이상으로 분리되지 않는다면 0 출력

- 3 <= 행n, 열m <= 300

- 첫행, n-1행, 첫열, m-1열은 0으로 주어짐

- 빙하의 최대 갯수는 10,000 이하

2. 접근방법

- 빙하 갯수를 세는 dfs or bfs

- 맵을 돌면서 물이 접하고 있는 빙하를 -1

3. 시간복잡도

- 빙하 갯수를 세는 dfs : N*M

- 맵을 돌면서 물이 접하고 있는 빙하 -1 : N*M

  => 여기까지 2NM

- 위 두 과정을 최대 몇번이나 반복할까?

  빙하의 갯수는 최대 10000 = 25 * 40

  행 25, 열 40 으로 된 한 덩어리의 빙하가 가장 늦게 녹음. 물과 접하는 면이 가장 작기 때문(50 + 80)

  정중앙에 있는 빙하가 가장 늦게 녹을 텐데 여기까지 도달하기 위해서는 12행((25 - 1) / 2)이 녹아야함

  모든 빙하가 10이라고 한다면 대략 한 행이 녹는데 10년

  12행이 녹는데 120년

  => 120 * 2NM = 21,600,000 반복

  => 반복마다 코드 길이가 조금 되지만 시간내엔 들어옴

4. 회고

- dfs를 돌때 4방향 탐색을

  if(!map[r-1][c] && !check[r-1][c]) dfs(r-1, c);

  if(!map[r][c-1] && !check[r][c-1]) dfs(r, c-1);

  if(!map[r+1][c] && !check[r+1][c]) dfs(r+1, c);

  if(!map[r][c+1] && !check[r][c+1]) dfs(r, c+1);

  은 틀리고

  for(int k = 0; k < 4; k++){

int nr = r + dr[k];

int nc = c + dc[k];

if(!map[nr][nc] && !check[nr][nc])

dfs(nr, nc);

  }

  는 맞는거지??

  물론 중간에 빙하 깍는 과정을 조금 수정했지만 디버깅 하면서 둘다 잘 돌아갔는데

  으흠.... 

  한시간동안 뻘짓했는데

- 시간이 244ms 나왔는데 더 줄일 수는 없을까?

- dfs에서 2개 이상 발견하면 dfs 안돌고 탈출

- 다 녹은 빙하 위치를 기억해서 다음 시작점을 거기서 부터 녹여나가도

소스코드

#include<iostream>
using namespace std;

int n, m, year, block;
int map[305][305];
bool check[305][305];
int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, -1, 0, 1 };

void dfs(int r, int c){
	check[r][c] = true;
	for (int i = 0; i < 4; i++){
		int nr = r + dr[i];
		int nc = c + dc[i];

		if (map[nr][nc] && !check[nr][nc])
			dfs(nr, nc);
	}
}

int main(void){
	cin >> n >> m;
	char a;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> map[i][j];

	while (true){
		block = 0;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				check[i][j] = false;

		for (int i = 1; i < n - 1; i++)
			for (int j = 1; j < m - 1; j++)
				if (map[i][j] && !check[i][j]){
					block++;
					dfs(i, j);
				}

		if (block >= 2){
			cout << year << "\n";
			return 0;
		}
		else if (block == 0) {
			cout << 0 << "\n";
			return 0;
		}

		year++;

		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (!map[i][j] && !check[i][j])
					for (int k = 0; k < 4; k++){
						int nr = i + dr[k];
						int nc = j + dc[k];

						if (0 <= nr && nr < n && 0 <= nc && nc < m && map[nr][nc]){
							map[nr][nc]--;
						}
					}
	}
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]