boj 2573 c++ 빙산

https://www.acmicpc.net/problem/2573

 

 

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

int n, m;
int board[305][305];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};

int chk[305][305];
int tmp[305][305];

int main(){
  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>>board[i][j];
    }
  }
  int ans=0;
  while(true){
    // 다 녹았는데 아직도 cnt>=2 가 안되서 반복을 돌고 있는 상황이면 종료
    int pos=false;
    for(int i=0; i<n; i++){
      for(int j=0; j<m; j++){
        if(board[i][j]!=0) pos=true;
      }
    }
    if(!pos){
      cout<<0;
      return 0;
    }

    //1년 지나서 빙산이 녹게하기
    for(int i=0; i<n; i++){
      for(int j=0; j<m; j++){
        if(board[i][j]==0) continue;
        int numzero=0;
        for(int dir=0; dir<4; dir++){
          int nx=i+dx[dir];
          int ny=j+dy[dir];
          if(board[nx][ny]==0) numzero++; 
        }
        tmp[i][j]=numzero;
      }
    }
    //빙산을 녹일때 i행 j열 별로 녹여나가면, 같은 년도에 녹인곳이 0이 되어버리면, i행 j열 별로 녹일때의 판단에
    //영향을 미칠 수 있으므로, tmp에 저장했다가 한번에 tmp의 값들을 각 원소에서 빼는 형태로 작성해서
    //판단부와 실행부를 나누어서 영향을 미치지 않도록 작성. 
    for(int i=0; i<n; i++){
      for(int j=0; j<m; j++){
        board[i][j]-=tmp[i][j];
        if(board[i][j]<0) board[i][j]=0;
      }
    }
    //1년 증가
    ans++;

    int cnt=0;
    for(int i=0; i<n; i++){
      for(int j=0; j<m; j++){
        chk[i][j]=0;
      }
    }
    queue<pair<int,int>> q;
    for(int i=0; i<n; i++){
      for(int j=0; j<m; j++){
        if(board[i][j]==0) continue;
        if(chk[i][j]!=0) continue;
        chk[i][j]=1;
        q.push({i,j});
        cnt++;
        while(!q.empty()){
          auto cur=q.front(); q.pop();
          for(int dir=0; dir<4; dir++){
            int nx=cur.first+dx[dir];
            int ny=cur.second+dy[dir];
            if(nx<0||nx>=n||ny<0||ny>=m) continue;
            if(board[nx][ny]==0) continue;
            if(chk[nx][ny]!=0) continue;
            chk[nx][ny]=1;
            q.push({nx,ny});
          }
        }
      }
    }
    if(cnt>=2) break;
  }
  cout<<ans;
}

 

위의 코드는 내가 옳게 작성한 코드이고, 그 코드에서 빙하 녹이는 부분을 보면, 

//1년 지나서 빙산이 녹게하기
    for(int i=0; i<n; i++){
      for(int j=0; j<m; j++){
        if(board[i][j]==0) continue;
        int numzero=0;
        for(int dir=0; dir<4; dir++){
          int nx=i+dx[dir];
          int ny=j+dy[dir];
          if(board[nx][ny]==0) numzero++; 
        }
        tmp[i][j]=numzero;
      }
    }
    for(int i=0; i<n; i++){
      for(int j=0; j<m; j++){
        board[i][j]-=tmp[i][j];
        if(board[i][j]<0) board[i][j]=0;
      }
    }

이렇게 작성을 하였다. 

초반에 빙하 녹이는 부분을 

//1년 지나서 빙산이 녹게하기
    for(int i=0; i<n; i++){
      for(int j=0; j<m; j++){
        if(board[i][j]==0) continue;
        int numzero=0;
        for(int dir=0; dir<4; dir++){
          int nx=i+dx[dir];
          int ny=j+dy[dir];
          if(board[nx][ny]==0) numzero++; 
        }
        board[i][j]-=numzero;
        if(board[i][j]<0) board[i][j]=0;
      }
    }

이런식의 형태로 작성을 하였는데, 이렇게 작성하면 예제로 제시해준 경우는 문제가 없었으나, 제출했을시에 틀렸다는 결과를 얻을 수 있었다. 이렇게 작성을 했을시에, 각각의 원소에서 판단을 진행하고, 판단의 결과를 바로 반영을 하기 때문에, 그렇게 되면 다른 원소에서 그 전 원소에서 이미 판단과 반영이 완료된 영역이, 새롭게 0이 되었다면 판단에 영향을 미치게 되는데, 이때에 문제에서 제시되는 형태는 1년이 지나면 모두 한번에 얼음이 녹는 형태이므로, 다른 얼음이 녹은 부분이 다른 원소에 같은 년도에 영향을 미치는 형태의 구조가 아니기 때문에 이렇게 코드를 작성하면 잘못된 구현에 해당한다. 그렇기 때문에 예시에서는 문제가 없을 수 있으나 잘못된 코드이고 다른 예시에서는 통과할 수 없게 되는 것이다. 

 

그래서 코드를 tmp[305][305] 배열을 따로 두어서, 매번 실행할때마다 tmp 배열에 해당 원소에서 변해야 하는 값들을 저장하고, 

그 값들을 다 판단해서 저장된 후에 일괄적으로 서로 영향을 미치지 않도록 이중for문을 따로 두어서 거기에서 원소들에서 녹아야 할 양만큼을 제거해주는 형태로 코드를 변형하여서 프로그램을 작성하였다. 

 

최근까지 프로그래머스에서 문제를 풀면서는, solution 함수를 제공하는 형태로 문제를 작성하였는데, 다시 백준에서 문제를 푸니까 스스로 처음부터 끝까지 프로그램을 작성하는 형태이고, main 함수를 포함하는 형태로 코드를 작성하다보니, main 하나에 모두 다 넣는 형태로 코드를 작성하고 있는데, 이제부터는 조금씩 main() 함수 부분에 다른 형태로 선언한 함수들을 포함하는 형태로 프로그램을 작성하는 연습을 해보아야 하는데, 아직까지 main에 로직에 관련된 모든 부분을 넣는게 익숙해서 이번에도 이렇게 코드를 작성하게 되었다. 

일단은 익숙한 대로 이렇게 작성하더라도, 후작업으로 위의 로직들을 따로 부분부분 함수로 나누는 연습을 해보도록 하자. 

 

 

다른 사람의 풀이를 참고해서 이것을 함수별로 나누어서 main 함수에서 사용하는 형태로 작성해본다면, 

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

 

위와 같은 형태로도 작성할 수 있을 것이다. 

함수를 따로 분리하는 연습을 꾸준하게 해보도록 하자.