#17472. 다리 만들기 2
Problem
Solution
- 각 섬에 고유 번호 붙이기(오름차순)
섬끼리 연결을 해야하기 때문에 이를 식별해주어야 한다.
BFS or DFS를 이용하여 구할 수 있고 필자는 BFS를 사용하였다. - 각 섬들마다 연결시키는 모든 경우를 구하되, 각 경우마다 연결이 가능한지 거리를 측정하면서 확인한다.
→ 연결이 가능하면 해당 다리를 저장한다.(어디에서 어디로 연결되고 그럴 때 최소 비용 저장) - 다리를 선택해서 1개 이상 선택했을 때부터 모든 섬을 연결 시킬 수 있는지 확인한다.
→ 모든 섬을 연결할 수 있으면 최소비용 갱신
Answer
완탐 코드 보기
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
using namespace std;
int N, M, total_island, ans = 1e9;
int map[10][10];
bool visited[10][10]; // 섬에 번호 붙일 때 방문 체크 용도
int dist[7][7]; // dist[a][b]: a에서 b로 가는 경로 비용, 기본값 1000
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
vector<pair<int, int>> Island_pos[11]; // Island_pos[i]: i번 섬의 모든 좌표
vector<pair<pair<int, int>, int>> bridge_list; // a, b, c : a->b의 비용이 c인 다리 목록
bool connect[7][7]; // a, b와의 연결 상태 확인 용도
bool connect_island[7]; // i번 섬의 방문 체크 용도
bool selected[7 * 7]; // 간선의 모든 경우를 담기 위함( N(N-1)/2 )
void BFS(int x, int y, int id) { // 섬에 번호 붙이기
queue<pair<int, int> > q;
q.push({ x, y });
visited[x][y] = true;
map[x][y] = id;
Island_pos[id].push_back({ x, y });
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int dir = 0; dir < 4; ++dir) {
int d_x = x + dx[dir];
int d_y = y + dy[dir];
if (d_x > -1 && d_y > -1 && d_x < N && d_y < M) {
if (visited[d_x][d_y] || map[d_x][d_y] != 1) continue;
visited[d_x][d_y] = true;
map[d_x][d_y] = id;
Island_pos[id].push_back({ d_x, d_y });
q.push({ d_x, d_y });
}
}
}
}
void Go(int x, int y, int dir, int len, int start, int end) { // 거리 측정하기
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) return;
if (map[nx][ny] == end) {
if (len > 1) { // 거리 2이상인 경우만 연결 가능
if (dist[start][end] > len) { // 최소 거리 갱신
dist[start][end] = len;
dist[end][start] = len;
}
}
return;
}
else if (map[nx][ny] == 0) Go(nx, ny, dir, len + 1, start, end);
else return;
}
void MakeBridge(int start, int end) {
//Start에 해당되는 섬의 모든 좌표를 end에 해당되는 섬까지 도달해본다.
for (int i = 0; i < Island_pos[start].size(); i++)
{
int x = Island_pos[start][i].first;
int y = Island_pos[start][i].second;
for (int dir = 0; dir < 4; ++dir) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx > -1 && ny > -1 && nx < N && ny < M) {
if (map[nx][ny] == 0) Go(nx, ny, dir, 1, start, end); // 한 방향으로 가야함, 0인 지점 방문이니 거리 1
}
}
}
}
void GetDistance() { // 섬들끼리 1:1로 연결시키는 모든 경우
for (int i = 1; i < total_island; i++)
{
for (int j = i + 1; j < total_island; j++)
{
MakeBridge(i, j);
if (dist[i][j] == 1000) continue; // 연결 불가능한 경우
bridge_list.push_back({ {i, j}, dist[i][j] }); // (i -> j : 비용) 저장
}
}
}
bool CheckConnect() { // 조건에 맞게 모든 섬이 연결되어있는지 확인
memset(connect, false, sizeof(connect));
memset(connect_island, false, sizeof(connect_island));
for (int i = 0; i < bridge_list.size(); i++) // 선택한 다리 연결 표시
{
if (selected[i]) { // 연결 표시 (x->y, y->x)
int x = bridge_list[i].first.first;
int y = bridge_list[i].first.second;
connect[x][y] = connect[y][x] = true;
}
}
queue<int> q;
q.push(1); // 1번 섬(섬은 최소 2개)
connect_island[1] = true; // 1번 섬 방문 체크
int Island_cnt = 1;
bool flag = false;
while (!q.empty()) { // 모든 섬 방문가능한지 체크하는 부분
int cur = q.front();
q.pop();
if (Island_cnt == total_island - 1) {
flag = true;
break;
}
for (int i = 1; i < total_island; i++)
{
if (cur == i) continue;
if (connect[cur][i] && connect_island[i] == false) { // 현재 섬과 i번 섬이 연결되어있고 i번 섬을 방문하지 않았을 때
connect_island[i] = true;
q.push(i);
Island_cnt++;
}
}
}
return flag;
}
void SelectBridge(int idx, int cnt, int sum) {
if (cnt >= 1) {
if (CheckConnect() == true) {
if (ans > sum) ans = sum;
}
}
for (int i = idx; i < bridge_list.size(); ++i) {
if (selected[i] == true) continue;
selected[i] = true;
SelectBridge(i, cnt + 1, sum + bridge_list[i].second);
selected[i] = false;
}
}
int main() {
for (int i = 0; i < 7; ++i) {
for (int j = 0; j < 7; j++) {
dist[i][j] = 1000;
}
}
cin >> N >> M;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
cin >> map[i][j];
}
}
int id = 1;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
if (map[i][j] != 0 && !visited[i][j]) BFS(i, j, id++);
}
}
total_island = id;
GetDistance();
SelectBridge(0, 0, 0);
if (ans == 1e9) ans = -1;
cout << ans << "\n";
return 0;
}Solution
위 방식에서 1, 2까지는 동일
- 크루스칼 알고리즘을 사용한다.
Answer
- 코드 보기
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
using namespace std;
typedef pair<int, int> d;
struct Bridge {
int from;
int to;
int len;
};
int N, M, total, ans = 10000;
int map[10][10];
bool visited[10][10];
int parent[7];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
vector<d> island[7];
vector<Bridge> bridge;
int Go(int from, int to) {
int len = 10000;
for (int i = 0; i < island[from].size(); i++){
int x = island[from][i].first;
int y = island[from][i].second;
for (int dir = 0; dir < 4; ++dir) {
int nx = x; int ny = y;
int cur = 0;
while (true) {
if (len <= cur) break;
nx += dx[dir];
ny += dy[dir];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) break;
if (map[nx][ny] == 0) {
cur++;
}
else if (map[nx][ny] == to) {
if (cur < 2) break;
if (len > cur) len = cur;
break;
}
else break;
}
}
}
return len;
}
void GetDistance() {
Bridge b;
for (int i = 1; i <= total; ++i) {
for (int j = i + 1; j <= total; ++j) {
b.from = i; b.to = j;
b.len = Go(i, j);
if (b.len == 10000) continue;
bridge.push_back(b);
}
}
}
void BFS(int r, int c, int id) {
queue<d> q;
q.push({ r, c });
visited[r][c] = true;
map[r][c] = id;
island[id].push_back({ r, c });
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int dir = 0; dir < 4; ++dir) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if (map[nx][ny] != 1 || visited[nx][ny]) continue;
visited[nx][ny] = true;
map[nx][ny] = id;
island[id].push_back({ nx, ny });
q.push({ nx, ny });
}
}
}
void MakeLabel() {
int id = 1;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
if (map[i][j] == 0 || visited[i][j]) continue;
BFS(i, j, id++);
}
}
total = id - 1;
for (int i = 1; i <= total; ++i) {
parent[i] = i;
}
}
int cmp(Bridge a, Bridge b) {
return a.len < b.len;
}
int FindParent(int idx) {
if (parent[idx] == idx) return idx;
else return FindParent(parent[idx]);
}
void Union(int from, int to) {
int p1 = FindParent(parent[from]);
int p2 = FindParent(parent[to]);
if (p1 < p2) {
parent[to] = p1;
parent[p2] = p1;
}
else {
parent[from] = p2;
parent[p1] = p2;
}
}
bool CheckConnection() {
for (int i = 1; i <= total; ++i) {
if (FindParent(parent[i]) != 1) return false;
}
return true;
}
void Kruskal() {
sort(bridge.begin(), bridge.end(), cmp);
int cost = 0;
for (int i = 0; i < bridge.size(); ++i) {
int from = bridge[i].from; int to = bridge[i].to;
if(FindParent(from) == FindParent(to)) continue;
else {
Union(from, to);
cost += bridge[i].len;
}
}
if (CheckConnection()) ans = cost;
}
void Solve() {
MakeLabel();
GetDistance();
Kruskal();
}
int main() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> map[i][j];
}
}
Solve();
if (ans == 10000) ans = -1;
cout << ans << "\n";
return 0;
}