이번 문제는 빙산이라는 문제다.
하나의 덩어리였던 빙산이 매년 녹으면서 두 개의 덩어리가 될때까지 몇년이 걸리는지 구하는 문제였다.
이 문제에서 가장 중요한 부분은 매년 빙하를 녹이는 부분, 두 개의 덩어리인지 확인하는 부분 그리고 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않는지 확인하는 부분인것 같다.
1.
매년 빙하를 녹이는 부분
우선 매년 빙하를 녹이는 부분은 year_later()라는 함수를 이용해서 구현을 했다.
저 함수에서 가장 중요한 부분은 빙하를 녹일 때 전역배열인 vec을 이용하지 않고 임시 벡터인 temp를 이용해서 계산을 하는 것이다.
만약 이렇게 구현하지 않고 전역벡터인 vec을 이용해서 계산을 하게 되면 어떤 경우가 일어나는지 확인해보자.
위 사진에서 다른 부분은 접어 두고 (3, 2)에 있는 1과 (4, 2)에 있는 5만 보도록 하자.
이때 빙하를 녹이는 작업은 (1, 1)부터 (N, M)방향으로 진행 하므로 위에 있는 1을 녹인 상태에서 5가 3면이 바다로 이루어진 상태로 계산을 하게 된다.
그렇지만 사실 (4, 2)에 있는 5는 두 면이 바다인 상태에서 녹아야 하므로 temp라는 임시 배열을 만들고 이를 계산한 후 전역 배열인 vec에 이를 복사해 주도록 구현하였다.
2.
두 개의 덩어리인지 확인하는 부분
이 기능은 is_divide()라는 함수를 이용해서 구현을 했다.
빙하가 두 부분으로 이루어졌다는 것은 bfs를 이용해서 인접해 있는 값을 찾을 때 적어도 2번의 bfs함수를 진행해야 한다는 뜻이므로 cnt값을 이용해서 bfs함수가 두번 진행될것 같으면(덩어리가 두개 이상이라면) true를 반환해주고 한 번만 진행한다면(한개의 덩어리로 이루어져 있다면) false를 반환해주었다.
3.
전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않는지 확인하기
이 기능은 final_check()함수를 이용해서 구현하였다.
사실 이 기능은 바로 위에서 is_divide()를 이용해서 두 덩어리로 이루어져 있지 않다는 것을 확인했기 때문에 vec배열 안에 0이 아닌 다른 값이 들어 있으면 다시 빙하를 녹이도록 구현을 하였다.
그리고 끝으로 이 문제를 풀면서 3번의 런타임 에러가 발생했었는데 이는 final_check()함수에서 for문 안에서만 return을 해주고 함수 전체에 대해서는 return을 해주지 않아서 발생한 것이였다.
이는 visual studio같은 msvc환경에서는 문제가 되지 않지만 visual studio code같은 환경에서는 런타임 에러를 발생시킨다는 알고리즘 고수분의 말씀을 듣고 알게 되었다.
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int N, M;
vector<vector<int>> vec(302);
struct Dir {int y, x;};
Dir dir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
bool check[302][302] = { false, };
void input() {
int n;
for (int i = 1; i <= N; i++) {
vec[i].push_back(0);
for (int j = 1; j <= M; j++) {
cin >> n;
vec[i].push_back(n);
}
}
}
void copy_vector(vector<vector<int>> temp) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++)
vec[i][j] = temp[i][j];
}
}
void year_later() { //일년이 지나는 함수
vector<vector<int>> temp(302); //얼음이 녹을 때 전역벡터인 vec을 가지고 계산을 하게 되면 안된다.
//모든 얼음이 한꺼번에 녹기 때문에 임시 벡터인 temp를 사용해야 한다.
for (int i = 1; i <= N; i++) {
temp[i].push_back(0);
for (int j = 1; j <= M; j++)
temp[i].push_back(vec[i][j]);
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
int cnt = 0;
if (vec[i][j]) {
for (int k = 0; k < 4; k++) {
int new_y = i + dir[k].y;
int new_x = j + dir[k].x;
if (new_y > 0 && new_y <= N && new_x > 0 && new_x <= M && !vec[new_y][new_x]) //몇개의 바다로 둘러 쌓여 있는지 확인한다.
cnt++;
}
temp[i][j] - cnt < 0 ? temp[i][j] = 0 : temp[i][j] -= cnt; //바다의 수만큼 빙하의 높이가 감소한다.
}
}
}
copy_vector(temp); //계산이 끝난 temp배열을 전역 변수인 vec에 대입해준다.
}
void bfs(int y, int x) { //빙하가 몇 개의 덩어리로 이루어져 있는지 확인하는 함수
check[y][x] = true;
queue<pair<int, int>> q;
q.push({ y, x });
while (!q.empty()) {
int new_y = q.front().first;
int new_x = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int next_y = new_y + dir[i].y;
int next_x = new_x + dir[i].x;
if (next_y > 0 && next_y <= N && next_x > 0 && next_x <= M && !check[next_y][next_x] && vec[next_y][next_x]) {
check[next_y][next_x] = true;
q.push({ next_y, next_x });
}
}
}
}
void reset() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++)
check[i][j] = false;
}
}
bool is_divide() { //빙하의 덩어리가 2개 이상이라면 true를 반환하고 아니라면 false를 반환한다.
int cnt = 0;
reset();
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (vec[i][j] && !check[i][j]) {
if (cnt == 0) {
cnt++;
bfs(i, j);
}
else //끝났다는 것
return true;
}
}
}
return false;
}
bool final_check() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (vec[i][j]) //녹을 때까지 두 덩이로 분류가 된게 아니라면
return false;
}
}
return true; //요기서 return true를 안해줘서 계속 틀렸다.
}
int main(void) {
cin.tie(NULL);
ios::sync_with_stdio(false);
cin >> N >> M;
input(); //입력값 받는 함수
int result = 0; //결과값
while (1) {
result++;
year_later(); //빙하가 녹는 기능을 지닌 함수
if (is_divide()) //두 덩이로 분류가 됐다면
break;
if (final_check()) { //빙하가 다 녹았는지 확인
result = 0;
break;
}
}
cout << result << "\n";
return 0;
}
'백준 알고리즘' 카테고리의 다른 글
| 백준 2075(N번째 큰 수) (0) | 2020.05.28 |
|---|---|
| 백준 2174(로봇 시뮬레이션) (0) | 2020.04.06 |
| 백준 2146 (다리 만들기) (0) | 2020.03.29 |
| 백준 15650 (N과 M(2)) (0) | 2020.03.29 |
| 백준 1022(소용돌이 예쁘게 출력하기) (0) | 2020.03.26 |
