boj 2146 c++ 다리 만들기

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

 

일단 잘못된 프로그램인데, 내가 작성한 방식을 한번 첨부해보자면, 

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

int n;
int board[105][105];
int chk[105][105];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int tmp[105][105];

int pland=0;

int cnt_land(){
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      chk[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(board[i][j]==0) continue;
      if(chk[i][j]!=0) continue;
      q.push({i,j});
      chk[i][j]=1;
      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(board[nx][ny]==0) continue;
          if(chk[nx][ny]!=0) continue;
          chk[nx][ny]=1;
          q.push({nx,ny});
        }
      }
    }
  }
  return cnt;
}

void plus_land(){
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(board[i][j]==0) continue;
      for(int dir=0; dir<4; dir++){
        int nx=i+dx[dir];
        int ny=j+dy[dir];
        if(nx<0||nx>=n||ny<0||ny>=n) continue;
        if(board[nx][ny]!=0) continue;
        if(tmp[nx][ny]==0){
          tmp[nx][ny]++;
          pland++;    
        } 
         //이렇게 작성하면, 나중에 두 섬에서 연결되어도, 2로 표시 안되고 1로 표시될텐데. 
        //이렇게 되는 형태에서, 이 성질을 이용해서, 추가된 칸수를 세면, 아닌데, 겹치는 부분이 많이 생기는데, 그러면 뭔가 애매한데. 
        //추가하는 tmp[nx][ny]의 값들을 세고, 그것들의 총합과, 맵에 있는 1들의 합을 셌을때, 차이가 발생한다면 그것은 겹치는 곳이 생긴다는 것이고, 겹치는 곳이 생긴다는 얘기는 겹쳤기 때문에 구하는 공식을 겹쳤을때의 공식으로 해결하며 된다는 뜻이다. 시도해보자. 
      }
    }
  }
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      board[i][j]=tmp[i][j];
    }
  }
  // cout<<"plus land done"<<'\n';
}

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

  int firstland=0;
  
  cin>>n;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      cin>>board[i][j];
      tmp[i][j]=board[i][j];//이 보드의 경우는 board에서 테두리를 따라서 1씩 늘어나는 연산을 수행할 보드이다. 그리고 다시 tmp의 값을 board에 씌울것
    }
  }

  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(board[i][j]==1) firstland++; 
    }
  }

  int f=cnt_land();
  // void plus_land();// tmp에 board를 영역을 넓히고, board에 해당 내용을 복사해서 board를 갱신해주는 함수. 

  int cnt=f;
  int midans=0;
  while(f==cnt){
    plus_land();
    cnt=cnt_land();
    midans++;
    // cout<<f<<" :<first> "<<cnt<<" : <cnt>"<<'\n';
  }
  bool isodd=false;
  int lastland=0;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(board[i][j]==1) lastland++;
    }
  }
  if(firstland+pland!=lastland) isodd=true; 
  int ans=0; 
  if(isodd) ans=2*midans-1;
  else ans=2*midans;
  cout<<firstland<<" + "<<pland<<" : "<<lastland<<'\n';
  cout<<ans;
  // for(int i=0; i<n; i++){
  //   for(int j=0; j<n; j++){
  //     cout<<board[i][j]<<' ';
  //   }
  //   cout<<'\n';
  // }

  // cout<<'\n';
  // plus_land();

  // for(int i=0; i<n; i++){
  //   for(int j=0; j<n; j++){
  //     cout<<tmp[i][j]<<' ';
  //   }
  //   cout<<'\n';
  // }
  // cout<<'\n';

  // for(int i=0; i<n; i++){
  //   for(int j=0; j<n; j++){
  //     cout<<board[i][j]<<' ';
  //   }
  //   cout<<'\n';
  // }

  // int ans=0;
  // for(int i=0; i<n; i++){
  //   for(int j=0; j<n; j++){
  //     if(board[i][j]>=2) ans=2*midans-1;
  //     else ans=2*midans;  
  //   }
  // }
  // cout<<ans;
  // 1. 카운트한다. 
  // 2. 섬에서 테두리를 1씩 증가시키는 형태로 만든다
  // 3. 카운트해서 숫자가 줄었다면, 다리가 연결된것이고, 연결되었을때, 겹치는 부분이 2일때와, 겹치는 부분이 없을때로 구분지어서 다리의 길이를 판단한다. 
}

