2146번 다리 만들기

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

DFS와 BFS 2개 모두 활용하는 문제이다.

DFS를 통해 각 섬들을 그룹화 시켜주고, BFS를 통해 퍼져나가는 작업을 실행한다.

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 101
 
int m[Max][Max], N, answer = 2e9;
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
bool visit[Max][Max];
 
void dfs(int r, int c, int group)
{
    visit[r][c] = true;
    m[r][c] = group;
    for (int i = 0; i < 4; i++)
    {
        int y = r + dy[i];
        int x = c + dx[i];
        if (y < 0 || y >= N || x < 0 || x >= N || visit[y][x] || !m[y][x]) continue;
        dfs(y, x, group);
    }
}
 
int bfs(int r, int c, int num)
{
    int ret = -1;
    memset(visit, false, sizeof(visit));
    visit[r][c] = true;
    queue<pair<int, int> > q;
    q.push({ r, c });
 
    while (!q.empty())
    {
        int qs = q.size();
 
        while (qs--)
        {
            r = q.front().first;
            c = q.front().second;
 
            q.pop();
 
            if (m[r][c] != 0 && m[r][c] != num) return ret;
            
            for (int i = 0; i < 4; i++)
            {
                int y = r + dy[i];
                int x = c + dx[i];
 
                if (y < 0 || y >= N || x < 0 || x >= N || visit[y][x] || m[y][x] == num) continue;
            
                visit[y][x] = true;
                q.push({ y, x });
            }
        }
 
        ++ret;
    }
 
    return 2e9;
}
 
int main(void)
{
    //freopen("C:\\Users\\park7\\Desktop\\in.txt", "r", stdin);
    //cin.tie(0);
 
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)     scanf("%d", &m[i][j]);
 
    int gc = 1;
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)    
            if (!visit[i][j] && m[i][j])
            {
                dfs(i, j, gc);
                ++gc;
            }
 
    for (int i = 0; i < N; i++) 
        for (int j = 0; j < N; j++)
            if(m[i][j])
                answer = min(answer, bfs(i, j, m[i][j]));
        
    printf("%d\n", answer);
 
    return 0;
}