행 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)에 있음]