위와 같고, 이때에 내가 하려고 했던 것은, bfs를 통해서 섬이 몇개인지를 체크하고, 그리고 한번에 섬들에서 테두리를 따라서 영역을 넓히는 함수를 통해서 영역들을 넓히는 형태로 한번씩 두르고, 그리고 나서 다시 bfs로 섬의 개수를 체크하는 식으로, 만약 섬의 개수가 달라지는 때가 나온다면 그때에 몇번의 시행을 했는지 확인하고, 시행의 갯수를 확인한뒤에 만약 섬의 영역이 서로 겹쳐지는 부분이 나온다면 그 경우 정답은 내가 구한 횟수의 2배를 하고 -1을 해주고, 겹치지 않는 상태에서 섬의 갯수가 변하면 그럼 곱하기 2를 통해서 정답을 도출하는 형태로, 양방향에서 점점 넓어지며 섬의 하나가 되는것을 체크해주는 형태로 기획하였다. 

 

그런데 이때에 땅을 넓히는 함수를 생각할때, 그냥 단순하게 tmp[i][j]++; 형태로 만들면, 1에 둘러싸여있는 0에서 값이 1이 아니라 2나 3 같이 더 증가하게 되고, 그렇게 되면 섬이 넓어져서 서로 다른 섬에서 넓어진 영역이 겹쳐진건지 아닌지 알 수 없어서, 

if(tmp[i][j]==0) tmp[i][j]++;

형태로 코드를 변경해보았을때를 떠올렸는데, 이렇게 해버리면 또 두 섬에서 넓어져서 겹쳐지는 부분도 체크가 안되게 된다. 

그래서 넓이를 넓히는 형태로 갯수를 새보려고 했었는데, 이것도 결국 땅을 넓히는 함수를 기존과 동일하게 작성해버리면 겹치는걸 체크하지 못하기 때문에, 이 상황에서 넓히는 함수를 어떤식으로 작성해야 할지 알지 못해서 난관에 봉착했다. 

 

너무 오랜 시간이 걸리고 다른 방향으로의 접근이 떠오르지 않아서, 다른 사람의 풀이방향을 참고하여서 풀어보았다. 

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

int board[105][105];
int vis[105][105];
int dist[105][105];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int n , cnt=0;

queue<pair<int,int>> q;

//주어진 섬들에 개별적으로 다른 번호를 붙여서 구분짓게 해주는 bfs 함수
void numbering_land(){
//cnt는 섬의 번호를 의미, board[i][j]의 값이 같은 경우 같은 섬
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(board[i][j]==0) continue;
      if(vis[i][j]==1) continue;
      cnt++;
      vis[i][j]=1;
      board[i][j]=cnt;
      q.push({i,j});
      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;
          board[nx][ny]=cnt;
          vis[nx][ny]=1;
          q.push({nx,ny});
        }
      }
    }
  }
}

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];
  }
  //bfs를 돌면서 섬들에 1부터 시작하는 번호로 섬들의 땅의 값들을 바꾸어서 구분지어주는 함수.
  numbering_land();

  for(int i=0; i<n; i++)
    fill(dist[i],dist[i]+n,-1);
  
  int ans=0x7f7f7f7f;
  // 모든 육지 (i,j)의 각각에 대해 bfs를 진행. 이때 board[i][j]와 board[nx][ny]가 다른 최초의 (nx,ny)를 찾으면 (i,j)에서 시작하는 다리의 길이를 계산 가능. 

  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(board[i][j]==0) continue;
      q.push({i,j});
      dist[i][j]=0;
      bool escape=false;
      while(!q.empty() && !escape){
        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(dist[nx][ny]>=0) continue;
          if(board[i][j]==board[nx][ny]) continue;
          if(board[nx][ny]!=0 && board[i][j]!=board[nx][ny]){
            ans=min(ans,dist[cur.first][cur.second]);
            while(!q.empty()) q.pop();
            escape=true;
            break;
          }
          dist[nx][ny]=dist[cur.first][cur.second]+1;
          q.push({nx,ny});
        }
      }
      for(int i=0; i<n; i++)
        fill(dist[i],dist[i]+n,-1);
    }
  }
  cout<<ans;
}

