BOJ 2468 c++ 안전 영역

 

처음에 아래와 같은 코드를 작성해서 제출했을때, 입출력 예제로 준 두가지에 대해서는 정상적으로 출력, 그런데 정답 제출시에 틀렸다. 어느 부분이 잘못되었는지 지속적으로 생각해보았다. 

// 5
// 6 8 2 6 2
// 3 2 3 4 6
// 6 7 3 3 2
// 7 2 5 3 6
// 8 9 5 2 7

// 2<=n<=100 // 1<=h<=100

// 5

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

int board[105][105];
int vis[105][105];
int cboard[105][105];

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

int n; 

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  cin>>n;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      cin>>board[i][j];
    }
  }
  //안전영역의 극단을 생각해보면, 모두 높이가 1일때, 한개, 혹은 0개// 결국 최대 갯수는 1이 최대이다 이 경우.
  int mxh=0;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      mxh=max(mxh,board[i][j]);
    }
  }
  int answer=0;
  
  for(int i=0; i<=mxh-1;i++){// 1씩 제거하기 위한 횟수의 의미로 사용함
    
    for(int i=0; i<n; i++){//매번 방문 보드 초기화
      for(int j=0; j<n; j++){
        vis[i][j]=0;
      }
    }
    for(int i=0; i<n; i++){//매번 새로 입힐 필요가 있나?
      for(int j=0; j<n; j++){
        board[i][j]-= 1;//한번 진행될때마다 1씩 빼면 될듯
      }
    }
    int cnt=0;
    queue<pair<int,int>> Q;
    for(int i=0; i<n; i++){
      for(int j=0; j<n; j++){
        if(vis[i][j]==1) continue;
        if(board[i][j]<=0) continue;
        vis[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>=n) continue;
            if(vis[nx][ny]==1) continue;
            if(board[nx][ny]<=0) continue;
            vis[nx][ny]=1;
            Q.push({nx,ny});
          }
        }
      }
    }
    answer=max(answer, cnt);
  }
  cout<<answer;
}

 

위의 풀이에서 무엇이 문제가 되어서 통과하지 못할까 생각해볼때, 저런 형태로 프로그램이 짜여야 한다는건 틀린건 아닌것 같았는데, 

이때에 내가 작성한 코드에서, 

for(int i=0; i<n; i++){//매번 새로 입힐 필요가 있나?
      for(int j=0; j<n; j++){
        board[i][j]-= 1;//한번 진행될때마다 1씩 빼면 될듯
      }
    }

이렇게 비가 비가 오는 양을 반복문을 통해서 1씩 증가시키면서 해당 경우마다 bfs를 돌려서 경우들을 나누려고 넣은 코드의 위치를 어디다가 두느냐가 차이를 만들어낼 수 있다고 생각해서 이 코드의 위치를 맨 아래로 옮겼다. 옮긴 이유는 비가 하나도 오지 않은 상태에서 bfs를 돌아서 안전영역을 측정하기 위함을 고려해서 그렇게 했는데, 그렇게 했을시에 작성한 코드를 첨부해보면, 

 

// 5
// 6 8 2 6 2
// 3 2 3 4 6
// 6 7 3 3 2
// 7 2 5 3 6
// 8 9 5 2 7

// 2<=n<=100 // 1<=h<=100

// 5

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

int board[105][105];
int vis[105][105];
int cboard[105][105];

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

int n; 

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  cin>>n;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      cin>>board[i][j];
    }
  }
  //안전영역의 극단을 생각해보면, 모두 높이가 1일때, 한개, 혹은 0개// 결국 최대 갯수는 1이 최대이다 이 경우.
  int mxh=0;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      mxh=max(mxh,board[i][j]);
    }
  }
  int answer=0;
  // 만약 mxh가 1이면 어떻게 되는가? 
  // for(int i=1; i<=0; i++){ 이거 출력 안된다. 
  //   cout<<"출력 되요?"<<' ';
  // }
  for(int i=0; i<=mxh;i++){//이건 횟수의 의미로 생각해야한다. 예를들어 최대 높이가 8이라면, 비가 1 왔을때, 2 왔을때, ... 8 왔을때 등을 생각할 수 있을 것이다. 그렇게 측정하기 위한 for문이다.  
    
    for(int i=0; i<n; i++){//매번 방문 보드 초기화
      for(int j=0; j<n; j++){
        vis[i][j]=0;
      }
    }
    
    int cnt=0;
    queue<pair<int,int>> Q;
    for(int i=0; i<n; i++){
      for(int j=0; j<n; j++){
        if(vis[i][j]==1) continue;
        if(board[i][j]<=0) continue;
        vis[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>=n) continue;
            if(vis[nx][ny]==1) continue;
            if(board[nx][ny]<=0) continue;
            vis[nx][ny]=1;
            Q.push({nx,ny});
          }
        }
      }
    }
    answer=max(answer, cnt);
    for(int i=0; i<n; i++){//매번 새로 입힐 필요가 있나?
      for(int j=0; j<n; j++){
        board[i][j]-= 1;//한번 진행될때마다 1씩 빼면 될듯
      }
    }
  }
  cout<<answer;
}

 

이와 같은 형태이다. 이때에 

for(int i=0; i<=mxh;i++)

