백준 2146 - 다리 만들기

문제

 

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

2146번: 다리 만들기

 

 

풀이

 

먼저 섬을 번호 순으로 그룹화를 시킨다. 그리고 각 번호가 다른 그룹사이에서의 최소 칸 수를 구하면 되는 문제이다. 

 

섬을 번호 순으로 그룹화 하는 방법은 그래프 탐색을 진행하면서 상하좌우로 연결되어 있는 좌표들에 같은 값을 부여하면 된다.

 

다른 그룹사이에서 최소 칸 수를 구하기 위해서 bfs 탐색을 이용한다. 예를 들어, 1번 그룹과 2번 그룹 사이의 최소 길이를 구하기 위해서는 1번 그룹의 가장자리를 1칸씩 더해 가면서 2번 그룹이 맞는지를 확인하는 과정을 반복하면 된다. 그러기 위해서는 1번 그룹의 가장자리부터 시작을 해야되는데, 1번 그룹의 모든 좌표를 큐에 저장한 후 좌표를 하나씩 꺼내서 상하좌우로 이동했을 때 1번 그룹이 아닌 좌표가 있으면 큐에서 꺼낸 그 좌표는 그 그룹의 가장자리 좌표가 되게 된다. 그 좌표에서 부터 다음 그룹 까지의 최소 길이를 구하면 된다. 

 

문제에서 두 개의 섬 사이의 최소 길이만을 요구하고 있으므로 N개의 섬이 있을 때 N-1번만 반복을 하면 된다. 예를 들어, 세 개의 섬이 있을때 2번 섬 까지만 최소 길이를 구하면 된다. 3번 섬은 1번 섬과 2번 섬의 경우에서 답이 나오게 되므로 굳이 하지 않아도 된다.  

 

 

코드

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
int N, group;
int graph[102][102];
bool visit[102][102];
queue< pair<int, int> > q;
pair<int, int> pos[4] = { {1,0}, {-1, 0}, {0,1}, {0, -1} };
int result = 987654321;
 
void bfs_g(int i, int j)
{
    q.push({i, j});
    visit[i][j] = true;
 
    while(!q.empty())
    {
        i = q.front().first;
        j = q.front().second;
        q.pop();
        graph[i][j] = group;
 
        for (int k=0; k<4; k++)
        {
            int nextI = i + pos[k].first;
            int nextJ = j + pos[k].second;
 
            if (graph[nextI][nextJ] && !visit[nextI][nextJ])
            {
                q.push({nextI, nextJ});
                visit[nextI][nextJ] = true;
            }
        }
    }
}
 
int bfs_l(int group_num)
{
    while(!q.empty()) q.pop();
 
    for (int i=1; i<=N; i++)
        for (int j=1; j<=N; j++)
            if (graph[i][j] == group_num)
            {
                visit[i][j] = true;
                q.push({i, j});
            }
        
    int cnt = 0;
    while (!q.empty())
    {
        int curSize = q.size();
        for (int i=0; i<curSize; i++)
        {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
 
            for (int i=0; i<4; i++)
            {
                int nextX = x + pos[i].first;
                int nextY = y + pos[i].second;
        
                if (graph[nextX][nextY] && graph[nextX][nextY] != group_num) 
 return cnt;
                if (!graph[nextX][nextY] && !visit[nextX][nextY] 
 && nextX<=N && nextY<=N && nextX>=1 && nextY>=1)
                {
                    visit[nextX][nextY] = true;
                    q.push({nextX, nextY});
                }
                
            }
        }
        cnt++;
    }
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> N;
 
    for (int i=1; i<=N; i++) 
        for (int j=1; j<=N; j++)
            cin >> graph[i][j];
        
    for (int i=1; i<=N; i++)
        for (int j=1; j<=N; j++)
            if (graph[i][j] && !visit[i][j]) 
            {
                group++;
                bfs_g(i, j);
            }
            
    for (int i=1; i<group; i++)
    { 
        memset(visit, 0, sizeof(visit));
        result = min(result, bfs_l(i));
    }
 
    cout << result;
    
    return 0;
}