침략자 진아 - 15812

//15812 - 침략자 진아
 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int N, M;
int V, E;
int xnum = 0;
int arr[20][20];
int isVil[400];
int xarr[4] = {0,0,1,-1};
int yarr[4] = {1,-1,0,0};
vector<vector<int>> adj;
 
void init()
{
    cin >> N >> M;
    string s;
    for(int i = 0; i<N; ++i)
    {
        cin >> s;
        for(int j = 0; j<M; ++j)
        {
            arr[i][j] = s[j] - '0';
            if(arr[i][j])
                ++xnum, isVil[i*M+j] = 1;
            else isVil[i*M+j] = 0;
        }
    }
    V = N*M;
    adj = vector<vector<int>>(V);
    for(int i = 0; i<N; ++i)
        for(int j = 0; j<M; ++j)
            for(int k = 0; k<4; ++k)
            {
                int i2 = i + xarr[k];
                int j2 = j + yarr[k];
                if(i2 >= 0 && i2 < N && j2 >= 0 && j2 < M)
                    adj[i*M+j].push_back(i2*M+j2), adj[i2*M+j2].push_back(i*M+j);
            }
}
 
int bfs(int u, int v)
{
    int num = xnum;
    if(!num) return 0;
    vector<int> discovered(V, -1);
    queue<int> Q;
    Q.push(u), Q.push(v);
    discovered[u] = discovered[v] = 0;
 
    while(!Q.empty())
    {
        int here = Q.front(); Q.pop();
        for(int i = 0; i<adj[here].size(); ++i)
        {
            int there = adj[here][i];
            if(discovered[there] == -1)
            {
                discovered[there] = discovered[here] + 1;
                if(isVil[there])
                    --num;
                Q.push(there);
                if(num == 0)
                    return discovered[there];
            }
        }
    }
    return 0;
}
 
int main()
{
    init();
    int ans = 1000000000;
    for(int u = 0; u < V; ++u)
        for(int v = 0; v < V; ++v)
            if(u != v && !isVil[u] && !isVil[v])
                ans = min(ans, bfs(u, v));
    cout << ans;
}

 

 

 

 

 

 

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

15812번: 침략자 진아

 

 

 

 

 

 

침략자 진아

그래프로 모델링 한 다음, bfs를 이용했습니다.