티스토리 뷰
1. 문제 링크
https://www.acmicpc.net/problem/17472
17472번: 다리 만들기 2
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.
www.acmicpc.net
2. 문제 개요
조건에 맞게 다리를 놓아서 각 섬을 모두 연결하는 다리의 최소 길이를 구하기.
3. 문제 힌트
알고리즘
(1) Grouping 하기.
(2) 다리 연결 -> 길이가 2 이상이고 조건(가로/세로)에 맞는 다리 중에서 길이가 최소 다리 구하기.
(3) 다리 정하기 -> 섬들이 모두 연결되는지 확인하기.
(4) 계산하기
의 순서대로 하면 된다.
4. 문제 풀기
(1) Grouping -> BFS로 구현함. 아마도 이 문제 풀 정도 되는 분들이면 간단히 할 수 있을 것이라 생각. 함수로 만들었다.
(2) 다리 연결
섬 간의 거리를 나타낼 dist [][] 배열을 만들고, INF로 초기화한다.(INF는 적당히 큰 수)
그리고 각 방향으로 뻗어나가 본다. 왜냐하면 다리는 일직선이 되어야 하기 때문. 뻗어나갈 때 섬의 모든 부분에서 뻗어나가 본다. 다음칸에 다리를 놓는데, 바다가 아니면 넘어가는 방식으로 구현한다.
이렇게 검은 점에서 탐색을 한다고 가정했을 때, 가는 곳이 맵 안쪽의 바다여야 하고, 상대방 섬(다른 그룹번호)에 닿을 때까지 탐색한다. 전수조사.
그래서 섬 x에서 섬 y에 가는 길이가 2가 넘는 다리의 길이를 구한다.
과 같이 다리를 놓을 수 있다. 그러면
[ INF, 4 , INF, 4 ]
[ 4 , INF, 3 , 2 ]
[ INF, 3 , INF , INF ]
[ 4 ,2 , INF , INF]
이런 행렬을 구할 수 있다.
MST( Minimun Spanning Tree )의 특성상 N개의 Vertex가 있다면 Edge의 개수는 항상 N-1개이다.
그래서 DFS를 사용하여 위의 다리 중 N-1개를 선택하고(조합) 값을 비교하여 최솟값을 구하는 방식이다.
그리고 그 다리를 선택했을 때, 모든 섬이 하나의 그룹인지 확인하는 부분이 필요한데,
밑의 코드에서는 BFS로 검사했다. 백준 질문란에 Union find 알고리즘을 사용해도 된다라고 하는데, 포스팅 후 적용시켜볼 예정이다.
BFS-> 위에서 구한 행렬을 토대로 인접 리스트(adjacency list)를 만들고 정점 아무거나 큐에 삽입하여 탐색 시작. 한 정점이라도 방문하지 않았다면 Return.
※Kruskal Algorithm을 적용시켜 구현해보았다.
거리를 나타내는 Dist행렬까지 만들고 Disjoint set 구조체 ( union, find함수 정의)를 만든다.
거리 즉, 연결관계를 나타내는 행렬을 토대로 Kruskal Algorithm을 구현.
우선순위 큐 사용.
그럼 답이 결정적으로 1개가 나오게 된다. DFS + BFS처럼 값을 비교 안 해도 됨.
5. 코드
(1) DFS + BFS를통한 전수조사.
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#define INF 0x7f7f7f7f
using namespace std;
int map[10][10];
int group[10][10];
int dist[7][7]; // use index 1~6
bool selected[7][7] = { false, };
int n, m;
const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,1,-1 };
int g_index = 1;
int ret = INF;
void grouping()
{
bool g_visited[10][10] = { false, };
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
{
if (map[i][j] == 1 && !g_visited[i][j])
{
queue<int> q;
g_visited[i][j] = true;
q.push(i * 10 + j); //it is okay to use pair or structure.
while (!q.empty())
{
int cur = q.front(); q.pop();
int cx = cur % 10;
int cy = cur / 10;
group[cy][cx] = g_index;
for (int dir = 0; dir < 4; ++dir)
{
int nx = cx + dx[dir];
int ny = cy + dy[dir];
if (nx < 0 || ny < 0 || nx >= m || ny >= n || map[ny][nx] == 0 || g_visited[ny][nx])
continue;
g_visited[ny][nx] = true;
q.push(ny * 10 + nx);
}
}
g_index++;
}
}
return;
}
void getdistance()
{
//in the group
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
{
if (group[i][j] != 0)
{
//north
int cx = j;
int cy = i - 1;
int tdist = 0;
while (cy >= 0)
{
if (group[cy][cx] == group[i][j]) break;
if (group[cy][cx] != 0 && group[cy][cx] != group[i][j])
{
if (tdist < 2) break;
dist[group[i][j]][group[cy][cx]] = min(dist[group[i][j]][group[cy][cx]], tdist);
break;
}
cy--;
tdist++;
}
//east
cx = j + 1;
cy = i;
tdist = 0;
while (cx <= m - 1)
{
if (group[cy][cx] == group[i][j]) break;
if (group[cy][cx] != 0 && group[cy][cx] != group[i][j])
{
if (tdist < 2) break;
dist[group[i][j]][group[cy][cx]] = min(dist[group[i][j]][group[cy][cx]], tdist);
break;
}
cx++;
tdist++;
}
//south
cx = j;
cy = i + 1;
tdist = 0;
while (cy <= n - 1)
{
if (group[cy][cx] == group[i][j]) break;
if (group[cy][cx] != 0 && group[cy][cx] != group[i][j])
{
if (tdist < 2) break;
dist[group[i][j]][group[cy][cx]] = min(dist[group[i][j]][group[cy][cx]], tdist);
break;
}
cy++;
tdist++;
}
//west
cx = j - 1;
cy = i;
tdist = 0;
while (cx >= 0)
{
if (group[cy][cx] == group[i][j]) break;
if (group[cy][cx] != 0 && group[cy][cx] != group[i][j])
{
if (tdist < 2) break;
dist[group[i][j]][group[cy][cx]] = min(dist[group[i][j]][group[cy][cx]], tdist);
break;
}
cx--;
tdist++;
}
}
}
return;
}
void dfs(int depth, int y, int x)
{
if (depth == g_index - 1)
{
bool check[7] = { false, };
//하나의 그룹인지 체크하는부분 필요
vector<vector<int>> v;
v.resize(g_index);
int startv;
for (int i = 1; i < g_index; ++i)
for (int j = 1; j < g_index; ++j)
{
if (selected[i][j] == true)
{
startv = i;
v[i].push_back(j);
v[j].push_back(j);
}
}
queue<int> q;
bool visited[7] = { false, };
q.push(startv);
visited[startv] = true;
while (!q.empty())
{
int cur = q.front(); q.pop();
int len = v[cur].size();
for (int i = 0; i < len; ++i)
{
int next = v[cur][i];
if (!visited[next])
{
visited[next] = true;
q.push(next);
}
}
}
for (int i = 1; i < g_index; ++i)
if (!visited[i]) return;
int sum = 0;
for (int i = 1; i < g_index; ++i)
for (int j = 1; j < g_index; ++j)
{
if (selected[i][j] == true)
{
sum += dist[i][j];
}
}
if (ret > sum)
ret = sum;
//ret = min(ret, sum);
return;
}
for (int i = y; i < g_index; ++i)
{
for (int j = x; j < g_index; ++j)
{
if (dist[i][j] != INF && dist[i][j] > 1)
{
selected[i][j] = true;
dfs(depth + 1, i, j + 1);
selected[i][j] = false;
}
}
x = 0;
}
}
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]);
grouping();
for (int i = 1; i < g_index; ++i)
for (int j = 1; j < g_index; ++j)
dist[i][j] = INF;
getdistance();
dfs(1, 1, 1);
if (ret == INF)
printf("-1");
else
printf("%d", ret);
return 0;
}(2) Kruskal Algorithm을 사용한 MST 구하기
#include <cstdio>
#include <queue>
#include <vector>
#include <functional>
#include <algorithm>
#define INF 0x7f7f7f7f
using namespace std;
int map[10][10];
int group[10][10];
int dist[7][7]; // use index 1~6
int n, m;
const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,1,-1 };
int g_index = 1;
int ret = 0;
struct AdjointSet {
vector<int> root;
vector<int> rank;
void init_AdjointSet(int g_size)
{
root.resize(g_size);
rank.resize(g_size);
for (int i = 1; i < g_size; ++i) {
root[i] = i;
rank[i] = 1;
}
}
int find(int x)
{
if (root[x] == x)
return x;
else
return root[x] = find(root[x]);
}
void union_set(int x, int y)
{
x = find(x);
y = find(y);
if (rank[x] < rank[y])
root[x] = y;
else
{
root[y] = x;
if (rank[x] == rank[y])
rank[x]++;
}
}
}AJS;
void grouping()
{
bool g_visited[10][10] = { false, };
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
{
if (map[i][j] == 1 && !g_visited[i][j])
{
queue<int> q;
g_visited[i][j] = true;
q.push(i * 10 + j); //it is okay to use pair or structure.
while (!q.empty())
{
int cur = q.front(); q.pop();
int cx = cur % 10;
int cy = cur / 10;
group[cy][cx] = g_index;
for (int dir = 0; dir < 4; ++dir)
{
int nx = cx + dx[dir];
int ny = cy + dy[dir];
if (nx < 0 || ny < 0 || nx >= m || ny >= n || map[ny][nx] == 0 || g_visited[ny][nx])
continue;
g_visited[ny][nx] = true;
q.push(ny * 10 + nx);
}
}
g_index++;
}
}
return;
}
void getdistance()
{
//in the group
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
{
if (group[i][j] != 0)
{
//north
int cx = j;
int cy = i - 1;
int tdist = 0;
while (cy >= 0)
{
if (group[cy][cx] == group[i][j]) break;
if (group[cy][cx] != 0 && group[cy][cx] != group[i][j])
{
if (tdist < 2) break;
dist[group[i][j]][group[cy][cx]] = min(dist[group[i][j]][group[cy][cx]], tdist);
break;
}
cy--;
tdist++;
}
//east
cx = j + 1;
cy = i;
tdist = 0;
while (cx <= m - 1)
{
if (group[cy][cx] == group[i][j]) break;
if (group[cy][cx] != 0 && group[cy][cx] != group[i][j])
{
if (tdist < 2) break;
dist[group[i][j]][group[cy][cx]] = min(dist[group[i][j]][group[cy][cx]], tdist);
break;
}
cx++;
tdist++;
}
//south
cx = j;
cy = i + 1;
tdist = 0;
while (cy <= n - 1)
{
if (group[cy][cx] == group[i][j]) break;
if (group[cy][cx] != 0 && group[cy][cx] != group[i][j])
{
if (tdist < 2) break;
dist[group[i][j]][group[cy][cx]] = min(dist[group[i][j]][group[cy][cx]], tdist);
break;
}
cy++;
tdist++;
}
//west
cx = j - 1;
cy = i;
tdist = 0;
while (cx >= 0)
{
if (group[cy][cx] == group[i][j]) break;
if (group[cy][cx] != 0 && group[cy][cx] != group[i][j])
{
if (tdist < 2) break;
dist[group[i][j]][group[cy][cx]] = min(dist[group[i][j]][group[cy][cx]], tdist);
break;
}
cx--;
tdist++;
}
}
}
return;
}
void kruskal()
{
AJS.init_AdjointSet(g_index);
//val, v -> u
priority_queue<pair<int, pair<int, int>>,vector<pair<int, pair<int, int>>>,greater<pair<int, pair<int, int>>>> pq;
for (int i = 1; i < g_index; ++i)
for (int j = i + 1; j < g_index; ++j)
{
if (dist[i][j] != INF)
pq.push(make_pair(dist[i][j], make_pair(i, j)));
}
while (!pq.empty())
{
int from, to, val;
val = pq.top().first;
from = pq.top().second.first;
to = pq.top().second.second;
pq.pop();
if (AJS.find(from) != AJS.find(to))
{
AJS.union_set(from, to);
ret += val;
}
}
bool complete = true;
for (int i = 2; i < g_index; ++i)
{
if (AJS.find(1) != AJS.find(i))
complete = false;
}
if (!complete)
printf("-1");
else
printf("%d", ret);
return;
}
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]);
grouping();
for (int i = 1; i < g_index; ++i)
for (int j = 1; j < g_index; ++j)
dist[i][j] = INF;
getdistance();
kruskal();
return 0;
}6. 결과 사진
지적, 댓글 언제나 환영입니다~
'알고리즘 > 삼성 SW테스트' 카테고리의 다른 글
| boj, 백준) 17822. 원판 돌리기 (C / C++) (0) | 2020.03.03 |
|---|---|
| boj, 백준) 17779. 게리맨더링 2 ( C / C++) (0) | 2020.03.01 |
| boj, 백준) 17471. 게리맨더링(C / C++) (0) | 2020.02.29 |
| boj, 백준) 17406. 배열 돌리기 4 ( C / C++) (0) | 2020.02.29 |
| boj, 백준) 17281. ⚾ ( C / C++) (0) | 2020.02.28 |
댓글