코딩테스트
[백준 17472] 다리만들기 2 와 mst에 대한 설명
코앤미
2021. 12. 19. 13:01
이 문제가 삼성 코테에 기출 되어서 풀어봤는데, 여러가지 알고리즘이 한 문제에 누적 되어 있어, 풀어보면
좋을 것 같아 자잘한 설명과 함께 코드를 공유하려합니다! 코드에 대한 설명은 주석으로 상세하게 적어놨습니다~
문제를 처음보면, 딱 "그룹" 이라는 단어가 떠오르면서 자연스럽게 mst(최소 스패닝 트리) 에 관한 문제인 것을 캐치하고
풀어 나갔다.
MST에 대해 잘 모른다면, 아래의 글을 참고하자.
https://codenme.tistory.com/manage/posts/
Tistory
좀 아는 블로거들의 유용한 이야기
www.tistory.com
문제는 크게 3파트로 나눌 수 있는데
1) 각 섬에 번호를 붙여 저장하기 (섬간의 구분을 위해)
이건 bfs를 통해 구현했다..
2)섬간의 거리를 구한다.
이것 역시 bfs 를 통해, 각섬의 모든 요소들에서 도착 섬까지의 최단 거리를 구하고, 그중 가장 짧은 거리를 최단거리로 저장했다.
3)위의 1,2 단계는 각각 정점(섬), 가중치(섬간의 거리)를 구한 것이다. 이 정보를 통해, MST(최소 스패닝 트리) 를 만들어주면
최소 비용으로 모든 섬을 연결할 수 있다. 크루스칼(비용이 최소인 간선부터 mst에 추가해나가며 완성하는 알고리즘) 알고리즘을 통해서 mst를 구했다!
#include<iostream>
#include<queue>
#include<vector>
#include<math.h>
using namespace std;
int ma[101][101];
int visit[101][101];
int xe[4] = { 1,0,-1,0 };
int ye[4] = { 0,1,0,-1 };
int n, m;
vector<pair<int, int>> vec[101];
const int inf = 987654321;
int parent[101];
int find(int v) {//disjoint set find
if (v == parent[v]) {
return v;
}
else
return parent[v] = find(parent[v]);
}
void join(int a, int b) {//distjoint set union
a = find(a);
b = find(b);
parent[a] = b;
}
//u번 섬에서 v번 섬으로 가는 직선 최단 거리를 구한다.
int distance(int u, int v) {
queue < pair<int, int>> q;
//u번 섬에 있는 칸들을 모두 큐에 넣는다.
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (visit[i][j] == u) {
q.push({ i, j });
}
}
}
int mindist = inf;
int x, y;
while (!q.empty()) {
x = q.front().first;
y = q.front().second;
q.pop();
for (int k = 0; k < 4; k++) {
int nx = x + xe[k];
int ny = y + ye[k];
int dist = 0;
//한방향으로 계속 이동
while (true) {
//맵 밖 범위를 넘어간 경우
if (ma[nx][ny]==-1) break;
//같은 섬일시 생략.
if (visit[nx][ny] == u) break;
if (visit[nx][ny] == v) {
//도착섬에 도착, 탐색 종료.
if (dist > 1 && mindist > dist) mindist = dist;
break;
}
else if (visit[nx][ny] == 0) {
//바다인 경우 거리증가하고 이동
// 이로인하여, 내륙에서 시작하는 점들을 거를 수 있다.
dist++;
nx += xe[k];
ny += ye[k];
}
else {
//다른 섬인 경우 더 탐색하지 않는다.
break;
}
}
}
}
//최소거리가 초기값이 아니라면 벡터에 최소거리와 섬의 번호를 넣는다.
return mindist;
}
void bfs(int i, int j, int num) {//i,j에서 시작된 섬에 num의 번호를 붙여 visit에 저장하는 함수.
visit[i][j] = num;
vec[num].push_back({ i,j });
queue<pair<int, int>> qu;
qu.push({ i,j });
while (!qu.empty()) {
int n_i = qu.front().first;
int n_j = qu.front().second;
qu.pop();
for (int k = 0; k < 4; k++) {
int nxt_i = n_i + xe[k];
int nxt_j = n_j + ye[k];
if (ma[nxt_i][nxt_j] == 1 && !visit[nxt_i][nxt_j]) {//다음위치(붙어있는 위치)가 땅이고,
visit[nxt_i][nxt_j] = num; //방문하지 않았다면, 같은섬으로 표기해줘야한다.
vec[num].push_back({ nxt_i,nxt_j });
qu.push({ nxt_i,nxt_j });
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i <= n + 1; i++) {
for (int j = 0; j <= m + 1; j++) {// 맵을 저장한 ma 함수의 기본 값을 -1로 설정.
ma[i][j] = -1;
}
}
for (int i = 1; i <= n; i++) { //입력을 받을때 x,y좌표(혹은 배열 인덱스) 를 한칸씩 +1해준다.
for (int j = 1; j <= m; j++) {
cin >> ma[i][j];
}
}
// -1 -1 -1 -1 위의 두 이중포문으로 배열내부는 이런식으로 생성될 것이다.
// -1 0 1 0 ma[i][j] == -1 이라면, 맵밖으로 나간것으로 쉽게 알 수 있다.
// -1 0 1 1
// -1 0 0 0
int cnt = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (!visit[i][j] && ma[i][j] == 1)//visit에 각섬을 번호로 표시.
bfs(i, j, cnt++);
}
}
for (int i = 1; i <= cnt; i++) {
parent[i] = i;
}
priority_queue<pair<int, pair<int, int>>> pq;
//아래의 2중포문은 "1~cnt 섬 까지의 섬들중 임의의 2섬을 각각 i,j에 담는다! (확통 때 배우는 "조합" 혹은 "콤비네이션" 과 유사
for (int i = 1; i <= cnt; i++) {//임의 의 두 섬 콤비네이션으로 뽑기. 첫째
for (int j = i + 1; j <= cnt; j++) {//둘째.
int res = distance(i, j);//i>j로 가는 최단거리를 찾아준다.
if (res != inf) {
pq.push({ -res, { i,j } });// priority queue는 큰수가 top으로 온다,
//따라서 최단거리가 top에 오게 하기 위하여, 거리에 - 를 붙인뒤, 마지막에 *-1 해주자.
}
}
}
int ans = 0;
int t = 0;
while (!pq.empty()) {
auto now = pq.top();//가장 적은 가중치의 간선이 먼저 나온다.
pq.pop();
if (find(now.second.first) != find(now.second.second)) {//같은 그룹이 아니라면
join(now.second.first, now.second.second);//mst에 합쳐준다.
t++;//합쳐진 횟수 저장.
ans += now.first;//해당 간선의 가중치 누적
}
}
ans *= (-1);
//cnt에 현재 들어있는 값은 섬의 개수 +1다. t는 간선의 개수를 저장해줌.
//mst의 간선개수 = 정점-1개 여야한다. 따라서 (cnt-1)=정점개수 에 -1 을 해서 cnt-2.
if (t==cnt-2)
cout << ans;
else//mst 완성실패.
cout << -1;
}
+
풀고 나서 아쉬웠던 부분이 있었는데, 섬간의 거리를 구할때, 섬의 각점마다 bfs를 돌게 짠 부분이 조금 별로였다...
시간초과는 나지 않았지만, 아래의 그림처럼 각 섬의 테두리부터 시작해 bfs를 통해 섬을 확장시켜 나가면서 가장 먼저 서로 만나는 섬들의 거리를 더해 각 섬들간의 최단거리를 찾았다면, 좀더 좋았을 것 같다!
