[백준/C++] 2573. 빙산

오늘 하루 요약

나 : 거 대충 넘어갑시다

컴퓨터(백준) : 응 안돼 돌아가

빙산문제

이 문제는 함수 두 개가 필요하다.

1. 덩어리가 몇 개인지 확인하는 bfs
   여기서는 얼음이 있는 구역을 확인하고 덩어리가 0개인지, 1개인지, 2개 이상인지 확인해야하기 때문에 bfs 호출하기 전에 얼음이 있는 구역만 들어가도록 조건문을 걸어줘야한다.
   그리고 이 함수가 끝났을 때
   i) 덩어리가 아예 없음 -> 한꺼번에 다 없어짐(녹을때까지 분리X) -> 0 출력
   ii) 덩어리가 1개 -> 덜녹았구만 -> 계속 녹여!
   iii) 덩어리가 2개 이상 -> 몇 년 걸렸는지 출력

   다음과 같은 조건을 걸어줘야한다. i)에다가 연도를 출력하게 해가지고 맞왜틀만 한시간 하고 있었다...
   만약 아직 ii)처럼 아직 덜녹았다면 다음 2번 bfs를 수행한다.

2. 한 칸에서 4방위를 돌면서 바다와 인접한 면이 몇 개인지 세고 그만큼 줄여주는 bfs
   먼저 한 칸당 4방위를 돌면서 인접한 바닷면을 세어서 맵과 같은 크기의 배열에 저장해준다. 이후에 다 돌고 나면 맵에다가 빼주고 0보다 작아지면 0으로 넣어준다.
   만약 이거를 나이브하게 생각해서 4방위를 돌면서 바로바로 빼주면 안된다! 마치 nn년 지난 후 처럼 되어버림...

1->2 를 반복하면서 두덩어리 이상 생길 때까지 걸린 시간을 출력해준다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;

int n, m;
int years = 0;
int map[301][301] = {0, };
int tmp[301][301] = {0, };
bool visited[301][301] = {false,};
int prow[4] = { -1, 0, 1, 0 };
int pcol[4] = { 0, 1, 0, -1 };
queue <pair<int, int>> q;


void bfs(int x, int y){
    q.push({x, y});
    visited[x][y] = true;

    while(!q.empty()){
        int cx = q.front().first;
		int cy = q.front().second;
        q.pop();

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

			if(nx>=0 && nx<n && ny>=0 && ny<m && map[nx][ny]!=0){
				if(!visited[nx][ny]){
                	q.push({nx, ny});
                	visited[nx][ny] = true;
            	}
			}
        }
    }
}

void oneyearlater(){

    for (int i = 0; i<n; i++){
        for(int j = 0; j<m; j++){
			int sides = 0;
			if(map[i][j] != 0){
				for(int k = 0; k<4;k++){
					int nx = i + prow[k];
					int ny = j + pcol[k];

					if(nx>=0 && nx<n && ny>=0 && ny<m && map[nx][ny] == 0){
						sides++;
					}
					tmp[i][j] = sides;
				}
			}
        }
	}

	for (int i = 0; i<n; i++){
        for(int j = 0; j<m; j++){
			int height = map[i][j] - tmp[i][j];
			if(height > 0){
				map[i][j] = height;
			}
			else{
				map[i][j] = 0;
			}
		}
	}
}

int main() {
	cin>>n>>m;

	for (int i = 0; i<n; i++){
		for(int j = 0; j<m; j++){
			cin>>map[i][j];
		}
	}

    while(true){
		int cnt = 0;
        for (int i = 0; i<n; i++){
            for(int j = 0; j<m; j++){
				if(!visited[i][j] && map[i][j]!=0){
					bfs(i, j);
					cnt++;
				}
            }
		}
		if(cnt == 0){
			cout<<0;
			return 0;
		}

		if(cnt >= 2){
			cout<<years;
			return 0;
		}

		years++;
		oneyearlater();
		memset(visited, false, sizeof(visited));
		memset(tmp, 0, sizeof(tmp));
    }

}