[BOJ][실3][2573] 빙산

문제 링크

문제링크

첫 번째 풀이 : DFS

알고리즘

조건대로 DFS 구현하다가 연결 요소의 갯수가 0개이면 얼음이 모두 녹은 것으로 판단하면 됩니다. 단, 얼음을 녹일 때 전체를 한 번에 녹이지 않고 1개씩 녹이면 인접한 바다의 갯수를 실제보다 많이 count할 수 있습니다. 또한 녹고 나서 음수가 되지 않도록 하는 것도 신경써야 합니다.

시간초과가 나는 경우 테두리가 0인 것을 이용해보세요. 그래도 안되면 함수 호출을 최대한 줄여보세요. (녹이는 함수를 따로 구현하지 않고 구현 등)

정답 코드

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

int n = 0, m = 0, ans;
int cmp = 0;
int map[300][300];
int melt[300][300];
bool visited[300][300];
int dx[4] = { 0,0, 1,-1 };
int dy[4] = { 1,-1,0,0 };
void dfs(int x, int y) {
  visited[x][y] = true;
  for (int k = 0; k < 4; k++) {
    int nx = x + dx[k];
    int ny = y + dy[k];
    if (nx < 0 || nx >= n) continue;
    if (ny < 0 || ny >= m) continue;
    if (visited[nx][ny]) continue;
    if (map[nx][ny]) {
      dfs(nx, ny);
    }
  }
}

int solve(void) {
  while (true) {
    ans++;
    //빙하 녹이기
    memset(melt, 0, sizeof(melt));
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (!map[i][j]) continue;
        for (int k = 0; k < 4; k++) {
          int nx = i + dx[k];
          int ny = j + dy[k];
          if (nx < 0 || nx >= n) continue;
          if (ny < 0 || ny >= m) continue;
          if (!map[nx][ny]) melt[i][j]++;
        }
      }
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        map[i][j] -= melt[i][j];
        if (map[i][j] < 0) map[i][j] = 0;
      }
    }
    cmp = 0;
    memset(visited, 0, sizeof(visited));
    //connected component 갯수 세기
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (map[i][j] && !visited[i][j]) {
          dfs(i, j);
          cmp++;
        }
      }
    }
    if (cmp >= 2) {
      return ans;
    }
    else if (cmp == 0) {
      return 0;
    }
  }
}



int main(void) {
  cin.tie(NULL);
  ios::sync_with_stdio("false");
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> map[i][j];
    }
  }

  cout << solve();

  return 0;
}

Success Notice: 수고하셨습니다.