[BaekJoon] 2146 다리 만들기 :: monton

문제

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

풀이

DFS+BFS를 모두 사용하는 문제

1. DFS를 이용하여 모든 섬을 라벨링한다

2. 모든 섬을 queue에 담는다.

3. BFS와 거리 공식(|x1-x2|+|y1-y2|)를 이용하여 섬사이의 모든 거리 경우의 수 중 가장 작은 값을 구한다.

(섬 중앙에서 연결이 될 경우가 있는데 어차리 최소 거리가 아니므로 상관없음)

코드

#include <iostream>
#include <queue>
 
using namespace std;
 
int N,cnt,ans=10000;
int arr[101][101];
int visit[101][101];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
 
queue <int>px;
queue <int>py;
queue <int>pnum;
void func(int x, int y) {
    if (x < 0 || x >= N || y < 0 || y >= N) return;
    if (visit[x][y] || !arr[x][y]) return;
    
    visit[x][y] = 1;
    px.push(x);
    py.push(y);
    pnum.push(cnt);
 
    for (int i = 0; i < 4; i++) {
            func(x + dir[i][0], y + dir[i][1]);
    }
}
 
int absnum(int x1, int x2, int y1, int y2) {
    int x = x1 - x2 > 0 ? x1 - x2 : x2 - x1;
    int y = y1 - y2 > 0 ? y1 - y2 : y2 - y1;
    return x + y;
}
 
int main() {
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[i][j]&&!visit[i][j]) cnt++, func(i, j);
        }
    }
 
    while (!px.empty()) {
        int x = px.front();
        int y = py.front();
        int num = pnum.front();
 
        px.pop();
        py.pop(); 
        pnum.pop();
 
        queue <int>px2=px;
        queue <int>py2=py;
        queue <int>pnum2=pnum;
 
        while (!px2.empty()) {
            int x2 = px2.front();
            int y2 = py2.front();
            int num2 = pnum2.front();
 
            px2.pop(); 
            py2.pop();
            pnum2.pop();
 
            if (num == num2) continue;
 
            int res = absnum(x, x2, y, y2)-1;
            ans = ans < res ? ans : res;
        }
    }
 
    cout << ans;
 
}

분명 절대값 구하는 함수랑 min값 구하는 c++ 함수가 있을텐데

그런 함수를 익숙하게 쓸수 있게 연습을 해야겠다.