[백준 2573] 빙산

2573번: 빙산 (acmicpc.net)

 

배운 것

- 구현해야 할 것이 많을때는 main 함수에 구현해야할 것들을 대략 함수로 빼서 나열해놓고

함수에서 고민하는 것이 깔끔한듯

- fill 함수 :

#include <algorithm>

	// 백터 생성
	vector<int> v(8);

	// 1번째 위치부터 4번째 위치까지 1로 할당
	fill (v.begin(), v.begin()+4, 1);

	// 5번째 위치부터 끝까지 2로 할당
	fill (v.begin()+4, v.end(), 2);

 

정답 코드1 - 좀 난해해서 읽기 어려움

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

int n, m, year;
int area[303][303];
int vis[303][303];

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

bool check(int i, int j) {
  return (i >= 0 && i < n && j >= 0 && j < m);
}

void initvis(){
  for(int i = 0; i < n; i++) fill(vis[i], vis[i] + m, 0);
}

// 1년의 시간 흐름을 진행
void melting(){ 
  int zero[303][303] = {0};
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      if(area[i][j] == 0) continue;
      for(int dir = 0; dir < 4; dir++){ // 주변의 0의 개수를 센다
        int nx = i + dx[dir];
        int ny = j + dy[dir];
        if(check(nx, ny) && area[nx][ny] == 0) zero[i][j]++;
      }
    }
  }
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++)
      area[i][j] = max(0, area[i][j] - zero[i][j]);    
  }
}

// 0 : 빙산이 다 녹음, 1 : 아직 한 덩이, 2 : 분리됨
int status(){
  int x = -1, y = -1;
  int cnt1 = 0; // 빙산의 개수
  // 빙산이 남아있는 아무 칸이나 선택
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      if(area[i][j]){
        x = i;
        y = j;
        cnt1++;
      }
    }
  }
  if(cnt1 == 0) return 0; // 빙산이 남아있는 칸이 없음
  int cnt2 = 0; // (x, y)와 붙어있는 빙산의 수
  queue<pair<int,int> > q;
  vis[x][y] = 1; // 현재 위치 방문
  q.push({x, y});
  while(!q.empty()){
    auto cur = q.front(); q.pop();
    cnt2++;
    for(int i = 0; i < 4; i++){
      int nx = cur.X + dx[i];
      int ny = cur.Y + dy[i];
      if(!check(nx, ny) || vis[nx][ny] == 1 || area[nx][ny] <= 0) continue; // 정상 범위, 첫 방문, 이동가능 체크
      vis[nx][ny] = 1; // 방문표시
      q.push({nx, ny}); // 이동
    }
  }
  if(cnt1 == cnt2) return 1; // 전체 빙산의 수와 (x, y)와 붙어있는 빙산의 수가 일치하므로 아직 한 덩이
  return 2;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

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

  while(true){    
    year++; // 1년 추가
    melting(); // 빙산 녹이기
    initvis(); // 방문배열 초기화
    int check = status(); // 빙산의 상태 확인
    if(check == 0){
      cout << 0;
      return 0;
    }
    else if(check == 1) continue; // 아직 한 덩이
    else break; // check = 2, 분리됨
  }
  cout << year;
  return 0;
}

 

정답코드2

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
int N, M;
int graph[300][300];
int tmp[300][300];
bool visited[300][300];
int dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };

void check(int r, int c) {
	queue<pair<int, int>>q;
	q.push({ r,c });

	while (!q.empty()) {
		int cr = q.front().first;
		int cc = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nr = cr + dir[i][0];
			int nc = cc + dir[i][1];

			if (nr >= 0 && nr < N && nc >= 0 && nc < M) {
				if (graph[nr][nc] != 0 && !visited[nr][nc]) {
					q.push({ nr,nc });
					visited[nr][nc] = true;
				}
			}
		}
	}
}
void meltIce() {
	memset(tmp, 0, sizeof(tmp));

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (graph[i][j] == 0) continue;
			int waterCnt = 0;
			for (int k = 0; k < 4; k++) {
				int nx = i + dir[k][0];
				int ny = j + dir[k][1];
				if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
				if (graph[nx][ny] == 0) {
					waterCnt++;
				}
			}
			int val = graph[i][j] - waterCnt;
			if (val > 0) tmp[i][j] = val;
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			graph[i][j] = tmp[i][j];
		}
	}
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> graph[i][j];
		}
	}

	int time = 0;
	while (true) {
		//나뉘어졌는지, 빙산이 다 녹았는지 검사
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (!visited[i][j] && graph[i][j] != 0) {
					check(i, j);
					cnt++;
				}
			}
		}
		//빙산이 다 녹았다면
		if (cnt == 0) {
			cout << 0;
			break;
		}
		//빙산이 두 덩이 이상이라면
		else if (cnt >= 2) {
			cout << time;
			break;
		}

		time++;
		//빙산 녹이기
		meltIce();
		memset(visited, false, sizeof(visited));

	}
	return 0;
}

 

참고

TWpower's Tech Blog