문제 링크

🔷 분류

구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색, 최소 스패닝 트리

✒️ 문제 설명

섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다.
이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.

섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말한다.
아래 그림은 네 개의 섬으로 이루어진 나라의 예시이다.

다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다.
다리를 연결해서 모든 섬을 연결하려고 한다.

다리의 양 끝은 섬과 인접한 바다 위에 있어야 하고,
다리의 방향이 중간에 바뀌면 안 되며, 길이는 2 이상이어야 한다.

다리의 방향은 가로 또는 세로만 가능하다.

섬 A에서 섬 B로 가는 다리가 섬 C와 인접한 바다를 지나가더라도
섬 C는 연결된 것으로 보지 않는다.

올바른 연결 예시

  • 첫 번째 경우: 총 다리 길이 13
  • 두 번째 경우: 총 다리 길이 9 (최소)

올바르지 않은 연결 예시

  • 다리의 방향이 중간에 바뀐 경우
  • 다리의 길이가 1인 경우
  • 가로 다리가 섬과 올바르게 연결되지 않은 경우

다리가 교차하는 경우

다리가 교차하더라도 각 칸은 모든 다리의 길이에 포함된다.

나라의 정보가 주어졌을 때
모든 섬을 연결하는 다리 길이의 최솟값을 구해보자.

⬅️ 입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다.
둘째 줄부터 N개의 줄에 지도의 정보가 주어진다.
각 줄은 M개의 수로 이루어져 있으며,
0은 바다, 1은 땅을 의미한다.

➡️ 출력

모든 섬을 연결하는 다리 길이의 최솟값을 출력한다.
모든 섬을 연결하는 것이 불가능하면 -1을 출력한다.

💻 코드 (C++)

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
using namespace std;

int n, m;
int island = 1;
int map[101][101];
bool visit[101][101];
bool visit2[101][101];
int p[7];

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

typedef struct Edge {
  int s, e, v;
  bool operator>(const Edge& temp) const {
    return v > temp.v;
  }
} Edge;

priority_queue<Edge, vector<Edge>, greater<Edge>> pq;

// 섬 번호 매기기 
void makeIsland(int i, int j) {
  queue<pair<int, int>> q;
  q.push({i, j});
  visit[i][j] = true;
  map[i][j] = island;

  while(!q.empty()) {
    int x = q.front().first;
    int y = q.front().second;
    q.pop();

    for(int k = 0; k < 4; k++) {
      int nx = x + dx[k];
      int ny = y + dy[k];

      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if(visit[nx][ny]) continue;
      if(map[nx][ny] == 0) continue;

      visit[nx][ny] = true;
      map[nx][ny] = island;
      q.push({nx, ny});
    }
  }
}

// 다리 만들기 (직선 탐색) 
void makeBridge(int i, int j) {
  int isNum = map[i][j];

  for(int d = 0; d < 4; d++) {
    int nx = i + dx[d];
    int ny = j + dy[d];
    int len = 0;

    while(nx >= 0 && nx < n && ny >= 0 && ny < m) {
      if(map[nx][ny] == isNum) break;

      if(map[nx][ny] != 0) {
        if(len >= 2) {
          pq.push({isNum, map[nx][ny], len});
        }
        break;
      }

      nx += dx[d];
      ny += dy[d];
      len++;
    }
  }
}

int find(int x) {
  if(x == p[x]) return x;
  return p[x] = find(p[x]);
}

void uni(int a, int b) {
  a = find(a);
  b = find(b);
  if(a != b) p[b] = a;
}

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 >> map[i][j];
    }
  }

  // 1. 섬 번호 매기기 -> BFS
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
      if(map[i][j] != 0 && !visit[i][j]) {
        makeIsland(i, j);
        island++;
      }
    }
  }

  // 2. 다리 만들기
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
      if(map[i][j] != 0) {
        makeBridge(i, j);
      }
    }
  }

  // 3. 가장 짧은 다리 길이 -> MST && UF
  for(int i = 1; i < island; i++) {
    p[i] = i;
  }

  int used = 0;
  int ans = 0;

  while(!pq.empty()) {
    Edge now = pq.top();
    pq.pop();

    if(find(now.s) != find(now.e)) {
      uni(now.s, now.e);
      ans += now.v;
      used++;
    }
  }

  if(used == island - 2) cout << ans;
  else cout << -1;

  return 0;
}

글 이동

Comments

참고