[BOJ] 다리 만들기2

문제

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

섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.

다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를 연결되었다고 한다. 다리의 양 끝은 섬과 인접한 바다 위에 있어야 하고, 한 다리의 방향이 중간에 바뀌면 안된다. 또, 다리의 길이는 2 이상이어야 한다.

 

다리의 방향이 중간에 바뀌면 안되기 때문에, 다리의 방향은 가로 또는 세로가 될 수 밖에 없다. 방향이 가로인 다리는 다리의 양 끝이 가로 방향으로 섬과 인접해야 하고, 방향이 세로인 다리는 다리의 양 끝이 세로 방향으로 섬과 인접해야 한다.

 

섬 A와 B를 연결하는 다리가 중간에 섬 C와 인접한 바다를 지나가는 경우에 섬 C는 A, B와 연결되어있는 것이 아니다. 

 

아래 그림은 섬을 모두 연결하는 올바른 2가지 방법이고, 다리는 회색으로 색칠되어 있다. 섬은 정수, 다리는 알파벳 대문자로 구분했다.

다음은 올바르지 않은 3가지 방법이다

 

다리가 교차하는 경우가 있을 수도 있다. 교차하는 다리의 길이를 계산할 때는 각 칸이 각 다리의 길이에 모두 포함되어야 한다. 아래는 다리가 교차하는 경우와 기타 다른 경우에 대한 2가지 예시이다.

 

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

 

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

17472번: 다리 만들기 2

 

풀이

 

17472

맞았습니다!!

2040

0

C++14 / 수정

3973

11분 전

0) 풀이 시간 = 1시간 12분 

 

1) MST(최소 신장 트리)를 서로소 집합과 크루스칼 알고리즘을 사용하여 풀이한다. 

 

2) 부르트포스로 풀 수 있다고 하는데 영역을 지정하고 이어주는 데는 서로소 집합이 가장 깔끔한 것 같다. 

 

3) 일단 영역들을 라벨링 한다. (BFS, DFS 모두 가능)

 

4) 라벨링이 끝나면 영역들은 각자 정점이 된다. 이 정점들을 이어주는 간선을 찾으면 된다. (사이클을 형성하지 않고-> 서로소 집합 사용)

 

5) findEdges()에서는 한 다리는 한 방향으로만 이어지기 때문에 step을 늘려가면서 탐색했을 때 다른 정점이 나오는지 탐색하는 함수이다. 

만약 자기 자신의 정점 번호가 나온다면 잘못된 방향이기 때문에 break를 걸어서 다른 방향으로 나아갈 수 있게 해주고 

다른 정점을 만났다면 edges라는 백터에 {정점1, 정점2, 거리}를 넣어준다. 

 

6) findEdges가 끝나면 edges에는 간선의 정보가 저장되어있다. 

서로소 집합을 사용하여 사이클이 형성되지 않는 한에서 가장 최소의 간선 길이를 구하려면 

일단 sort를 통해 가장 길이가 짧은 간선을 앞으로 오게 한다. 

 

7) edges를 탐색하면서 다리의 길이가 1이하인 경우에는 조건에 맞지 않으므로 넘기고 

그 외에 find(정점1) != find(정점2) => 부모가 같지 않다면 사이클 형성 조건이 안된다. 라면 

같은 집합으로 넣어주고(union_find) 그 다리의 길이를 누적합한다. 

 

이때 다리가 형성되는 간선의 개수를 구해준다. 

 

8) 마지막으로 그래프에서 간선의 길이는 정점의 개수-1이므로 이 조건이 만족하면 다리의 길이 누적합을 출력하고 

아니면 -1 , sum==0이어도 -1을 출력하여 다리 형성이 불가능함을 나타낸다. 

 

---

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
int n, m, map[101][101], area = 1;
bool visited[101][101];
 
typedef pair<int, int> pp;
typedef pair<pp, int> ppp;
 
int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
 
int parent[7]; //섬은 최대 6개까지
 
vector<ppp> edges;
 
void printMap() {
     cout << '\n';
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cout << map[i][j] << " ";
        }
        cout << '\n';
    }
 cout << '\n';
}
 
bool compare(ppp &a, ppp &b)
{
    return a.second < b.second;
}
void renameAreas(int x, int y)
{
    visited[x][y] = true;
    map[x][y] = area;
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny])
            continue;
 
        if (map[nx][ny]) renameAreas(nx, ny);   
    }
}
 
void init(int n)
{
    for (int i = 1; i < n; i++)
    {
        parent[i] = i;
    }
}
int find(int a)
{
    if (parent[a] == a)
        return a;
    return parent[a] = find(parent[a]);
}
 
void union_find(int a, int b)
{
    int pA = find(a);
    int pB = find(b);
 
    if (pA != pB)
        parent[pA] = pB;
}
 
void findEdges(int x, int y)
{
    //다른 정점을 만날 때까지 한 방향으로 나아가면서 길이를 저장하낟.
   for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
    
        if (nx < 0 || nx >= n || ny < 0 || ny >= m ) continue;
        
        if (!map[nx][ny]) {
            int step = 2;
            int dist = 1;
            while(1) {
                int nnx = x + step * dx[i];
                int nny = y + step * dy[i];
 
                if (nnx < 0 || nnx >= n || nny < 0 || nny >= m ) break;
 
                if (map[nnx][nny]) {
                    if (map[nnx][nny] == map[x][y]) break; //올바른 방향이 아님 
                    edges.push_back(ppp(pp(map[x][y], map[nnx][nny]), dist));
                    break;
                }
                dist++;
                step++;
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> map[i][j];
            if (!map[i][j]) visited[i][j];
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (map[i][j] && !visited[i][j])
            //바다가 아니고 아직 안들렸다면 
            {
                renameAreas(i, j);
                area++;
            }
        }
    }
    //이제 다리 건설하기
    // printMap();
 
    //각 정점들 간의 간선을 연결해야 한다.
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (map[i][j])
            //섬에서 시작 
            {
                findEdges(i, j);
                //각 정점을 이어준다. 
            }
        }
    }
 
    sort(edges.begin(), edges.end(), compare);
    //거리가 짧은 순으로 정렬한다.
 
    init(area);
 
    int sum = 0; //다리 길이 합
    int idx = 0; //간선의 개수
 
    for (auto e : edges)
    {
        if (e.second <= 1)
            continue; //조건이 다리 길이는 2이상
 
        if (find(e.first.first) != find(e.first.second))
        {
            //서로 다른 정점을 가르킨다.
            union_find(e.first.first, e.first.second);
            //같은 그룹으로 묶어준다. 
            sum += e.second;
            idx++;
        }
    }
 
    //그래프에서 사이클이 생기지 않으려면 정점의 개수 -1은 간선의 개수이다.
    //idx(섬의 개수) 를 1부터 시작했기 때문에 2를 빼준다.  
    if (area-2 != idx) cout << -1 << '\n';
    else if (sum == 0) cout << -1 << '\n';
    else cout << sum << '\n';
    return 0;
}

 

[같이 풀면 좋은 문제]

2019/08/09 - [BOJ/코테 ] - [BOJ] 네트워크 연결