[BOJ] #17472 다리 만들기 2

[BOJ] #17472 다리 만들기 2

삼성 역량테스트 문제였다
MST와 BFS 구현 위주의 문제라 그냥 끝까지 풀어보았다.
그리고 엣지케이스가 생각보다 많아서 꽤 오랜 시간이 걸렸다(..)

FLOW

1. 각 섬을 Numbering해야한다. BFS로 진행하였다.
2. 섬과 섬 사이의 거리를 구한다. 이 때, 꼭 일직선으로만 진행해야한다.(진행 후 벡터에 저장하여 edge값으로 사용했다.)
3. 각 섬간의 관계를 가중치 그래프로 나타낸 뒤, Kruskal Algorithm을 적용한다.

• 가중치의 합을 구하다 보면 result가 0일 때에만 cout<<-1을 해주었는데, 이 외에도 섬이 모두 연결되지 않은 경우가 포함된다. 이를 위해 연결된 edge의 개수가 몇개인지도 체크해야한다. MST 특성 상 E = V-1이 된다.

  #include <algorithm>
  #include <iostream>
  #include <queue>
  #include <vector>
  using namespace std;
  const int MAX = 11;
  const int M = 7;
  const int E = 10000;
  int map[MAX][MAX];
  int n, m, idx, vsize, res, cnt;
  int dirX[4] = {1, 0, -1, 0};
  int dirY[4] = {0, 1, 0, -1};
  int root[M];
  bool vis[MAX][MAX];
  queue<pair<int, int>> island;
  vector<pair<int, int>> v[M];
  pair<int, pair<int, int>> edge[E];

  void makeIsland() {
    queue<pair<int, int>> q;

    int num = 1;
    while (!island.empty()) {
      int curX = island.front().first;
      int curY = island.front().second;
      island.pop();
      if (vis[curX][curY]) {
        continue;
      }
      vis[curX][curY] = true;
      map[curX][curY] = num;
      v[num].push_back(make_pair(curX, curY));
      for (int i = 0; i < 4; i++) {
        int nextX = curX + dirX[i];
        int nextY = curY + dirY[i];

        if (nextX < 0 || nextX >= m || nextY < 0 || nextY >= n) {
          continue;
        }
        if (vis[nextX][nextY]) continue;
        if (map[nextX][nextY] == 1) {
          map[nextX][nextY] = num;
          v[num].push_back(make_pair(nextX, nextY));
          q.push(make_pair(nextX, nextY));
          vis[nextX][nextY] = true;
        }
      }

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

        for (int i = 0; i < 4; i++) {
          int nextX = x + dirX[i];
          int nextY = y + dirY[i];
          if (nextX < 0 || nextX >= m || nextY < 0 || nextY >= n) {
            continue;
          }
          if (vis[nextX][nextY]) continue;
          if (map[nextX][nextY] == 1) {
            map[nextX][nextY] = num;
            v[num].push_back(make_pair(nextX, nextY));
            q.push(make_pair(nextX, nextY));
            vis[nextX][nextY] = true;
          }
        }
      }
      num++;
    }

    vsize = num;
  }

  void checkX(int startX, int startY) {
    for (int i = 0; i < 4; i++) {
      int nextX = startX + dirX[i];
      int nextY = startY + dirY[i];
      int len = 0;
      while (1) {
        if (nextX < 0 || nextX >= m || nextY < 0 || nextY >= n) {
          break;
        }
        if (map[nextX][nextY] != 0) {
          break;
        }
        nextX += dirX[i];
        nextY += dirY[i];
        len++;
      }
      if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n) {
        if (len >= 2) {
          edge[idx].first = len;
          edge[idx].second.first = map[startX][startY];
          edge[idx].second.second = map[nextX][nextY];
          idx++;
        }
      }
    }
  }

  void makeEdge() {
    for (int i = 1; i < vsize; i++) {
      for (int j = 0; j < v[i].size(); j++) {
        int startX = v[i][j].first;
        int startY = v[i][j].second;
        checkX(startX, startY);
      }
    }
  }

  int find(int x) {
    if (root[x] == x)
      return x;
    else {
      int parent = root[x];
      return root[x] = find(parent);
    }
  }

  void kruskal() {
    for (int i = 0; i < idx; i++) {
      int a = edge[i].second.first;
      int b = edge[i].second.second;
      int val = edge[i].first;

      int x = find(a);
      int y = find(b);
      if (x != y) {
        root[y] = x;
        res += val;
        cnt++;
      }
    }
  }

  int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        cin >> map[j][i];
        if (map[j][i] == 1) {
          island.push(make_pair(j, i));
        }
      }
    }
    makeIsland();
    makeEdge();
    sort(edge, edge + idx);

    for (int i = 1; i < vsize; i++) {
      root[i] = i;
    }

    kruskal();
    if (res == 0 || cnt != vsize - 2)
      cout << -1;
    else
      cout << res;
    return 0;
  }