알고리즘/BOJ
17472. 다리 만들기 2
병인
2019. 10. 16. 20:04
https://www.acmicpc.net/problem/17472
17472번: 다리 만들기 2
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.
www.acmicpc.net
마지막에 최소 스패닝 트리에 모든 섬이 포함되었는지 확인하는걸 빼먹어서 오답이 많이 났었다.
<JAVA>
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
class pos {
pos(int x, int y) {
this.x = x;
this.y = y;
}
int x, y;
}
class bridge implements Comparable<bridge> {
int from, to, count;
bridge(int from, int to, int count) {
this.from = from;
this.to = to;
this.count = count;
}
@Override
public int compareTo(bridge o) {
return Integer.compare(count, o.count);
}
};
class Main {
static final int dx[] = { 1, -1, 0, 0 };
static final int dy[] = { 0, 0, 1, -1 };
static int N, M;
static int map[][] = new int[10][10];
static boolean visit[][] = new boolean[10][10];
static int relation[] = new int[10];
static int unionCnt = 0;
static int islandCnt = 0;
static int result = 0;
static List<bridge> list = new ArrayList<>();
static int find(int n) {
if (relation[n] == n)
return n;
else
return relation[n] = find(relation[n]);
}
static void _union(int x, int y, int idx) {
x -= 2;
y -= 2;
x = find(x);
y = find(y);
if (x == y)
return;
relation[x] = y;
++unionCnt;
result += list.get(idx).count;
}
static void input() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
for (int i = 0; i < N; ++i) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < M; ++j) {
map[i][j] = Integer.parseInt(st.nextToken(" "));
}
}
}
static void islandSetting() {
for (int i = 0; i < 10; ++i) {
relation[i] = i;
}
int index = 2;
Queue<pos> q = new LinkedList<>();
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
if (!visit[i][j] && map[i][j] == 1) {
visit[i][j] = true;
map[i][j] = index;
q.add(new pos(i, j));
while (!q.isEmpty()) {
pos cur = q.poll();
for (int dir = 0; dir < 4; ++dir) {
int nx = cur.x + dx[dir];
int ny = cur.y + dy[dir];
if (nx < 0 || ny < 0 || nx >= N || ny >= M || visit[nx][ny] || map[nx][ny] != 1) {
continue;
}
q.add(new pos(nx, ny));
map[nx][ny] = index;
visit[nx][ny] = true;
}
}
++index; // 섬의 번호 증가
}
}
}
islandCnt = index - 2;
}
static void searchBridge() {
int index = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
if (map[i][j] != 0) {
index = map[i][j];
for (int dir = 0; dir < 4; ++dir) {
int nx = i;
int ny = j;
int cnt = 0;
while (true) {
nx += dx[dir];
ny += dy[dir];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) {
break;
}
if (map[nx][ny] != 0) {
if (map[nx][ny] != index && cnt > 1) {
list.add(new bridge(index, map[nx][ny], cnt));
}
break;
}
++cnt;
}
}
}
}
}
}
static void makeBridge() {
Collections.sort(list);
for (int i = 0; i < list.size(); ++i) {
_union(list.get(i).from, list.get(i).to, i);
if (islandCnt == unionCnt)
break;
}
}
public static void main(String[] args) throws Exception {
unionCnt = 0;
result = 0;
input();
islandSetting();
searchBridge();
makeBridge();
// 최소 스패닝 트리에 모든 섬이 포함되었는지 확인
int f = find(0);
for (int i = 1; i < islandCnt; i++) {
if (f != find(i)) {
result = 0;
}
}
if (result == 0)
System.out.println("-1");
else
System.out.println(result);
}
}<C++>
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
struct pos
{
int x, y;
};
struct bridge
{
int from, to, count;
bool operator < (bridge b)
{
return count < b.count;
}
};
const int dx[] = { 1, -1, 0, 0 };
const int dy[] = { 0, 0, 1, -1 };
int N, M;
int map[10][10];
bool visit[10][10];
int relation[10];
int unionCnt = 0;
int islandCnt = 0;
int result = 0;
vector<bridge> v;
int find(int n) {
if (relation[n] == n)
return n;
else
return relation[n] = find(relation[n]);
}
void _union(int x, int y, int idx) {
x -= 2;
y -= 2;
x = find(x);
y = find(y);
if (x == y)
return;
relation[x] = y;
++unionCnt;
result += v[idx].count;
}
void input()
{
cin >> N >> M;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < M; ++j)
{
cin >> map[i][j];
}
}
}
void islandSetting()
{
for (int i = 0; i < 10; ++i)
{
relation[i] = i;
}
int index = 2;
memset(visit, false, sizeof(visit));
queue<pos> q;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < M; ++j)
{
if (!visit[i][j] && map[i][j] == 1)
{
visit[i][j] = true;
map[i][j] = index;
q.push({ i,j });
while (!q.empty())
{
pos cur = q.front(); q.pop();
for (int dir = 0; dir < 4; ++dir)
{
int nx = cur.x + dx[dir];
int ny = cur.y + dy[dir];
if (nx < 0 || ny < 0 || nx >= N || ny >= M || visit[nx][ny] || map[nx][ny] != 1)
{
continue;
}
q.push({ nx,ny });
map[nx][ny] = index;
visit[nx][ny] = true;
}
}
++index; //섬의 번호 증가
}
}
}
islandCnt = index - 2;
}
void searchBridge()
{
int index = 0;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < M; ++j)
{
if (map[i][j] != 0)
{
index = map[i][j];
for (int dir = 0; dir < 4; ++dir)
{
int nx = i;
int ny = j;
int cnt = 0;
while (true)
{
nx += dx[dir];
ny += dy[dir];
if (nx < 0 || ny < 0 || nx >= N || ny >= M)
{
break;
}
if (map[nx][ny] != 0)
{
if (map[nx][ny] != index && cnt > 1)
{
v.push_back({ index,map[nx][ny],cnt });
}
break;
}
++cnt;
}
}
}
}
}
}
void makeBridge()
{
sort(v.begin(), v.end());
for (int i = 0; i < v.size(); ++i)
{
_union(v[i].from, v[i].to, i);
if (islandCnt == unionCnt)
break;
}
}
int main()
{
cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
unionCnt = 0;
result = 0;
input();
islandSetting();
searchBridge();
makeBridge();
// 최소 스패닝 트리에 모든 섬이 포함되었는지 확인
int f = find(0);
for (int i = 1; i < islandCnt; i++)
{
if (f != find(i))
{
result = 0;
}
}
if (result == 0)
cout << -1;
else
cout << result;
return 0;
}