[BOJ]백준 17472번: [삼성 A형 기출문제] 다리 만들기2 (풀이 및 반례)

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

17472번: 다리 만들기 2

 

다리를 놓아 모든 섬을 연결할 수 있을 때, 다리 길이의 합의 최솟값을 찾는 문제이다.

다리는

1️⃣ 섬끼리 인접한 바다에서만 직선으로 설치할 수 있다

2️⃣ 중간에 방향전환을 할 수 없다

3️⃣ 길이는 2 이상이다

라는 조건을 가지고 있다

 

알고리즘 노트 中

위의 그림에서, 초록색으로 칠해진 부분이 다리를 설치할 수 있는 부분이다.

그래서 각각의 구역에서 BFS를 돌려 섬 번호를 나누고, 

섬 지역에서 특정 방향의 다음 칸을 검사했을 때 바다 영역이라면 다리 설치 가능 큐에 push해줬다

 

하지만 노란색 칠해진 부분을 보면

목적지가 맵을 벗어나는 부분과 한 다리를 놨을 때 중복으로 체크되는 서로 다른 섬의 영역은 체크해줄 필요가 없다

그런 부분을 검사해서 최종 다리 후보를 벡터에 저장한다

그 이후 백트래킹을 통해 시뮬레이션을 돌려 BFS로 전체 섬을 순회 가능하면서 다리 길이가 최솟값인 case를 찾는다

 

(원래 코드가 2000자 넘어가게 짜는걸 극도로 싫어하는데, 이 문제는 넘을 수 밖에 없었다😢

시간이 갈 수록 문제가 더 어려워진다 😵

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <math.h>
using namespace std;
int n, m, land, map[11][11], dr[] = { 1,0,-1,0 }, dc[] = { 0,1,0,-1 };
typedef struct {
	int r, c;
}point;
typedef struct {
	point p;
	int dir, len, des;
}bridge;
vector<bridge> v;
queue<bridge> ib;
queue<point> q;
bool visit[11][11], check[100];
int cg[7][7], cv[7], ans = 100000;
bool safe(int r, int c) {
	return r >= 0 && r < n && c >= 0 && c < m;
}
void erase_bridge() {
	bool b[4][11][11]; memset(b, false, sizeof(b));
	while (!ib.empty()) {
		point p = ib.front().p;
		point w = p;
		int dir = ib.front().dir, len = 0;
		p.r += dr[dir]; p.c += dc[dir];
		if (b[dir][w.r][w.c]) {
			ib.pop(); continue;
		}
		b[dir][w.r][w.c] = 1;

		while (1) {
			if (!safe(p.r, p.c)) {	//맵을 벗어날 경우
				break;
			}
			if (map[p.r][p.c] != 0) {	//섬에 닿으면
				len = abs(ib.front().p.r - p.r) + abs(ib.front().p.c - p.c) - 1;
				if (len < 2)break;
				v.push_back({ w,dir,len,map[p.r][p.c] });
				b[(dir + 2) % 4][p.r][p.c] = 1;
				break;
			}
			p.r += dr[dir]; p.c += dc[dir];
		}
		ib.pop();
	}
}
void bfs(point p) {
	q.push(p);
	visit[p.r][p.c] = 1;
	map[p.r][p.c] = land;

	while (!q.empty()) {
		point cur = q.front(); q.pop();

		for (int i = 0, nr, nc; i < 4; i++) {
			nr = cur.r + dr[i], nc = cur.c + dc[i];
			if (safe(nr, nc) && map[nr][nc] && !visit[nr][nc]) {
				q.push({ nr,nc });
				visit[nr][nc] = 1;
				map[nr][nc] = land;
			}
			else if (safe(nr, nc) && !map[nr][nc]) {
				//다리 후보 삽입
				ib.push({ cur,i,0 });
			}
		}
	}
}
void dfs(int cur) {
	cv[cur] = true;
	for (int next = 1; next <= land; next++)
		if (!cv[next] && cg[cur][next])
			dfs(next);
}
void func(int dep) {
	if (dep == v.size()) {
		memset(cg, false, sizeof(cg));
		memset(cv, false, sizeof(cv));
		int sum = 0;
		for (int i = 0; i < v.size(); i++) {
			if (!check[i])continue;
			int cur = map[v[i].p.r][v[i].p.c];
			int next = v[i].des;
			cg[cur][next] = cg[next][cur] = 1;
			sum += v[i].len;
		}
		dfs(1);

		for (int i = 1; i <= land; i++)
			if (!cv[i])return;
		if (sum < ans)ans = sum;
		return;
	}

	check[dep] = true;
	func(dep + 1);
	check[dep] = false;
	func(dep + 1);
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			scanf("%d", &map[i][j]);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			if (map[i][j] && !visit[i][j]) {
				land++;
				bfs({ i,j });
			}
		}
	erase_bridge();
	func(0);
	printf("%d", ans == 100000 ? -1 : ans);
	return 0;
}

 

 

👇 반례 모음!!

10 8
0 0 1 1 1 1 1 0
1 1 1 1 1 1 0 1
0 0 0 1 0 1 0 0
1 1 0 1 1 0 1 1
0 0 1 1 0 1 1 0
0 1 0 0 0 0 0 0
1 1 1 1 0 0 1 0
1 0 0 1 1 1 0 0
1 1 0 0 0 1 1 1
1 1 1 0 0 1 0 1

ans: -1

 

4 10
0 0 1 0 0 0 0 1 0 1
0 0 0 0 0 0 1 0 0 1
0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 1 0 0 0 0

ans: -1

 

3 10
1 1 0 0 0 0 0 0 1 1
1 0 0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 0 1 1

ans: -1

 

9 5
0 1 1 1 1
1 0 0 1 0
0 0 0 1 0
1 1 0 0 1
1 1 0 1 1
1 0 0 0 1
1 0 1 1 0
0 0 1 0 0
0 0 0 0 0

ans: 11

 

8 8
0 0 0 0 0 1 0 1
0 1 0 1 0 1 1 0
1 1 1 1 1 1 0 0
0 0 1 0 0 1 0 0
1 1 0 0 0 1 1 0
0 0 0 1 1 1 1 1
0 1 1 0 0 1 1 0
0 0 1 0 1 0 0 1

ans: -1

 

10 5
0 1 0 0 0
1 1 1 0 0
1 0 1 1 1
0 1 1 1 0
1 0 0 0 1
1 1 1 0 1
0 0 0 0 1
0 0 0 1 0
0 0 0 1 1
0 0 0 0 0

ans: -1

 

9 3
0 1 1
0 0 1
1 0 0
1 0 0
0 1 0
0 0 1
1 0 0
0 1 0
0 1 0

ans: -1

 

10 6
0 0 0 1 0 0
0 0 0 1 0 0
0 1 0 0 0 1
0 0 0 0 0 0
1 1 0 1 1 0
1 0 0 0 1 0
1 1 0 0 1 0
0 0 0 0 1 1
0 0 0 0 0 0
0 1 0 0 0 0

ans: 13

 

4 9
0 0 1 1 1 0 0 1 0
1 0 0 1 0 0 0 1 0
0 0 1 0 0 1 0 1 0
1 0 0 0 0 0 0 1 0

ans: -1

 

10 10
1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 1 0 1 0 1 0 1 0

ans: 40

 

10 10
0 0 0 1 1 0 0 0 0 0
0 0 0 1 0 0 0 0 0 1
0 0 0 1 1 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0
1 0 0 1 0 0 0 0 0 1
0 0 0 1 1 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1
0 0 1 1 1 1 0 0 1 1

ans: 11