백준 17472 : 다리 만들기 2
다리 만들기 2 성공
| 1 초 | 512 MB | 16036 | 5635 | 3397 | 31.451% |
문제
섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.
섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.
다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를 연결되었다고 한다. 다리의 양 끝은 섬과 인접한 바다 위에 있어야 하고, 한 다리의 방향이 중간에 바뀌면 안된다. 또, 다리의 길이는 2 이상이어야 한다.
다리의 방향이 중간에 바뀌면 안되기 때문에, 다리의 방향은 가로 또는 세로가 될 수 밖에 없다. 방향이 가로인 다리는 다리의 양 끝이 가로 방향으로 섬과 인접해야 하고, 방향이 세로인 다리는 다리의 양 끝이 세로 방향으로 섬과 인접해야 한다.
섬 A와 B를 연결하는 다리가 중간에 섬 C와 인접한 바다를 지나가는 경우에 섬 C는 A, B와 연결되어있는 것이 아니다.
아래 그림은 섬을 모두 연결하는 올바른 2가지 방법이고, 다리는 회색으로 색칠되어 있다. 섬은 정수, 다리는 알파벳 대문자로 구분했다.
| 다리의 총 길이: 13 D는 2와 4를 연결하는 다리이고, 3과는 연결되어 있지 않다. |
다리의 총 길이: 9 (최소) |
다음은 올바르지 않은 3가지 방법이다
| C의 방향이 중간에 바뀌었다 | D의 길이가 1이다. | 가로 다리인 A가 1과 가로로 연결되어 있지 않다. |
다리가 교차하는 경우가 있을 수도 있다. 교차하는 다리의 길이를 계산할 때는 각 칸이 각 다리의 길이에 모두 포함되어야 한다. 아래는 다리가 교차하는 경우와 기타 다른 경우에 대한 2가지 예시이다.
| A의 길이는 4이고, B의 길이도 4이다. 총 다리의 총 길이: 4 + 4 + 2 = 10 |
다리 A: 2와 3을 연결 (길이 2) 다리 B: 3과 4를 연결 (길이 3) 다리 C: 2와 5를 연결 (길이 5) 다리 D: 1과 2를 연결 (길이 2) 총 길이: 12 |
나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자.
입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.
출력
모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든 섬을 연결하는 것이 불가능하면 -1을 출력한다.
제한
- 1 ≤ N, M ≤ 10
- 3 ≤ N×M ≤ 100
- 2 ≤ 섬의 개수 ≤ 6
예제 입력 1 복사
7 8
0 0 0 0 0 0 1 1
1 1 0 0 0 0 1 1
1 1 0 0 0 0 0 0
1 1 0 0 0 1 1 0
0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1
예제 출력 1 복사
9
예제 입력 2 복사
7 8
0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 0
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1
예제 출력 2 복사
10
예제 입력 3 복사
7 8
1 0 0 1 1 1 0 0
0 0 1 0 0 0 1 1
0 0 1 0 0 0 1 1
0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0
1 1 1 1 1 1 0 0
예제 출력 3 복사
9
예제 입력 4 복사
7 7
1 1 1 0 1 1 1
1 1 1 0 1 1 1
1 1 1 0 1 1 1
0 0 0 0 0 0 0
1 1 1 0 1 1 1
1 1 1 0 1 1 1
1 1 1 0 1 1 1
예제 출력 4 복사
-1
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
struct info{
int to, from, weight;
};
int Map[10][10];
bool visited[10][10];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int parent[11];
int N, M;
int cnt = 1;
vector <info> graph;
vector<int> island[];
bool check[8];
bool cmp(info a,info b) {
return a.weight < b.weight;
}
int F_parent(int x) {
if (x == parent[x])
return x;
else
return parent[x] = F_parent(parent[x]);
}
void U_parent(int x, int y) {
x = F_parent(x);
y = F_parent(y);
if (x != y)
parent[y] = x;
}
void mark(int y, int x) {
queue<pair<int, int>> q;
q.push({ y,x });
Map[y][x] = cnt;
visited[y][x] = true;
while (!q.empty()) {
int a = q.front().first;
int b = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int ny = a + dy[i];
int nx = b + dx[i];
if (ny<0 || nx <0 || ny>N - 1 || nx>M - 1) continue;
if (Map[ny][nx] == 0)continue;
if (Map[ny][nx] == 1 && visited[ny][nx]==false) {
visited[ny][nx] = true;
Map[ny][nx] = cnt;
q.push({ ny,nx });
}
}
}
}
void dist(int y, int x, int mark) {
for (int i = 0; i < 4; i++) {//방향
int ny=y, nx=x;
int weight = 0;//직선이 되기전에 weight는 초기화 되는데?
while (1) {//직선
ny += dy[i];
nx += dx[i];
weight++;
if (ny<0 || nx <0 || ny>N - 1 || nx> M - 1) break;
if (Map[ny][nx] == mark)break;
if (Map[ny][nx] != mark && Map[ny][nx] != 0) {
if (weight > 2) {
graph.push_back({ mark, Map[ny][nx],weight-1 });
break;
}
break;
}
}
}
}
void check_cycle(int cur) {
check[cur] = true;
for (int i = 0; i < island[cur].size(); i++) {
if (check[island[cur][i]] == false) {
check[island[cur][i]] = true;
check_cycle(island[cur][i]);
}
}
}
int main() {
cin >> N >> M;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
cin >> Map[i][j];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (Map[i][j] == 1&& visited[i][j] == false) {
mark(i, j);//bfs
cnt++;
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (Map[i][j] >0) {
dist(i, j, Map[i][j]);
}
}
}
for (int i = 0; i < 11; i++)
parent[i] = i;
/*cout << endl;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cout << Map[i][j] << ' ';
}cout << endl;
}*/
sort(graph.begin(), graph.end(), cmp);
/*for (int i = 1; i < graph.size(); i++) {
cout << graph[i].to << ' ' << graph[i].from<< ' ' << graph[i]. weight<< endl;
}*/
int answer = 0;
for (int i = 1; i < graph.size(); i++) {
if (F_parent(graph[i].from) != F_parent(graph[i].to)) {
U_parent(graph[i].from,graph[i].to);
island[graph[i].from].push_back(graph[i].to);
island[graph[i].to].push_back(graph[i].from);
answer += graph[i].weight;
//cout << graph[i].weight;
}
}
check_cycle(1);
bool flag = false;
for (int i = 1; i < cnt; i++) {
if (check[i] == false) {
flag = true;
break;
}
}
if (flag == false) {
if (answer)
cout << answer;
else {
cout << -1;
}
}
else
cout << -1;
return 0;
}일단 섬을 숫자로 분류해서 연결하고 연결된 섬을 다시 크루스칼알고리즘으로 스패닝트리로만든다.
그리고 전체 섬을 모두 연결하는지 여부를 따져보고 다연결된다면 연결된 간선의 가중치를 출력하고 아니라면-1을 출력하면 된다.