이렇게 mxh를 기준으로 bfs를 몇번을 돌려야 할지에 대한 횟수를 설정하고 그 안에 로직들을 작성해 넣었는데, 그때에 내가 맨 위에 처음으로 작성한 코드의 경우는 가장 먼저 -1을 해주면서 처음 시작부터 비가 1 왔을때를 가정하고 문제를 푸는데, 계속 이런식으로 작성할때 통과가 안되는걸 보니까 극단의 부분에서 문제가 발생한다는 생각에, 장마철에 비가 안왔을때의 안전영역, 그리고 그 뒤에 비가 왔을때의 안전영역을 고려한 풀이를 작성해야하지 않을까 싶어서 board[i][j]-=1; 의 부분을 맨 아래로 옮겨서 비가 하나도 안와서 주어진 그대로의 안전영역을 측정할 수 있도록( 이 경우 안전영역의 최대 갯수는 1 일 것이다) 코드를 변형시켜보았다. 

 

그리고 변형한 코드를 제출하니 통과할 수 있었다. 

mxh까지 비가 왔을때는 결국 안전영역의 갯수가 0이 될 것이기 때문에 이 경우는 for문에 횟수를 포함시키던지 안시키던지 영향을 미치지 않는 형태의 코드가 될것이다. 

 

내가 맨 처음에 작성한 코드가 판별해내지 못하는 경우를 예로 들면, board가 모두 높이가 1로 주어지고 그 다음에 비가 1만큼 오고, 2만큼 오고, ... 형태로 증가하면서 오면, 가장 처음에 비가 안왔을때의 안전영역의 최대 갯수 1개, 그리고 그 뒤로는 계속 안전 영역의 최대갯수가 0개인데, 가장 첫번째 풀이처럼 작성하면 비가 안와서 안전영역의 갯수가 1개인 경우를 계산해주지 못하므로 문제가 발생할 것이라고 예상된다. 

 

다른 사람의 코드를 보고 참고해보기 위해 풀이를 찾아보았을때, 

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

int n, maxcnt, maxlimit;
int area[102][102];
int vis[102][102]; // 비에 잠긴 영역
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void bfs(int i, int j, int limit){
  queue<pair<int,int>> q;
  vis[i][j] = 1; // 방문표시
  q.push({i, j}); // 푸시
  while(!q.empty()){
    auto cur = q.front(); q.pop();

    for(int i = 0; i < 4; i++){
      int nx = cur.X + dx[i];
      int ny = cur.Y + dy[i];

      if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue; // 정상 범위 체크
      if(vis[nx][ny] == 0 && area[nx][ny] > limit){  // 미방문, 침수되지 않음
        vis[nx][ny] = 1;  // 첫 방문이라면 방문표시
        q.push({nx, ny}); // 푸시
      }
    }
  }
}

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

  cin >> n;
  for(int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) { // 0인 영역에서 시작하기
      cin >> area[i][j];
      maxlimit = max(area[i][j], maxlimit); // 잠기는 최대 높이
    }
  }

  for(int limit = 0; limit <= maxlimit; limit++) {
    for(int i = 0; i < n; i++)
      fill(vis[i], vis[i]+n, 0); // 방문배열 초기화
    
    int cnt = 0;
    for(int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (area[i][j] > limit && vis[i][j] == 0) { // 침수 여부, 방문 여부
          bfs(i, j, limit);
          cnt++;
        }
      }
    }
    maxcnt = max(cnt, maxcnt);
  }
  cout << maxcnt;
}

이와 같은 풀이를 얻을 수 있었고, 이 풀이의 경우는 내가 푼 풀이와는 다르게 높이를 하나씩 증가시키는 형태로 limit를 구현하고 있지만(나의 경우는 보드의 높이를 하나씩 빼주는 형태로 높이를 낮추는 형태) 결국 같은 결과를 가져오는 풀이이고, 이 풀이에서 높이의 limit=0으로 시작하는 것을 통해서 비가 하나도 오지 않았을때를 고려할 수 있는 풀이라는것을 알 수 있다. 

위의 풀이에서 

for(int limit=0; limit<=maxlimit; limit++) 라는 부분에서, 수면의 높이가 maxlimit 만큼 오게되면 결국 모두 잠겨서 안전영역의 갯수가 0개가 될 것이므로 limit<=maxlimit-1 까지만 고려해도 될 것이라고 생각해서 해당 부분을 

 

for(int limit = 0; limit <= maxlimit-1; limit++)

로 수정해서 제출해도 통과되었다. 

그리고 처음 내 문제의 풀이에서 잘못된 것처럼, 만약 limit=1로 시작하게 만들면, 이 풀이의 경우에는 비가 안오는 경우(limit==0) 을 제외한 형태로 코드를 수정해서 제출하면, 

내 처음 풀이에서 백준 사이트에서 채점 69% 위치에서 "틀렸습니다" 가 뜨게 되는데 이 풀이에서도 그렇게 틀리게 된다. 

결국 비가 오지 않았을때의 안전 영역까지 고려하는 풀이를 해야, 비가 오지 않아서 안전영역이 총 1개, 그리고 그 뒤로는 전체적으로 높이가 1이라서 모두 잠겨서 안전영역이 0개인 경우를 걸러내주어서 문제를 통과할 수 있게 되는 것이다. 

 

이 문제의 경우는 비가 어느정도까지 온다는것인지 알 수 없어서 조금 애매하게 느껴지는 문제였는데, 다음에 내가 옳다고 생각하는 로직을 작성했는데 틀렸다면, 먼저 양 극단 부분의 케이스를 고려해보는 접근을 시도해보도록 하자. 이번에는 이러한 생각을 하는데 굉장히 오래 걸려서 이 문제에 시간을 많이 투자하였다.