[백준 2146] 다리 만들기

2146번: 다리 만들기 (acmicpc.net)

2146번: 다리 만들기

 

접근법

1. 기존 (섬 cnt + 넓이 구하기 문제) + 다른 섬과의 거리 

2. 기존 섬 cnt 하던대로 하고 다른 섬과의 거리 저장을 위한 dist 배열 하나 더 만들어서 적용

3. 신경쓸 것은 if문 안의 조건들, 리셋해줄것들, 추가 변수 cnt, ans 등등 어디에 넣고 언제 카운트해줄건지

 

정답 코드 1

// Authored by : yongjunleeme
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/1b1d9408543c440885788af2cfade28c
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
const int MX = 102;
int board[MX][MX];
int vis[MX][MX];
int dist[MX][MX];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,-1,1};
int n, cnt = 0;
queue<pair<int,int>> Q;
vector<int> ans;

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++) cin >> board[i][j];

  // cnt는 섬의 번호를 의미, board[i][j]의 값이 같은 경우 같은 섬임
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      if(board[i][j] == 0 || vis[i][j]) 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.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if(vis[nx][ny] || board[nx][ny] == 0) continue;
            board[nx][ny] = cnt;
            vis[nx][ny] = 1;
            Q.push({nx,ny});
        }
      }
    }
  }

  for(int i = 0; i < n; i++)
    fill(dist[i], dist[i] + n, -1);

  int ans = 999999;
  // 모든 육지 (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){
        Q.push({i,j});
        dist[i][j] = 0;
        bool escape = false; // 다리를 찾으면 이 변수를 true로 만들어 bfs를 중단. 있으나 없으나 big O의 시간복잡도 관점에서는 동일하나 약간의 최적화 가능.
        while(!Q.empty() && !escape){
          auto cur = Q.front(); Q.pop();
          for(int dir = 0; dir < 4; dir++){
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if(dist[nx][ny] >= 0 || board[i][j] == board[nx][ny]) continue;
            if(board[nx][ny] != 0 && board[i][j] != board[nx][ny]){
              ans = min(ans, dist[cur.X][cur.Y]);
              while(!Q.empty()) Q.pop();
              escape = true;
              break;
            }            
            dist[nx][ny] = dist[cur.X][cur.Y] + 1;
            Q.push({nx,ny});
          }
        }
        for(int i = 0; i < n; i++)
          fill(dist[i], dist[i] + n, -1);
      }
    }
  }
  cout << ans;
}

 

 

정답 코드 2

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/9d843ab1d6ce444a91717842520d1df3
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int board[101][101];
bool vis[101][101]; // 섬을 분류하는 첫 번째 bfs에서 사용
int dist[101][101]; // 다리의 길이를 구하는 두 번째 bfs에서 사용
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int n;
bool OOB(int a, int b){ // Out Of Bounds인지 체크하는 함수
  return a < 0 or a >= n or b < 0 or b >= n;
}

// 섬을 분류하는 첫 번째 bfs
void island(){
  int idx = 1; // 섬의 번호. board를 이 섬의 번호로 갱신할 예정
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      if(vis[i][j] || 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.X][cur.Y] = idx;
        for(int dir = 0; dir < 4; dir++){
          int nx = cur.X+dx[dir];
          int ny = cur.Y+dy[dir];
          if(OOB(nx,ny) || vis[nx][ny] || board[nx][ny] == 0) continue;
          Q.push({nx,ny});
          vis[nx][ny] = true;
        }
      }
      idx++; // 번호를 1 증가시켜 다음 섬에는 1 증가된 값이 기록될 수 있게끔 한다.
    }
  }
}

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++)
      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){
        dist[i][j] = 0;
        Q.push({i,j});
      }
    }
  }
  int ans = 999999;
  while(!Q.empty()){
    auto cur = Q.front(); Q.pop();
    for(int dir = 0; dir < 4; dir++){
      int nx = cur.X+dx[dir];
      int ny = cur.Y+dy[dir];
      if(OOB(nx,ny) || board[nx][ny] == board[cur.X][cur.Y]) // OOB거나 인접한 곳이 같은 섬일 경우
        continue;
      if(board[nx][ny] != 0){ // 인접한 곳이 다른 섬일 경우
        ans = min(ans,dist[nx][ny]+dist[cur.X][cur.Y]); // cur와 (nx, ny) 각각이 육지로부터 떨어진 거리를 합하면 된다.
      }
      else{ // 바다일 경우
        board[nx][ny] = board[cur.X][cur.Y];
        dist[nx][ny] = dist[cur.X][cur.Y]+1;
        Q.push({nx,ny});
      }
    }
  }
  cout << ans;
}