다리 만들기(BOJ 2146번)

문제

이미지 클릭

문제 설명

이 문제는 두 개 이상의 섬이 존재한다고 가정하고 한 섬에서 다른 섬으로 연결할 수 있는 가장 짧은 다리의 길이를 출력하는 간단한 문제이다. 그렇기에 단순히 너비 우선 탐색을 사용한다면 쉽게 해결할 수 있다.

문제 해설

#include<iostream>
#include<queue>
using namespace std;
int n;
const int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
int a[201][201];
int visited[201][201];
int mn = 1e9;
struct P {
  int b, c, d;
};
int f(int x, int y, int t) {
  int visited1[201][201];
  fill(&visited1[0][0], &visited1[0][0] + 201 * 201, 0);
  visited1[x][y] = 1;
  queue<P> q;
  q.push({ x,y,1 });
  while (!q.empty()) {
    int x = q.front().b, y = q.front().c, cnt = q.front().d;
    q.pop();
    for (int i = 0; i < 4; i++) {
      int xx = x + dx[i], yy = y + dy[i];
      if(mn<=cnt) return 1e9;
      if (xx<1 || yy<1 || xx>n || yy>n || a[xx][yy] == t || visited1[xx][yy]) continue;
      if (a[xx][yy] != t && a[xx][yy]!=0) return cnt;
      visited1[xx][yy] = 1;
      q.push({ xx,yy,cnt + 1 });
    }
  }
  return 1e9;
}
int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> a[i][j];
    }
  }
  int k = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (!visited[i][j]&&a[i][j]) {
        queue<pair<int, int>> q;
        visited[i][j] = 1;
        q.push({ i,j });
        while (!q.empty()) {
          int x = q.front().first, y = q.front().second;
          a[x][y] = k;
          q.pop();
          for (int i = 0; i < 4; i++) {
            int xx = x + dx[i], yy = y + dy[i];
            if (xx<1 || yy<1 || xx>n || yy>n || visited[xx][yy] || !a[xx][yy]) continue;
            visited[xx][yy] = 1;
            q.push({ xx,yy });
          }
        }
        k += 1;
      }
    }
  }
  fill(&visited[0][0], &visited[0][0] + 201 * 201, 0);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (!visited[i][j] && a[i][j]!=0) {
        queue<pair<int,int>> q;
        visited[i][j] = 1;
        q.push({ i,j });
        while (!q.empty()) {
          int x = q.front().first, y = q.front().second;
          q.pop();
          for (int i = 0; i < 4; i++) {
            int xx = x + dx[i], yy = y + dy[i];
            if (xx<1 || yy<1 || xx>n || yy>n || visited[xx][yy]) continue;
            else if (!a[xx][yy]){
              int p= f(xx, yy, a[x][y]);
              mn = min(mn,p);
              continue;
            }
            else q.push({ xx,yy });
            visited[xx][yy] = 1;
          }
        }
      }
    }
  }
  cout << mn;
}

 

코드가 비교적 길기 때문에 크게 3 부분으로 나누어서 설명해보자

 

1) 섬을 각각 분리해 주기

int k = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (!visited[i][j]&&a[i][j]) {
        queue<pair<int, int>> q;
        visited[i][j] = 1;
        q.push({ i,j });
        while (!q.empty()) {
          int x = q.front().first, y = q.front().second;
          a[x][y] = k;
          q.pop();
          for (int i = 0; i < 4; i++) {
            int xx = x + dx[i], yy = y + dy[i];
            if (xx<1 || yy<1 || xx>n || yy>n || visited[xx][yy] || !a[xx][yy]) continue;
            visited[xx][yy] = 1;
            q.push({ xx,yy });
          }
        }
        k += 1;
      }
    }
  }

 

1. 만약 섬인 부분(즉 숫자 1인 부분)을 만나게 된다면 그 부분을 1번 섬으로 칭하고 나머지 부분을 BFS를 사용하여서 1로 채워준다.

2. 그런 다음 k를 +1해 주어서 2번째 섬을 2로 채워 주고 n번째 섬은 n으로 채워준다.  

대충 이런 느낌?

2)  바다와 맞닿은 부분을 탐색

fill(&visited[0][0], &visited[0][0] + 201 * 201, 0);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (!visited[i][j] && a[i][j]!=0) {
        queue<pair<int,int>> q;
        visited[i][j] = 1;
        q.push({ i,j });
        while (!q.empty()) {
          int x = q.front().first, y = q.front().second;
          q.pop();
          for (int i = 0; i < 4; i++) {
            int xx = x + dx[i], yy = y + dy[i];
            if (xx<1 || yy<1 || xx>n || yy>n || visited[xx][yy]) continue;
            else if (!a[xx][yy]){
              int p= f(xx, yy, a[x][y]);
              mn = min(mn,p);
              continue;
            }
            else q.push({ xx,yy });
            visited[xx][yy] = 1;
          }
        }
      }
    }
  }

 

1. BFS를 통해서 역시나 1,2,.. ni번째 섬까지 탐색을 진행해 준다.

2. 만약 바다와 인접한 부분(0과 인접한 부분)이 있다면 또 다른 BFS 탐색을 시작해 준다.

3. 함수 f로 인자를 전달해 줄 때는 (xx, yy)(즉 섬과 인접해 있는 바다의 좌표값)과 a [x][y] (섬의 번호)를 전달해준다.  

3) 거리 측정(함수 f)

struct P {
  int b, c, d;
};
int f(int x, int y, int t) {
  int visited1[201][201];
  fill(&visited1[0][0], &visited1[0][0] + 201 * 201, 0);
  visited1[x][y] = 1;
  queue<P> q;
  q.push({ x,y,1 });
  while (!q.empty()) {
    int x = q.front().b, y = q.front().c, cnt = q.front().d;
    q.pop();
    for (int i = 0; i < 4; i++) {
      int xx = x + dx[i], yy = y + dy[i];
      if(mn<=cnt) return 1e9;
      if (xx<1 || yy<1 || xx>n || yy>n || a[xx][yy] == t || visited1[xx][yy]) continue;
      if (a[xx][yy] != t && a[xx][yy]!=0) return cnt;
      visited1[xx][yy] = 1;
      q.push({ xx,yy,cnt + 1 });
    }
  }
  return 1e9;
}

 

1. 큐에는 현제 좌표와 현제 다리의 길이를 넣어준다.

2. 만약에 mn의 값(거리의 최솟값) 보다 현제 다리의 길이가 더 크다면 큰 수를 리턴하여서 BFS를 종료한다.

3. 만약에 현제 위치가 바다가 아니고 섬이면서 처음에 출발한 섬의 번호(t)와 현제 섬의 번호가 다르다면 현제 다리의 길이를 리턴해주면서 탐색을 종료해준다.

 

이미지 클릭