글 읽기 - 빙산 문제 시간초과가 납니다 (C++) 도움 부탁드립니다!

bitstr58 2년 전 0

안녕하세요.

읽어주셔서 감사합니다.

빙산 문제에서 시간 초과가 나는데 얼음을 녹이는 melting 함수쪽 시간 복잡도를 어떻게 줄여야되는지 해결 못하고 있습니다.

시간초과 관련해서 도움이 필요해서 글 올려봅니다.

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

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);
}

int melting(){ // 녹는 높이 계산해서 area - diff

  int zero[303][303] = {0};
  int zerocnt = 0;

  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){

      if(area[i][j] == 0) continue;
      for(int z = 0; z < 4; z++){ // 주변의 0의 개수를 센다.
        int nx = i + dx[z];
        int ny = j + dy[z];
        if(!check(nx, ny)) continue; // 유효 인덱스 체크
        if(area[nx][ny] == 0) zero[i][j]++;
      }
    }
  }

  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){ // area - diff
      area[i][j] = area[i][j]- zero[i][j];
      if(area[i][j] < 0) {
        area[i][j] = 0; zerocnt++;
      }
    }
  }

  return zerocnt;
}

void bfs(int x, int y){

  queue<pair<int,int> > qu; // {좌표 x, y}

  vis[x][y] = 1; // 현재 위치 방문
  qu.push({x, y});

  while(!qu.empty()){
    int curx = qu.front().X;
    int cury = qu.front().Y;
    qu.pop();

    for(int i = 0; i < 4; i++){
      int nx = curx + dx[i];
      int ny = cury + dy[i];
      if(!check(nx, ny)) continue; // 정상 범위 체크
      if(vis[nx][ny] == 0 && area[nx][ny] > 0){ // 첫 방문, 이동가능 체크
        vis[nx][ny] = 1; // 방문표시
        qu.push({nx, ny}); // 이동
      }
    }
  }

}


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(1){

    int zero = melting(); // 빙산 녹이기
    if(zero == (m*n)){ // 빙산 다 녹으면 탈출
      cout << 0;
      return 0;
    }

    year++; // 1년 추가

    //initvis(); // 방문배열 초기화
    memset(vis, 0, sizeof(vis));

    int areacnt = 0;
    // 덩어리 세기
    for(int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if(area[i][j] > 0 && !vis[i][j]) { // 첫방문, 높이존재.
          bfs(i, j);
          areacnt++;
          // 덩어리 2개 이상면 탈출
          if(areacnt > 1){
            cout << year;
            return 0;
          }
        }
      }
    }

  }

  cout << 0;
  return 0;
}

rhdqor213 2년 전 1

현재 코드는 0의 개수를 제대로 세지 못하고 있습니다.

따라서 87번째 줄 조건문으로 while문을 제 때 탈출하지 못하고 무한루프를 돌게 됩니다.

38번째 줄 조건문을 <=로 고쳐주시면 맞았습니다를 받습니다.

bitstr58 2년 전 1

@rhdqor213 님 정말 감사합니다!!

제 코드를 보니까 음수가 된 것만 0의 개수로 카운팅 하고 있었네요.... ㅠㅠ;

긴 코드 읽어봐 주셔서 감사합니다!!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

빙산 문제 시간초과가 납니다 (C++) 도움 부탁드립니다!

bitstr58 2년 전 0

rhdqor213 2년 전 1

bitstr58 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말