[BaekJoon][2146] 다리 만들기

BAEKJOON ONLINE JUDGE

2146 다리 만들기

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

풀이 1. DFS & BFS

DFS 또는 BFS로 섬들을 잇고 BFS로 섬 주위로 다리를 지어 섬들을 연결하면 된다.

섬마다 한칸씩 다리를 지어 만나도록 연결하였다. 

0ms

#include <stdio.h>
#include <queue>
using namespace std;
 
int inputmap[100][100];
int map[100][100];
int bridge[100][100];
int n;
int islandcnt;
int mn = 10000;
queue<pair<int, int>> que;
 
void input()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &inputmap[i][j]);
        }
    }
}
 
void init()
{
    while (!que.empty()) que.pop();
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            bridge[i][j] = 0;
        }
    }
}
 
void dfs(int y, int x, int cnt)
{
    int dy[4] = { -1, 0, 0, 1 };
    int dx[4] = { 0, -1, 1, 0 };
    int nexty, nextx;
 
    while (!que.empty())    que.pop();
 
    que.push(make_pair(y, x));
    map[y][x] = cnt;
 
    while (!que.empty()) {
        y = que.front().first;
        x = que.front().second;
        que.pop();
        
 
        for (int i = 0; i < 4; i++) {
            nexty = y + dy[i];
            nextx = x + dx[i];
 
            if (nexty < n && nexty >= 0 && nextx < n && nextx >= 0) {
                if (inputmap[nexty][nextx] && !map[nexty][nextx])        
                {
                    que.push(make_pair(nexty, nextx));
                    map[nexty][nextx] = cnt;
                    
                }
            }
        }
    }
}
 
void labeling()
{
    islandcnt = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (inputmap[i][j] && !map[i][j])    dfs(i, j, islandcnt++);
        }
    }
}
 
void bfs(int num)
{
    int dy[4] = { -1, 0, 0, 1 };
    int dx[4] = { 0, -1, 1, 0 };
    int nexty, nextx;
 
    init();
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j] == num) {
                for (int k = 0; k < 4; k++) {
                    nexty = i + dy[k];
                    nextx = j + dx[k];
 
                    if (nexty < n && nexty >= 0 && nextx < n && nextx >= 0) {
                        if (!map[nexty][nextx]) {
                            bridge[nexty][nextx] = 1;
                            que.push(make_pair(nexty, nextx));
                        }
                    }
                }
            }
        }
    }
 
    while (!que.empty()) {
        int y = que.front().first;
        int x = que.front().second;
        que.pop();
 
        for (int k = 0; k < 4; k++) {
            nexty = y + dy[k];
            nextx = x + dx[k];
 
            if (nexty < n && nexty >= 0 && nextx < n && nextx >= 0) {
 
                if (map[nexty][nextx] && map[nexty][nextx] != num) {
                    if (bridge[y][x] < mn) mn = bridge[y][x];
                    return;
                }
 
                if (!map[nexty][nextx] && !bridge[nexty][nextx]) {
                    bridge[nexty][nextx] = bridge[y][x] + 1;
                    que.push(make_pair(nexty, nextx));
                }
            }
        }
    }
}
 
void linkisland()
{
    for (int i = 1; i < islandcnt; i++) {
        bfs(i);
    }
}
 
int main()
{
    input();
 
    labeling();
 
    linkisland();
 
    printf("%d\n", mn);
 
    return 0;
}

풀이 2. DFS

BFS없이 섬을 labeling 하여 번호를 주고, map을 계속 돌면서 섬주변에 다리를 하나씩 늘린다.

다리를 짓는 과정은 어차피 map을 (최대) 전체 한번 다 도는 것이기 때문에 시간이 많이 걸리진 않는다. 

but 역시 다리를 놓을 자리만 저장해서 짓는 것보다는 확실히 느리다.

68ms

#include <stdio.h>
#include <queue>
using namespace std;
 
#define LI    100000
 
int n;
int inputdata[100][100];
int map[100][100];
queue<pair<int, int>> que;
int dy[4] = { -1, 0, 0, 1 };
int dx[4] = { 0, -1, 1, 0 };
 
void input()
{
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &inputdata[i][j]);
        }
    }
}
 
void dfs(int y, int x, int num)
{
    int nexty, nextx;
 
    map[y][x] = num;
 
    for (int i = 0; i < 4; i++) {
        nexty = y + dy[i];
        nextx = x + dx[i];
 
        if (nexty >= 0 && nexty < n && nextx >= 0 && nextx < n) {
            if (!map[nexty][nextx]) {
                if (inputdata[nexty][nextx])
                    dfs(nexty, nextx, num);
                else {
                    map[nexty][nextx] = num + 1;
                    que.push(make_pair(nexty, nextx));
                }
            }
        }
    }
}
 
void island()
{
    for (int i = 0, cnt = 1; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (inputdata[i][j] && !map[i][j]) {
                dfs(i, j, cnt * LI);
                cnt++;
            }
        }
    }
}
 
int linkbridge()
{
    int x, y;
    int nexty, nextx;
    int min = n * n;
    int temp;
 
    while (!que.empty()) {
        y = que.front().first;
        x = que.front().second;
        que.pop();
 
        for (int i = 0; i < 4; i++) {
            nexty = y + dy[i];
            nextx = x + dx[i];
 
            if (nexty < n && nexty >= 0 && nextx < n && nextx >= 0) {
                if (map[nexty][nextx]) {
                    if (map[nexty][nextx] / LI != map[y][x] / LI) {
                        temp = map[nexty][nextx] % LI + map[y][x] % LI;
 
                        if (temp < min)    min = temp;
                    }
                }
                else { 
                    map[nexty][nextx] = map[y][x] + 1;
                    que.push(make_pair(nexty, nextx));
                }
            }
        }
    }
 
    return min;
}
 
int main()
{
    input();
 
    island();
 
    printf("%d\n", linkbridge());
 
    return 0;
}