오랜만에 빡구현 문제를 만났다. 처음에 접근하기를 우선 BFS를 통해 섬들을 구분하자였고, 그 다음은 이 섬들 간의 거리를 배열에 저장시켜서 이것을 활용해먹자는 생각이었다. 하지만, 거리를 배열에 저장해놓고 이것을 어떻게 활용해먹지? 라는 의문이 사라지지 않았는데, 결국 알고리즘 분류를 눌러 힌트를 보고 아 이걸 최소 스패닝 트리로 작성하면 되는 구나! 라는 생각을 하게 되었다.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<tuple>
#include<map>
#include<stack>
#include<set>
using namespace std;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
int N, M;
int d = 2;
bool cmp(iii&a, iii&b)
{
return a.second < b.second;
}
vector<vector<int>> place;
vector<vector<ii>> island(8, vector<ii>());
vector<vector<int>> adj(8, vector<int>(8, 1000));
vector<int> s;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
void BFS()
{
for ( int i = 0; i < N; i++ )
{
for ( int j = 0; j < M; j++ )
{
if ( place[i][j] == 1 )
{
queue<ii> que;
que.push({ i,j });
while ( !que.empty() )
{
int y, x;
tie(y, x) = que.front();
que.pop();
if ( place[y][x] != 1 )continue;
place[y][x] = d;
island[d].push_back({ y,x });
for ( int k = 0; k < 4; k++ )
{
int nx = x + dx[k];
int ny = y + dy[k];
if ( nx >= M || nx < 0 || ny >= N || ny < 0 || place[ny][nx] != 1 )continue;
que.push({ ny,nx });
}
}
d++;
}
}
}
}
int Find(int x)
{
if ( s[x] == -1 )return x;
return s[x] = Find(s[x]);
}
bool Union(int x, int y)
{
int sx = Find(x);
int sy = Find(y);
if ( sx == sy ) return false;
if ( sx < sy ) s[sy] = sx;
else s[sx] = sy;
return true;
}
void DFS(int dir, int y, int x, int d, int num)
{
if ( dir == 1 ) //오른쪽
{
if ( x + 1 < M)
{
if ( place[y][x + 1] == 0 )
{
DFS(dir, y, x + 1, d + 1, num);
}
else if ( place[y][x + 1] != num )
{
if ( d == 1 )return;
int destNum = place[y][x + 1];
adj[num][destNum] = min(adj[num][destNum], d);
return;
}
else return;
}
}
else if ( dir == 2 ) // 왼쪽
{
if ( x - 1 >= 0 )
{
if ( place[y][x - 1] == 0 )
{
DFS(dir, y, x-1, d + 1, num);
}
else if ( place[y][x - 1] != num )
{
if ( d == 1 )return;
int destNum = place[y][x - 1];
adj[num][destNum] = min(adj[num][destNum], d);
return;
}
else return;
}
}
else if ( dir == 3 ) //위쪽
{
if ( y - 1 >= 0 )
{
if ( place[y-1][x] == 0 )
{
DFS(dir, y - 1, x, d + 1, num);
}
else if ( place[y-1][x] != num )
{
if ( d == 1 )return;
int destNum = place[y - 1][x];
adj[num][destNum] = min(adj[num][destNum], d);
return;
}
else return;
}
}
else //아래쪽
{
if ( y + 1 < N )
{
if ( place[y + 1][x] == 0 )
{
DFS(dir, y + 1, x, d + 1, num);
}
else if ( place[y + 1][x ] != num )
{
if ( d == 1 )return;
int destNum = place[y + 1][x];
adj[num][destNum] = min(adj[num][destNum], d);
return;
}
else return;
}
}
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> N >> M;
place.resize(N, vector<int>(M));
for ( int i = 0; i < N; i++ )
{
for ( int j = 0; j < M; j++ )
{
cin >> place[i][j];
}
}
BFS();
s.resize(d + 1, -1);
for ( int i = 2; i < d; i++ )
{
vector<ii> sums = island[i];
for ( ii &start : sums )
{
for ( int j = 1; j < 5; j++ )
{
DFS(j, start.first, start.second, 0, i);
}
}
}
vector<iii> arr;
for ( int i = 2; i < d; i++ )
{
for ( int j = 2; j < d; j++ )
{
if ( adj[i][j] == 1000 )continue;
arr.push_back({ { i,j }, adj[i][j] });
}
}
sort(arr.begin(), arr.end(), cmp);
int total = 0;
for ( int i = 0; i < arr.size(); i++ )
{
iii &t = arr[i];
int x = t.first.first;
int y = t.first.second;
int d = t.second;
if ( Find(x) != Find(y) )
{
total += d;
Union(x, y);
}
}
for ( int i = 2; i < d; i++ )
{
if ( Find(i) != 2 )
{
cout << -1 << endl;
return 0;
}
}
cout << total << endl;
return 0;
}우선 전체 코드이다. DFS 함수는 처음 설정된 방향으로 쭉쭉 나아가는 함수이며 마지막에 다른 섬에 다았을 때 adj 배열을 살펴보고 해당 배열의 값보다 작다면 배열을 재설정해준다. 중요한 점은 한 방향으로 나아가야만 한다는 점이다. BFS로 코드를 작성하는게 더 깔끔할 거 같다는 생각이 든다.
BFS함수는 섬을 찾는 함수이다. place[i][j]가 0이 아니라면 섬에 해당하는 뜻이므로 해당 위치 주변을 살펴보아 0이 아닌 곳들을 모두 섬으로 포함시켜주었다. 이때 섬들을 int로 구분하였고 편의를 위해 2부터 시작하였다.
어쨋든 순서는 BFS를 통해 섬들을 구분 짓고 -> DFS를 통해 섬들간의 거리를 구해주고 -> 마지막엔 최소 스패닝 트리 알고리즘을 사용하여 섬들사이 거리의 최솟값을 구해주면 된다. 이 때 나는 분리집합을 사용하였는데 우선순위 큐를 사용하여도 똑같은 결과가 나올 것이다.
게임개발자