위의 풀이의 경우는, 처음에 bfs를 보드에 대해서 각 원소별로 판단하면서 돌면서, 개별 섬들에 대해서 연결되어 있는 1들의 경우 섬으로 판단하고, 해당 섬에 등장하는 순서에 따라 번호를 달리해서 섬을 이루는 원소들의 값을 1이 아니라 등장순서에 해당하는 번호로 바꾸는 형태로 섬들의 번호를 바꾸고, 그리고 나서 바뀐 섬들의 번호를 가지고 있는 board를 기준으로, 각 개별 섬들의 각 원소에서 다른 번호의 섬이 나올때까지를 bfs를 돌면서, 다른 섬을 만났을때 그때까지의 거리를 ans에 저장하며 해당 ans의 값에 더 작은 값을 갱신하는 형태로 작성한 프로그램이다. 

 

내가 처음에 생각한 것처럼, 점점 영역을 넓혀가면서 만나게 되는 부분이 있는지에 대해서 판단하는 형태에 대한 코드도 찾을 수 있었으며, 해당 코드의 경우 더욱 효율적인 형태의 풀이를 제공한다. 그러한 형태의 코드에 대해서 내 식으로 코드를 변형해서 제공해보면, 

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

int board[105][105];
bool vis[105][105];
int dist[105][105];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int n;
bool OOB(int a, int b){
  return a<0 || a>=n || b<0 || b>=n;
}

void island(){
  int idx=1;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(vis[i][j]) continue;
      if(board[i][j]==0) continue;
      queue<pair<int,int>> Q;
      Q.push({i,j});
      vis[i][j]=true;
      while(!Q.empty()){
        auto cur = Q.front(); Q.pop();
        board[cur.first][cur.second]= idx; 
        for(int dir=0; dir<4; dir++){
          int nx=cur.first+dx[dir];
          int ny=cur.second+dy[dir];
          if(OOB(nx,ny)) continue;
          if(vis[nx][ny]) continue;
          if(board[nx][ny]==0) continue;
          Q.push({nx,ny});
          vis[nx][ny]=true;
        }
      } 
      idx++;
    }
  }
}

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];
  island();
  for(int i=0; i<n; i++)
    fill(dist[i],dist[i]+n,-1);
  queue<pair<int,int>> Q;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(board[i][j]!=0){//모든 점을 bfs의 대상으로 만들기 위해 dist 0으로 표시하고 queue에 넣기. 
        dist[i][j]=0;
        Q.push({i,j});
      }
    }
  }
  int ans=0x7f7f7f7f;
  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(OOB(nx,ny)) continue;
      if(board[nx][ny]==board[cur.first][cur.second]) continue; //인접한 섬이 같은 섬의 일부일 경우 건너뛰기
      if(board[nx][ny]!=0){
        //인접한 섬이 현재 섬과 같지 않은데 0이 아니므로 다른 섬
        ans=min(ans, dist[nx][ny]+dist[cur.first][cur.second]);
      }
      else{//바다일 경우
        board[nx][ny]=board[cur.first][cur.second];
        dist[nx][ny]=dist[cur.first][cur.second]+1;
        Q.push({nx,ny});
      }
    }
  }
  cout<<ans;
}

이와같이 나타낼 수 있다. 이 경우, bfs가 동작하는 형태대로, 테스트 해보고 다른 섬의 일부를 만나는것이 아닌경우, 그 경우에 같은 섬의 일부라면 그냥 지나치고, 만약 바다라면 해당 섬의 영역을 넓혀가는 형태처럼 계산해서 점점 영역을 넓혀가는 형태처럼 bfs를 돌고, 그렇게 할수록 dist에 거리를 갱신시켜 가면서 표시한뒤에, 만약 bfs의 과정에서 다른 섬을 만나게 되는 판단부에 걸리게 된다면, 그때에 지금 섬의 거리 값과 다른 섬의 거리값을 합쳐서 ans에 저장하는 형태로 ans 값들을 판단하면서 더 작은 값으로 갱신하는 형태로 코드를 작성한 방법이다. 

 이와 같은 방법으로 구하는것이 훨씬 효율적이게 문제를 해결할수 있는 풀이인데, 내가 처음에 고민을 많이했던 영역을 어떻게 넓혀 나갈지에 대해서, 그 영역을 넓혀 가는것 또한 bfs를 돌면서 판단을 하면서 같이 영역을 넓혀나가는 처리를 하는것이 매우 인상깊고 좋은 방법이라는 생각이 든다. 

bfs가 어떤식으로 퍼저나가는 지에 대해서 잘 이해해야 할것이고, 그리고 bfs를 시작하고 싶은 모든 점들을 한번에 담아서 다같이 bfs를 돌리는것이 어떠한 형태로 동작하는지에 대해서 제대로 이해하는것이 중요한 코드라는 생각이 든다. 

더욱 잘 이해해보도록 하자.