Algorithm/BOJ
침략자 진아 - 15812
jhg0406
2020. 3. 7. 05:16
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
//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;
}
|
cs |
https://www.acmicpc.net/problem/15812
15812번: 침략자 진아
2차원 공간의 세로의 크기와 가로의 크기를 의미하는 두 정수 N, M(2 ≤ N, M ≤ 20)이 주어진다. 예제 입력과 같이 마을의 지도가 주어진다. 0은 빈 공간을, 1은 마을이 있는 공간을 의미한다.
www.acmicpc.net
침략자 진아
그래프로 모델링 한 다음, bfs를 이용했습니다.
