[BOJ - 17472] 다리 만들기2

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

17472번: 다리 만들기 2

 

 

이번 9월 삼성 A형 역량테스트 복기된 문제로 난이도는 이제껏 풀었던 A형 문제중 어려운 문제에 속한것 같다.

 

지난번 게리맨더링 문제도 난이도가 꽤 높았고 이번 문제도 꽤 높은걸 보니

 

이제는 출제자 측에서도 지원자들이 상향평준화 되었다는걸 알아서 올해 하반기 지원자들의 수준을 테스트해보기 위해 삼성 역량테스트 전에 문제의 난이도를 조금 올린듯 하다.

 

이번 문제를 풀 때는 BFS와 크루스칼 알고리즘을 사용했다.

 

- 풀이 방법

1. 입력을 받는다.

 

2. BFS로 떨어진 섬들에게 번호를 부여한다.

(번호를 부여하면서 섬의 좌표들을 vector 배열에 수집한다.) -> 섬의 갯수가 최대 6개이기 때문에 시간 초과 안남

 

3. vector배열에 수집된 좌표들을 이용해 섬에서 섬까지의 최단 경로를 구한다(직선으로)

- 저는 재귀로 구했습니다.

- dist라는 이차원 배열에 저장했는데 dist[i][j]는 i섬에서 j섬까지의 최단 거리 입니다.

 

4. 최소 스패닝 트리를 만들어준다.

- 크루스칼 알고리즘을 사용합니다.

- union-find를 알아야 하기 때문에 모르신다면 구글 검색을 추천...

 

5. 모든 섬들이 연결이 되어있는지 find_parent함수를 이용해 확인합니다.

 

6. 답을 출력합니다.

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

struct POINT {
	int y, x;
};
struct DIST {
	int from, to, dist;
};
int n, m, ans;
int map[11][11];
int map_number[11][11];
int visited[11][11];
int dist[7][7];
int parent[7];
vector<POINT> area[7];
vector<DIST> line;
const int dy[] = { -1,1,0,0 };
const int dx[] = { 0,0,-1,1 };

bool cmp(DIST a, DIST b) {
	return a.dist < b.dist;
}

int find_parent(int a) {
	if (parent[a] == a) return a;
	else return parent[a] = find_parent(parent[a]);
}

void parent_union(int a, int b) {
	int aRoot = find_parent(a);
	int bRoot = find_parent(b);
	parent[aRoot] = bRoot;
}

void find_dist(int start, int u, int v, int dir, int val, int dist_cnt) {

	int ny = u + dy[dir];
	int nx = v + dx[dir];

	if (ny < 0 || ny >= n || nx < 0 || nx >= m) return;
	if (map_number[ny][nx] == 0) {
		find_dist(start, ny, nx, dir, val, dist_cnt + 1);
	}
	else if (map_number[ny][nx] != val && dist_cnt >= 2) {
		dist[start][map_number[ny][nx]] = min(dist[start][map_number[ny][nx]], dist_cnt);
		return;
	}
	else return;
}

int main(void) {

	scanf("%d %d", &n, &m);

	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			scanf("%d", &map[y][x]);
		}
	}

	int cnt = 0;
	//섬에 넘버링 해줌
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			if (map[y][x] != 0 && visited[y][x] == 0) {
				cnt += 1;

				queue<POINT> q;
				q.push({ y,x });
				visited[y][x] = 1;
				map_number[y][x] = cnt;
				area[cnt].push_back({ y,x });

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

					for (int dir = 0; dir < 4; dir++) {
						POINT next;
						next.y = cur.y + dy[dir];
						next.x = cur.x + dx[dir];

						if (next.y < 0 || next.y >= n || next.x < 0 || next.x >= m || visited[next.y][next.x]) continue;
						if (map[next.y][next.x] == 0 || map[next.y][next.x] != map[cur.y][cur.x]) continue;

						visited[next.y][next.x] = 1;
						map_number[next.y][next.x] = cnt;
						area[cnt].push_back(next);
						q.push(next);
					}
				}
			}
		}
	}

	for (int y = 0; y < 7; y++) {
		for (int x = 0; x < 7; x++) {
			dist[y][x] = 0x7fffffff;
		}
	}

	//섬에서 섬까지 연결될 수 있는 모든 경로 찾기
	for (int i = 1; i <= cnt; i++) {
		for (int j = 0; j < area[i].size(); j++) {
			int y = area[i][j].y;
			int x = area[i][j].x;

			for (int dir = 0; dir < 4; dir++) {
				find_dist(i, y, x, dir, map_number[y][x], 0);
			}
		}
	}

	//간선의 정보를 모음
	for (int i = 1; i <= cnt; i++) {
		for (int j = 1; j <= cnt; j++) {
			if (dist[i][j] != 0x7fffffff) {
				line.push_back({ i,j,dist[i][j] });
			}
		}
	}
	//간선 작은 순으로 정렬
	sort(line.begin(), line.end(), cmp);

	//부모 초기화
	for (int i = 1; i <= cnt; i++) parent[i] = i;

	//최소 스패닝 트리를 만들어줌
	for (int i = 0; i < line.size(); i++) {
		int from = line[i].from;
		int to = line[i].to;

		int pfrom = find_parent(from);
		int pto = find_parent(to);

		if (pfrom != pto) {
			parent_union(pfrom, pto);
			ans += line[i].dist;
		}
	}
	//연결되었는지 검사
	int temp1 = find_parent(1);
	for (int i = 2; i <= cnt; i++) {
		int temp2 = find_parent(i);
		if (temp1 != temp2) {
			ans = -1;
			break;
		}
	}

	if (ans == 0) ans = -1;
	printf("%d\n", ans);

	getchar();
	getchar();

	return 0;
}