BOJ : 2146 다리 만들기

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

제가 푼 방식에는 두 가지 핵심이 있습니다.

먼저 각 섬의 모서리 부분을 찾고 각 모서리가 어느 섬의 것인지 구분하기 위한 라벨링 작업

두 번째는 각 섬에 대한 모서리 간의 거리 비교

입니다.

라벨링은 DFS로 돌면서 근처에 물이 있으면 vector에 삽입했습니다. 

한 지점에서 주위에 물이 두 군데 이상이면 중복 삽입되기 때문에 flag를 이용해 제외시켜주었습니다.

거리 비교는 BFS로 하려다가 굳이 그럴 필요가 없을 것 같아 서로 다른 라벨을 가지고 있는 섬끼리 비교하며 그냥 좌표를 빼줬습니다.

#include <cstdio>
#include <vector>
using namespace std;

int map[102][102], no=2, N, ans=987654321;
int pr[4] = { 1,-1,0,0 };
int pc[4] = { 0,0,1,-1 };
int visited[102][102];

struct Edge {
    int r, c, no;
};

vector<Edge> v;

void counting(int r, int c, int no) {
    visited[r][c] = 1;
    bool isPushed = false;
    for (int i = 0; i < 4; i++) {
        int nr = r + pr[i], nc = c + pc[i];
        if (visited[nr][nc]) continue;
        if (nr < 0 || nc < 0 || nr >= N || nc >= N) continue;
        if (!isPushed && map[nr][nc] == 0) {
            Edge edge;
            edge.r = r, edge.c = c, edge.no = no;
            v.push_back(edge);
            isPushed = true;
        }
        if (map[nr][nc]) counting(nr, nc, no);
    }
}

int ABS(int n) {
    if (n < 0) return -1 * n;
    else return n;
}

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            scanf("%d", &map[i][j]);
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (!visited[i][j] && map[i][j]) {
                counting(i, j, no++);
            }
        }
    }
    
    for (int i = 0; i < v.size()-1; i++) {
        int A_X = v[i].r, A_Y = v[i].c, A_No = v[i].no;
        for (int j = i + 1; j < v.size(); j++) {
            int B_X = v[j].r, B_Y = v[j].c, B_No = v[j].no;
            if (A_No != B_No) {
                int len = ABS(B_X - A_X) + ABS(B_Y - A_Y) - 1;
                if (len < ans) ans = len;
                
            }
        }
    }
    printf("%d\n", ans);
}