[BOJ] 2146. 다리 만들기

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

4963. 섬의 개수 문제의 확장판(?)같은 문제다.

먼저 섬을 잇는 다리를 만들기 위해 각 섬을 구분해야 한다.

각 섬을 구분하였다면,

각 섬의 끝 지점에서 다른 섬 끝 지점으로 도달할 때까지 거리를 구하게 되는데,

그 거리의 최솟값을 구하면 된다.

#. Code

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
#define pos pair<int, int>
#define x first
#define y second
 
int n, k = 2, ans = 2147000000;
int map[105][105], dist[105][105];
int dx[] = { 1, 0, -1, 0 }, dy[] = { 0, 1, 0, -1 };
 
void dfs(int x, int y)
{
    int i;
    
    map[x][y] = k;
    for (i = 0; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
 
        if (xx <= 0 || xx > n || yy <= 0 || yy > n) continue;
        if (map[xx][yy] == 1) {
            dfs(xx, yy);
        }
    }
}
 
void bfs(int k)
{
    int i, j;
    queue<pos> q;
    memset(dist, -1, sizeof(dist));
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            if (map[i][j] == k) {
                q.push({ i, j });
                dist[i][j] = 0;
            }
        }
    }
            
    while (!q.empty()) {
        pos now = q.front();
        q.pop();
 
        for (i = 0; i < 4; i++) {
            int xx = now.x + dx[i];
            int yy = now.y + dy[i];
 
            if (xx <= 0 || xx > n || yy <= 0 || yy > n) continue;
            if (map[xx][yy] && map[xx][yy] != k) {
                if (ans > dist[now.x][now.y])
                    ans = dist[now.x][now.y];
                return;
            }
 
            if (!map[xx][yy] && dist[xx][yy] == -1) {
                dist[xx][yy] = dist[now.x][now.y] + 1;
                q.push({ xx, yy });
            }
        }
    }
}
 
int main(void)
{
    int i, j;
    // freopen("input.txt", "rt", stdin);
    scanf("%d", &n);
 
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            scanf("%d", &map[i][j]);
 
    // 대륙 번호 지정, (2번 부터)
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            if (map[i][j] == 1) {
                dfs(i, j);
                k++;
            }
        }
    }
 
    for (i = 2; i < k; i++) 
        bfs(i);
 
    printf("%d\n", ans);
 
    return 0;
}

line 13~27) 각 섬을 구분하여 번호를 붙여주는 함수

line 17) 현재 좌표의 땅에 번호를 표시

line 18~26) 현재 좌표로부터 동서남북에 땅이 존재한다면 같은 섬이므로

line 23) 다음 좌표와 함께 dfs() 호출

line 29~64) 다른 섬과의 거리를 저장

line 34~41) 해당 좌표가 방문하려는 섬의 번호라면

line 37) queue에 push해주고

lien 38) dist[][]에 땅이라고 표시

line 43~63) 방문해야하는 좌표에 모두 방문할 때까지 반복

line 52~56) 다음 좌표가 땅인데 다른 섬이라면

line 53~54) 두 섬을 연결하는 최소 길이와 비교하여 수정

line 55) 다른 섬에 도달하였으므로 return

line 58~61) 다음 좌표가 땅이 아니고, 방문하지 않은 바다라면

line 59) 현재 좌표까지의 거리 + 1

line 60) 다음 좌표도 방문하기 위해 queue에 push

line 77~84) 각 섬에 번호를 붙여준다.

line 79~81) 해당 지점에 땅이 있을 경우

line 80) 현재 k의 번호로 땅에 표시를 해준다.

line 81) 해당 번호로 표시를 해주었으니 k++

line 86~87) 구분된 각 섬을 방문하면서 다른 섬과 연결할 수 있는 다리의 길이를 dist[][]에 저장

#. Other Code

/*
reference : subinium
*/
 
#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
 
const int dx[4] = { 0, 1, 0, -1 }, dy[4] = { 1, 0, -1, 0 };
int N, MP[105][105], ck[105][105], dist[105][105];
 
void dfs(int col, int idx) {
    int x = idx / (N + 1), y = idx % (N + 1);
    ck[x][y] = col;
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i], yy = y + dy[i];
        if (!xx || !yy || xx > N || yy > N || ck[xx][yy] || !MP[xx][yy]) continue;
        dfs(col, xx * (N + 1) + yy);
    }
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie();
    queue<pair<int, int> > point;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) cin >> MP[i][j];
    }
    int idx = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (MP[i][j] && !ck[i][j]) {
                dfs(++idx, i * (N + 1) + j);
            }
        }
    }
    memset(dist, -1, sizeof(dist));
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (ck[i][j]) {
                point.push({ i * (N + 1) + j, ck[i][j] });
                dist[i][j] = 0;
            }
        }
    }
    int ans = 10001;
    while (!point.empty()) {
        auto tp = point.front(); point.pop();
        int idx = tp.first, col = tp.second;
        int x = idx / (N + 1), y = idx % (N + 1);
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i], yy = y + dy[i];
            if (!xx || !yy || xx > N || yy > N || ck[xx][yy] == col) continue;
            if (ck[xx][yy]) {
                ans = min(ans, dist[x][y] + dist[xx][yy]);
                continue;
            }
            ck[xx][yy] = col;
            dist[xx][yy] = dist[x][y] + 1;
            point.push({ xx * (N + 1) + yy, col });
        }
    }
    cout << ans << '\n';
}

line 9~17) 각 섬에 번호를 표시하기 위한 함수

line 10) 현재 좌표 추출

line 11) 현재 좌표에 번호(idx)를 표시

line 12~16) 다음 좌표(동서남북)를 탐색

line 14) 다음 좌표가 범위 안에 없거나, 방문을 했었거나, 바다인 경우 pass

line 15) 그 외의 경우는 idx, 현재 좌표와 함께 dfs() 호출

line 26~33) 섬을 구분하기 위한 단계

line 29~30) 만일 현재 좌표가 땅이고 방문하지 않았다면

line 30) idx, 현재 좌표와 함께 dfs() 호출

line 35~42) 모든 좌표를 탐색하는데

line 37~40) 방문했던 좌표(땅이 있는 좌표)라면

line 38) 해당 좌표와 해당 섬의 번호를 queue에 push

line 44~59) 방문해야할 좌표를 모두 방문할 때까지 반복

line 48~58) 현재 좌표로부터 다음좌표(동서남북)를 탐색

line 50) 다음 좌표가 범위 안에 없거나, 같은 섬이라면 pass

line 51~54) 그렇지 않고, 다른 섬에 도달했다면

line 52) 결과값보다 작다면 수정

line 53) 더이상 다음 좌표를 탐색할 필요가 없으므로 pass

line 55) 다음 좌표가 바다라면 현재 섬 번호를 저장

line 56) 다음 좌표의 거리는 현재 좌표까지 거리 + 1

line 57) 다음 좌표를 방문해보기위해 queue에 push

* check 배열을 안 쓰고, 메모리를 줄이려다가 오히려 속도가 느려졌다.

  이 코드에서는 ckeck 배열을 잘 활용해서(섬 번호를 저장) 더 효율적인 것 같다.