[백준/BOJ] 17472 다리 만들기 2★- 접근과 풀이 (c++)

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

17472번: 다리 만들기 2

MST 복습문제 - 삼성 A형 기출문제

 

---

접근 방법

 

최대 10*10의 격자칸에 섬이 존재하고, 섬을 다리로 잇는 최소 비용을 구한다.

 

문제를 보았을때 접근 방법은 누구나 비슷하게 쉽게 떠올릴 수 있을 것 같고, 구현이 조금 많이 어려웠다.

 

1. 각 섬에 dfs/bfs로 번호를 붙인다.

2. 각 섬에서 섬으로 이동하는 dist를 구한다.

3. MST를 계산한다.

 

1. 각 섬에 번호를 붙이는것은 백준에 같은 문제가 있고, 너무 기초 dfs/bfs문제니까 자세히 설명하지 않는다.
   
   
2. 섬과 섬 간의 거리를 구하는 방법은 다음과 같다.
   하나의 섬에서, 해당 섬의 모든 좌표에서 4방향으로 나아가며 다른 섬을 만나면 2차원 matrix에 저장한다.
   그리고 하나의 섬이 갖는 좌표를 1번 단계에서 벡터에 저장하면 좀 더 간편하다.
   >더 나은 방법으로, 그냥 N*N배열에서 시작하는 것이 좀 더 편할 것 같다.
   
   나는 위의 방법을 처음에 떠올렸으나, 조금 다른 방식으로 계산했다가 처참히 실패했다.
   A섬과 B섬의 모든 좌표를 각각 a*b 개 만큼 대응하여 x축 또는 y축이 같은것이 있다면 동일선 상에 존재하므로 차이를 dist로 저장하고, dist의 최솟값을 구했다. 그러나 이는 ㄷ자같은 섬이 존재하거나 섬의 모양이 조금만 불규칙해도 안된다.
   
   
3. MST를 구하는 방법은 이전 포스팅에 잘 나와있다.
   추가로 모든 섬이 연결되었는지 확인해야하므로, 간선이 (섬의 개수-1)가 맞는지 확인하면 된다.

 

수 많은 알고리즘과 테크닉이 결합된 문제로, 풀이를 떠올리는 건 어렵지 않았으나 구현에서 시간이 너무 오래 걸렸다.

그리고 최대 격자가 100칸밖에 안되므로 시간복잡도도 거의 고려하지 않아도 된다.

 

구현 문제 연습좀 해야겠다.!

 

---

풀이

    

tag : MST, dfs, bfs, bruteforce, implement

 

#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
#define INF 0x3f3f3f3f
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};
int N, M;
int arr[11][11];
int visited[11][11] = {0};
int idx = 1; //섬의 idx
vector<pii> coords[7]; //6개 섬 구성좌표
vector<pair<int, pii>> edges; //거리, (idx1 idx2)
int distArr[7][7];
int parent[7] = {0, 1, 2, 3, 4, 5, 6};

void dfs(int r,int c){
  coords[idx].push_back(mp(r, c));
  visited[r][c] = 1;
  arr[r][c] = idx;

  for (int i = 0; i < 4;i++){
    int nr = r + dy[i];
    int nc = c + dx[i];
    if(nr<0 || nc<0 || nr>=N || nc>=M)
      continue;
    if(arr[nr][nc]==1 && visited[nr][nc]==0)
      dfs(nr, nc);
    
  }
}
void calcDist(int idx){
  /* idx섬부터 뻗어나가는 최소거리 구하기*/

  for (int i = 0; i < coords[idx].size();i++){
    pii coord = coords[idx][i];
    for (int j = 0; j < 4;j++){
      //4방향쭉쭉
      int dist = 1;
      while(1){
        int nr = coord.first + dy[j]*dist;
        int nc = coord.second + dx[j]*dist;

        if(nr<0 || nc<0 || nr>=N || nc>=M || arr[nr][nc]==idx)
          break;

        if(arr[nr][nc]!=0){//섬 발견
          if(dist==2) //거리가1
            break;
          distArr[idx][arr[nr][nc]] = distArr[arr[nr][nc]][idx] = min(distArr[idx][arr[nr][nc]],dist - 1);
          break;
        }
        dist++;
      }
    }
  }
}
int findParent(int idx){
  if(parent[idx]==idx)
    return idx;
  return findParent(parent[idx]);
}
void unionParent(int idx1,int idx2){
  int pr1 = findParent(idx1);
  int pr2 = findParent(idx2);
  if(pr1<pr2)
    parent[pr2] = pr1;
  else
    parent[pr1] = pr2;
}
int main(){
  cin >> N >> M;
  for (int i = 0; i < N;i++){
    for (int j = 0; j < M;j++)
      cin >> arr[i][j];
  }
  for (int i = 0; i < N;i++){
    for (int j = 0; j < M;j++){
      if(arr[i][j] && visited[i][j]==0){
        dfs(i, j);
        idx++;
      }
    }
  }

  memset(distArr, INF, sizeof(distArr));
  for (int i = 1; i < idx;i++)
    calcDist(i);
  
 
  for (int i = 1; i < idx;i++){
    for (int j = i+1; j < idx;j++){
      if(distArr[i][j]==INF)
        continue;
      edges.push_back(mp(distArr[i][j], mp(i, j)));
    }
   
  }
   sort(edges.begin(), edges.end());

  int ans = 0;
  int cntEdge = 0;

  /* MST*/
  for (int i = 0; i < edges.size();i++){
    int pr1 = findParent(edges[i].second.first);
    int pr2 = findParent(edges[i].second.second);
    if(pr1==pr2)
      continue;
    cntEdge++;
    ans += edges[i].first;
    unionParent(edges[i].second.first, edges[i].second.second);
  }
  if(cntEdge!=idx-2)
    ans=-1;
  cout << ans; 
}