인사
안녕하세요. 오랜만에 플래티넘으로 가는 길 시리즈, 저번 포스팅에 이어 세 번째 과정을 소개합니다.
오늘은 브루트포스(Brute Force) 알고리즘에 대해 이야기하려고 합니다.
브루트포스 문제를 풀면서 느낀 점은, 문제의 요구사항을 정확하게 파악하고 그에 맞춰 코드를 작성하는 것이 가장 중요하다는 것입니다. 또한, 단순 구현처럼 보이지만 최적화 관점에서 다양한 고민을 하게 만드는 유형이기도 했습니다.
그럼 이제 문제 소개와 함께 제가 작성한 풀이를 살펴보겠습니다.
문제
오늘 다룰 문제는 백준 17472번 – 다리 만들기 2입니다.
문제 링크
이 문제는 solved.ac 기준 골드 1 난이도의 문제입니다.
저는 예전에 Python으로 한 번 풀어본 경험이 있었는데, 이번에는 C++로 알고리즘 문제 풀이 연습을 하면서 다시 도전하게 되었습니다.
문제를 풀면서 느낀 점은, 브루트포스 알고리즘이 들어가면서도 최적화를 어떻게 적용할지 고민하게 만드는 문제라는 것입니다.
다시 풀어보아도 여전히 까다롭고, 중간에 최적화 방법을 모른다면 상당히 어려운 유형이라는 생각이 들었습니다.
<출처: baekjoon 17472번 그림 설명>
문제 요약
N × M 크기의 나라가 있고, 일부 칸에는 섬이, 나머지 칸에는 바다가 있습니다.
모든 섬이 연결되도록 다리를 설치하되, 다리 길이의 총합이 최소가 되도록 해야 합니다.
기본 규칙
-
다리는 일자로만 놓을 수 있으며, 섬의 가장자리에서 동·서·남·북 방향으로만 연결 가능
-
모든 섬을 연결해야 함
-
최종 출력은 다리 길이 총합의 최소값
다리를 놓을 수 없는 조건
-
다리의 방향이 중간에 바뀌면 안 됨
-
다리의 길이는 2 이상이어야 함
-
다리 양 끝은 반드시 섬이어야 함
입력과 출력 형식
입력
출력
```
입력:
7 8
0 0 0 0 0 0 1 1
1 1 0 0 0 0 1 1
1 1 0 0 0 0 0 0
1 1 0 0 0 1 1 0
0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1
출력:
9
```
전체 코드
우선, 전체 코드를 먼저 보여드리겠습니다.
코드가 다소 길지만, 실행 결과 시간 0ms, 메모리 2088KB로 문제를 통과할 수 있었습니다.
물론 코드 구조를 더 정리할 여지가 있고, 제 풀이가 정답이라고 단정할 수는 없습니다.
다만, “이런 접근법도 가능하다”, “이 문제를 푸는 여러 방법 중 하나다” 정도로 참고해 주시면 좋겠습니다.
풀이 전략
이번 문제를 풀면서 저는 크게 다섯 가지 단계로 접근했습니다.
-
섬 그룹 라벨링
-
가능한 모든 다리 후보 탐색
-
다리 길이 기준 정렬
-
최소 스패닝 트리(MST) 구성
-
연결성 검증
이 다섯 가지 흐름을 기반으로 세부 구현을 진행했습니다.
다음 글에서는 각 단계별 구체적인 풀이 아이디어와 코드 구현 방식을 설명드리겠습니다.
#include <stdio.h>
#include <iostream>
#include <string>
#include <sstream>
#include <tuple>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <limits>
void InputMatrix(int n, int m, int** matrix) {
for ( int i = 0; i < n; i++ ) {
matrix[i] = new int[m];
std::string matrix_s;
getline(std::cin, matrix_s);
std::istringstream iss(matrix_s);
int value, j = 0;
while ( iss >> value ) matrix[i][j++] = value;
}
}
void DeleteMatrix(int n, int** matrix) {
for ( int i = 0; i < n; i++ ) delete[] matrix[i];
delete[] matrix;
}
class HeapSortClass {
public:
HeapSortClass(std::vector<std::tuple<int, int, int>>& roads_) : roads(roads_) {}
void HeapSortFunc() {
int roadSize = roads.size();
for ( int i = ((roadSize / 2) - 1); i > -1 ; i-- ) Heapfy(i, roadSize);
for ( int i = roadSize - 1; i > 0; i-- ) {
std::swap(roads[0], roads[i]);
Heapfy(0, i);
}
}
private:
std::vector<std::tuple<int, int, int>>& roads;
void Heapfy(int i, int upper) {
while ( true ) {
int largest = i;
int left = 2 * i + 1, right = 2 * i + 2;
if ( left < upper && std::get<2>(roads[largest]) < std::get<2>(roads[left]) ) largest = left;
if ( right < upper && std::get<2>(roads[largest]) < std::get<2>(roads[right]) ) largest = right;
if ( i != largest ) {
std::swap(roads[i], roads[largest]);
i = largest;
} else break;
}
}
};
class BruteForce {
public:
BruteForce(int n_, int m_, int** matrix_) : n(n_), m(m_), matrix(matrix_) {
rangeMatrix = new int* [n];
for ( int i = 0; i < n; i++ ) {
rangeMatrix[i] = new int [m];
for ( int j = 0; j < m; j++ ) rangeMatrix[i][j] = 0;
}
}
void Start() {
// range
MakeToken();
// road
std::vector<std::tuple<int, int, int>> roads;
roads.reserve(n * m);
FindRoads(roads);
// sort
HeapSortClass hs(roads);
hs.HeapSortFunc();
// mst
int roadLength = 0;
std::vector<int> union_list;
SetUnionList(union_list);
MST(roads, union_list, roadLength);
// answer
Answer(union_list, roadLength);
std::cout << roadLength << std::endl;
// delete RangeMatrix
DeleteMatrix(n, rangeMatrix);
}
private:
int n;
int m;
int finalToken = 0;
int** matrix;
int** rangeMatrix;
int getIndex(const int row, const int col) {
return row * m + col;
}
void SetVector(std::vector<int>& v, int size, int initValue) {
v.reserve(size);
v.resize(size, initValue);
}
void SetBfsQueue(std::queue<std::tuple<int, int>>& que, std::vector<int>& checks, std::tuple<int, int>& init) {
que.push(init);
int initX = std::get<0>(init), initY = std::get<1>(init);
checks[getIndex(initX, initY)] = 1;
}
bool MakeTokenBfsGobool(const int x, const int y, std::vector<int>& checks) {
// range
if ( x < 0 || x >= n ) return false;
if ( y < 0 || y >= m ) return false;
// checks
if ( checks[getIndex(x, y)] != 0 ) return false;
// 1
if ( matrix[x][y] != 1 ) return false;
return true;
}
void MakeTokenBfsAddQueue(std::queue<std::tuple<int, int>>& que, std::vector<int>& checks, const int newX, const int newY, const int token) {
std::tuple<int, int> newNode(newX, newY);
que.push(newNode);
checks[getIndex(newX, newY)] = 1;
rangeMatrix[newX][newY] = token;
}
void MakeTokenBfsFunc(std::queue<std::tuple<int, int>>& que, std::vector<int>& checks, const int prevX, const int prevY, const int token) {
// up
int newX1 = prevX - 1, newY1 = prevY;
bool upBool = MakeTokenBfsGobool(newX1, newY1, checks);
if ( upBool ) MakeTokenBfsAddQueue(que, checks, newX1, newY1, token);
// down
int newX2 = prevX + 1, newY2 = prevY;
bool downBool = MakeTokenBfsGobool(newX2, newY2, checks);
if ( downBool ) MakeTokenBfsAddQueue(que, checks, newX2, newY2, token);
// right
int newX3 = prevX, newY3 = prevY + 1;
bool rightBool = MakeTokenBfsGobool(newX3, newY3, checks);
if ( rightBool ) MakeTokenBfsAddQueue(que, checks, newX3, newY3, token);
// left
int newX4 = prevX, newY4 = prevY - 1;
bool leftBool = MakeTokenBfsGobool(newX4, newY4, checks);
if ( leftBool ) MakeTokenBfsAddQueue(que, checks, newX4, newY4, token);
}
void MakeTokenBfs(std::vector<int>& checks, std::tuple<int, int>& initNode, int& token) {
std::queue<std::tuple<int, int>> que;
SetBfsQueue(que, checks, initNode);
while ( !que.empty() ) {
std::tuple<int, int> node = que.front();
que.pop();
int prevX = std::get<0>(node), prevY = std::get<1>(node);
MakeTokenBfsFunc(que, checks, prevX, prevY, token);
}
}
void MakeToken() {
int token = 1;
std::vector<int> checks;
SetVector(checks, n * m, 0);
for ( int i = 0; i < n; i++ ) {
for ( int j = 0; j < m; j++ ) {
int index = getIndex(i, j);
if ( checks[index] == 0 && matrix[i][j] == 1 ) {
std::tuple<int, int> node(i, j);
rangeMatrix[i][j] = token;
MakeTokenBfs(checks, node, token);
token += 1;
}
}
}
finalToken = token;
}
bool CheckRoadsBool(const int x, const int y) {
if ( x < 0 || x >= n ) return false;
if ( y < 0 || y >= m ) return false;
if ( matrix[x][y] == 1 ) return false;
return true;
}
bool CheckEndCandidateBool(const int x, const int y, const int start, const int roadLength) {
if ( x < 0 || x >= n ) return false;
if ( y < 0 || y >= m ) return false;
if ( rangeMatrix[x][y] == start ) return false;
if ( roadLength < 2 ) return false;
return true;
}
void ArrowNum(const int arrow, int& x, int& y) {
if ( arrow == 1 ) x -= 1; // up
else if ( arrow == 2 ) x += 1; // down
else if ( arrow == 3 ) y += 1; // right
else if ( arrow == 4 ) y -= 1; // left
}
int FindRoadsFunc(const int arrow, int x, int y, const int start, int& end) {
int roadLength = 0;
while ( true ) {
ArrowNum(arrow, x, y);
bool checkBool = CheckRoadsBool(x, y);
if ( !checkBool ) break;
roadLength += 1;
}
bool roadBool = CheckEndCandidateBool(x, y, start, roadLength);
if ( roadBool ) end = rangeMatrix[x][y];
return roadLength;
}
void FindRoadsFunc(std::vector<std::tuple<int, int, int>>& roads, const int x, const int y) {
int start = rangeMatrix[x][y];
// up
int upEnd = 0;
int upLength = FindRoadsFunc(1, x, y, start, upEnd);
if ( upEnd > 0 ) {
std::tuple<int, int, int> upRoad(start, upEnd, upLength);
roads.push_back(upRoad);
}
// down
int downEnd = 0;
int downLength = FindRoadsFunc(2, x, y, start, downEnd);
if ( downEnd > 0 ) {
std::tuple<int, int, int> downRoad(start, downEnd, downLength);
roads.push_back(downRoad);
}
// right
int rightEnd = 0;
int rightLength = FindRoadsFunc(3, x, y, start, rightEnd);
if ( rightEnd > 0 ) {
std::tuple<int, int, int> rightRoad(start, rightEnd, rightLength);
roads.push_back(rightRoad);
}
// left
int leftEnd = 0;
int leftLength = FindRoadsFunc(4, x, y, start, leftEnd);
if ( leftEnd > 0 ) {
std::tuple<int, int, int> leftRoad(start, leftEnd, leftLength);
roads.push_back(leftRoad);
}
}
void FindRoads(std::vector<std::tuple<int, int, int>>& roads) {
for ( int i = 0; i < n; i++ ) {
for ( int j = 0; j < m; j++ ) {
if ( matrix[i][j] == 1 ) FindRoadsFunc(roads, i, j);
}
}
}
void SetUnionList(std::vector<int>& union_list) {
union_list.reserve(finalToken);
for ( int i = 0; i < finalToken; i++ ) union_list.push_back(i);
}
int Find(std::vector<int>& union_list, int node) {
if ( union_list[node] != node ) {
union_list[node] = Find(union_list, union_list[node]);
return union_list[node];
} else return node;
}
bool Union(std::vector<int>& union_list, int x, int y) {
int nodeX = Find(union_list, x);
int nodeY = Find(union_list, y);
if ( nodeX != nodeY ) {
union_list[nodeY] = nodeX;
return true;
} else return false;
}
void MST(std::vector<std::tuple<int, int, int>>& roads, std::vector<int>& union_list, int& roadMinLength) {
int roadSize = roads.size();
for ( int i = 0; i < roadSize; i++ ) {
std::tuple<int, int, int> node = roads[i];
int x = std::get<0>(node), y = std::get<1>(node), weight = std::get<2>(node);
bool unionBool = Union(union_list, x, y);
if ( unionBool ) roadMinLength += weight;
}
}
void Answer(std::vector<int>& union_list, int& roadMinLength) {
int unionLength = union_list.size();
int iniVal = Find(union_list, 1);
for ( int i = 2; i < unionLength; i++ ) {
int nextVal = Find(union_list, i);
if ( iniVal != nextVal ) {
roadMinLength = -1;
break;
}
}
}
};
int main(void) {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
// n, m
int n, m;
std::cin >> n >> m;
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
// matrix
int** matrix = new int* [n];
InputMatrix(n, m, matrix);
// bruteForce
BruteForce bf(n, m, matrix);
bf.Start();
// delete matrix
DeleteMatrix(n, matrix);
return 0;
}
<문제 결과>
문제 풀이1 – 섬의 그룹 라벨링
첫 번째 단계는 **섬에 그룹 번호(라벨)**를 붙이는 작업입니다.
이 과정을 진행한 이유는, 입력값만으로는 다리의 시작점과 끝점을 구분할 수 없었기 때문입니다.
문제에서 제공되는 입력은 0과 1로 구성된 N × M 행렬입니다.
하지만 이 정보만으로는 “어느 섬에서 어느 섬으로 이동하는지” 알 수 없습니다.
그래서 저는 **각 섬에 고유 이름(토큰)**을 붙여,
다리의 출발점과 도착점을 명확하게 식별할 수 있도록 했습니다.
구현 방식 – MakeToken 함수
-
브루트포스로 N × M의 모든 좌표 (i, j)를 완전 탐색
-
해당 위치에 섬(값이 1)이 있다면 BFS를 실행해 주변 연결된 땅을 같은 그룹 번호로 라벨링
-
이렇게 같은 그룹 번호를 가진 영역은 하나의 섬이 되며, 이 라벨 정보를 rangeMatrix에 저장
시간 복잡도 최적화
이 단계가 완료되면,
다리 탐색 시 *“이 좌표는 몇 번 섬이다”*라는 정보를 바로 참조할 수 있어
이후 알고리즘 단계를 훨씬 효율적으로 진행할 수 있습니다.
bool MakeTokenBfsGobool(const int x, const int y, std::vector<int>& checks) {
// range
if ( x < 0 || x >= n ) return false;
if ( y < 0 || y >= m ) return false;
// checks
if ( checks[getIndex(x, y)] != 0 ) return false;
// 1
if ( matrix[x][y] != 1 ) return false;
return true;
}
void MakeTokenBfsAddQueue(std::queue<std::tuple<int, int>>& que, std::vector<int>& checks, const int newX, const int newY, const int token) {
std::tuple<int, int> newNode(newX, newY);
que.push(newNode);
checks[getIndex(newX, newY)] = 1;
rangeMatrix[newX][newY] = token;
}
void MakeTokenBfsFunc(std::queue<std::tuple<int, int>>& que, std::vector<int>& checks, const int prevX, const int prevY, const int token) {
// up
int newX1 = prevX - 1, newY1 = prevY;
bool upBool = MakeTokenBfsGobool(newX1, newY1, checks);
if ( upBool ) MakeTokenBfsAddQueue(que, checks, newX1, newY1, token);
// down
int newX2 = prevX + 1, newY2 = prevY;
bool downBool = MakeTokenBfsGobool(newX2, newY2, checks);
if ( downBool ) MakeTokenBfsAddQueue(que, checks, newX2, newY2, token);
// right
int newX3 = prevX, newY3 = prevY + 1;
bool rightBool = MakeTokenBfsGobool(newX3, newY3, checks);
if ( rightBool ) MakeTokenBfsAddQueue(que, checks, newX3, newY3, token);
// left
int newX4 = prevX, newY4 = prevY - 1;
bool leftBool = MakeTokenBfsGobool(newX4, newY4, checks);
if ( leftBool ) MakeTokenBfsAddQueue(que, checks, newX4, newY4, token);
}
void MakeTokenBfs(std::vector<int>& checks, std::tuple<int, int>& initNode, int& token) {
std::queue<std::tuple<int, int>> que;
SetBfsQueue(que, checks, initNode);
while ( !que.empty() ) {
std::tuple<int, int> node = que.front();
que.pop();
int prevX = std::get<0>(node), prevY = std::get<1>(node);
MakeTokenBfsFunc(que, checks, prevX, prevY, token);
}
}
void MakeToken() {
int token = 1;
std::vector<int> checks;
SetVector(checks, n * m, 0);
for ( int i = 0; i < n; i++ ) {
for ( int j = 0; j < m; j++ ) {
int index = getIndex(i, j);
if ( checks[index] == 0 && matrix[i][j] == 1 ) {
std::tuple<int, int> node(i, j);
rangeMatrix[i][j] = token;
MakeTokenBfs(checks, node, token);
token += 1;
}
}
}
finalToken = token;
}
문제 풀이2 – 각 섬에서 만들 수 있는 모든 다리 조사
두 번째 단계는 모든 섬에서 만들 수 있는 다리 후보를 전부 탐색하는 작업입니다.
이 단계 역시 브루트포스 알고리즘을 사용하여,
N × M 행렬을 완전 탐색하면서 섬이 위치한 곳(값이 1)을 기준으로 동·서·남·북 방향으로 다리를 뻗어 보았습니다.
구현 아이디어
-
현재 좌표가 섬(1)이라면, 네 방향(상·하·좌·우)으로 이동 시뮬레이션
-
이동 중 바다(0)를 만나면 계속 진행, 다른 섬을 만나면 다리 후보 완성
-
도중에 문제에서 주어진 조건을 만족하지 않으면 중단
시뮬레이션 조건
-
방향 유지 – 이동 중 방향이 바뀌면 안 됨
-
최소 길이 2 이상 – 다리 길이가 2 미만이면 무효
-
다리 양 끝은 모두 섬 – 바다에서 끝나면 무효
이 조건을 만족하면 (출발 섬, 도착 섬, 다리 길이) 형태로
roads 벡터에 저장합니다.
코드 로직 구성
-
CheckRoadsBool – 이동 가능 여부(맵 범위, 섬 여부) 검사
-
CheckEndCandidateBool – 다리 끝점 후보 유효성 검사
-
ArrowNum – 방향(상·하·좌·우)에 따라 좌표 변경
-
FindRoadsFunc (단일 방향) – 한 방향으로 다리를 뻗으며 길이 계산
-
FindRoadsFunc (4방향) – 상·하·좌·우 네 방향에 대해 다리 탐색
-
FindRoads – 맵 전체를 탐색하며 모든 다리 후보 수집
최적화에 대한 고민
이 단계에서는 직접적인 최적화는 하지 않았습니다.
다만, 이후 MST(최소 스패닝 트리) 알고리즘에서 유용하게 쓰이도록,
roads에 중복되는 (시작, 끝, 길이) 정보를 넣지 않도록 map을 사용해 관리하는 방법을 고민했습니다.
이번 문제의 입력 크기에서는 크게 필요하지 않았지만,
만약 입력 크기가 매우 커진다면 메모리를 조금 더 사용하더라도 중복 제거를 시도하는 것이 유의미할 수 있습니다.
bool CheckRoadsBool(const int x, const int y) {
if ( x < 0 || x >= n ) return false;
if ( y < 0 || y >= m ) return false;
if ( matrix[x][y] == 1 ) return false;
return true;
}
bool CheckEndCandidateBool(const int x, const int y, const int start, const int roadLength) {
if ( x < 0 || x >= n ) return false;
if ( y < 0 || y >= m ) return false;
if ( rangeMatrix[x][y] == start ) return false;
if ( roadLength < 2 ) return false;
return true;
}
void ArrowNum(const int arrow, int& x, int& y) {
if ( arrow == 1 ) x -= 1; // up
else if ( arrow == 2 ) x += 1; // down
else if ( arrow == 3 ) y += 1; // right
else if ( arrow == 4 ) y -= 1; // left
}
int FindRoadsFunc(const int arrow, int x, int y, const int start, int& end) {
int roadLength = 0;
while ( true ) {
ArrowNum(arrow, x, y);
bool checkBool = CheckRoadsBool(x, y);
if ( !checkBool ) break;
roadLength += 1;
}
bool roadBool = CheckEndCandidateBool(x, y, start, roadLength);
if ( roadBool ) end = rangeMatrix[x][y];
return roadLength;
}
void FindRoadsFunc(std::vector<std::tuple<int, int, int>>& roads, const int x, const int y) {
int start = rangeMatrix[x][y];
// up
int upEnd = 0;
int upLength = FindRoadsFunc(1, x, y, start, upEnd);
if ( upEnd > 0 ) {
std::tuple<int, int, int> upRoad(start, upEnd, upLength);
roads.push_back(upRoad);
}
// down
int downEnd = 0;
int downLength = FindRoadsFunc(2, x, y, start, downEnd);
if ( downEnd > 0 ) {
std::tuple<int, int, int> downRoad(start, downEnd, downLength);
roads.push_back(downRoad);
}
// right
int rightEnd = 0;
int rightLength = FindRoadsFunc(3, x, y, start, rightEnd);
if ( rightEnd > 0 ) {
std::tuple<int, int, int> rightRoad(start, rightEnd, rightLength);
roads.push_back(rightRoad);
}
// left
int leftEnd = 0;
int leftLength = FindRoadsFunc(4, x, y, start, leftEnd);
if ( leftEnd > 0 ) {
std::tuple<int, int, int> leftRoad(start, leftEnd, leftLength);
roads.push_back(leftRoad);
}
}
void FindRoads(std::vector<std::tuple<int, int, int>>& roads) {
for ( int i = 0; i < n; i++ ) {
for ( int j = 0; j < m; j++ ) {
if ( matrix[i][j] == 1 ) FindRoadsFunc(roads, i, j);
}
}
}
문제 풀이3 – 힙 정렬로 오름차순 정리
세 번째 단계는 다리 정보를 길이 기준으로 오름차순 정렬하는 작업입니다.
사실 일반적으로는 std::sort를 이용해 간단하게 정렬할 수 있습니다.
하지만 제 경우, std::vector<std::tuple<int, int, int>> 형태로
(start, end, weight) 데이터를 저장하고 있었기 때문에,
MST(최소 스패닝 트리) 알고리즘을 적용하기 위해 **weight(다리 길이)**를 기준으로 정렬할 필요가 있었습니다.
왜 힙 정렬(Heap Sort)을 사용했나?
저는 힙 정렬, 병합 정렬, 퀵 정렬을 모두 구현할 수 있었고,
이 중에서 최악의 경우에도 O(N log N) 성능을 보장하는 힙 정렬을 선택했습니다.
또한, 이번에는 직접 구현 연습을 겸해서 HeapSortClass로 구조화했습니다.
구현 개요
-
힙 구성
-
정렬 과정
-
루트(가장 큰 값)과 마지막 노드를 교환
-
힙 크기를 줄이며 Heapfy 반복 수행
-
결과적으로 오름차순 정렬 완성
특징
이 단계까지 완료하면,
다음에 진행할 MST 알고리즘(Union-Find) 단계에서
가장 짧은 다리부터 차례대로 선택할 수 있게 되어 효율적으로 최소 비용을 계산할 수 있습니다.
class HeapSortClass {
public:
HeapSortClass(std::vector<std::tuple<int, int, int>>& roads_) : roads(roads_) {}
void HeapSortFunc() {
int roadSize = roads.size();
for ( int i = ((roadSize / 2) - 1); i > -1 ; i-- ) Heapfy(i, roadSize);
for ( int i = roadSize - 1; i > 0; i-- ) {
std::swap(roads[0], roads[i]);
Heapfy(0, i);
}
}
private:
std::vector<std::tuple<int, int, int>>& roads;
void Heapfy(int i, int upper) {
while ( true ) {
int largest = i;
int left = 2 * i + 1, right = 2 * i + 2;
if ( left < upper && std::get<2>(roads[largest]) < std::get<2>(roads[left]) ) largest = left;
if ( right < upper && std::get<2>(roads[largest]) < std::get<2>(roads[right]) ) largest = right;
if ( i != largest ) {
std::swap(roads[i], roads[largest]);
i = largest;
} else break;
}
}
};
문제 풀이 4 – 총 길이의 최솟값 구하기
이제 roads 벡터에는 다리의 출발 섬, 도착 섬, 다리 길이가 모두 저장되어 있습니다.
그렇다면 여기서 모든 섬을 연결하는 총 다리 길이의 최소값을 어떻게 구할까요?
핵심 아이디어
-
모든 섬을 연결한다는 것은 곧 **하나의 그룹(네트워크)**를 만든다는 의미입니다.
-
그룹을 만드는 전형적인 방법은 Union-Find(유니온 파인드) 알고리즘입니다.
-
여기에 최소 비용까지 고려한다면, MST(최소 스패닝 트리) 알고리즘을 적용해야 합니다.
즉,
구현 개요
-
초기화 – union_list를 생성해 각 노드(섬)를 자기 자신으로 초기화
-
정렬된 roads 순회 – 다리 길이가 짧은 순서대로 탐색
-
Union-Find로 연결 여부 확인
-
이미 같은 그룹이면 무시
-
다른 그룹이면 연결 후 총 길이에 추가
-
최종 길이 반환
이 단계까지 완료하면,
최소 비용으로 모든 섬을 연결할 수 있으며,
다음 단계에서 모든 섬이 실제로 연결되었는지 검증만 해주면 됩니다.
void SetUnionList(std::vector<int>& union_list) {
union_list.reserve(finalToken);
for ( int i = 0; i < finalToken; i++ ) union_list.push_back(i);
}
int Find(std::vector<int>& union_list, int node) {
if ( union_list[node] != node ) {
union_list[node] = Find(union_list, union_list[node]);
return union_list[node];
} else return node;
}
bool Union(std::vector<int>& union_list, int x, int y) {
int nodeX = Find(union_list, x);
int nodeY = Find(union_list, y);
if ( nodeX != nodeY ) {
union_list[nodeY] = nodeX;
return true;
} else return false;
}
void MST(std::vector<std::tuple<int, int, int>>& roads, std::vector<int>& union_list, int& roadMinLength) {
int roadSize = roads.size();
for ( int i = 0; i < roadSize; i++ ) {
std::tuple<int, int, int> node = roads[i];
int x = std::get<0>(node), y = std::get<1>(node), weight = std::get<2>(node);
bool unionBool = Union(union_list, x, y);
if ( unionBool ) roadMinLength += weight;
}
}
문제 풀이 5 – 모든 섬이 연결되었는지 확인
마지막 단계는 모든 섬이 하나의 그룹으로 연결되었는지 검증하는 작업입니다.
앞선 MST(최소 스패닝 트리) 과정에서는 최소 비용으로 다리를 선택했지만,
경우에 따라 일부 섬이 연결되지 않고 남을 수도 있습니다.
따라서 최종적으로 모든 섬이 한 네트워크에 속해 있는지를 확인해야 합니다.
구현 아이디어
시간 복잡도
void Answer(std::vector<int>& union_list, int& roadMinLength) {
int unionLength = union_list.size();
int iniVal = Find(union_list, 1);
for ( int i = 2; i < unionLength; i++ ) {
int nextVal = Find(union_list, i);
if ( iniVal != nextVal ) {
roadMinLength = -1;
break;
}
}
}
결론
이번 풀이를 통해 문제를 해결할 수 있었고,
제가 추정한 전체 로직의 시간 복잡도는 O(N² × M²) 입니다.
문제 제한에서 N, M이 최대 10이므로 연산량이 매우 적어 실제 실행 시간은 0ms가 나왔습니다.
과거에 Python으로 풀었을 때는 시간이 꽤 걸렸는데,
다시 생각해 보니 언어적인 차이뿐 아니라, 당시에는 코드 구조가 다소 비효율적이었던 것도 원인인 것 같습니다.
문제에서 활용한 알고리즘
이 한 문제 안에 다양한 알고리즘이 모두 녹아있었습니다.
-
브루트포스(Brute Force)
-
시뮬레이션(Simulation)
-
BFS (너비 우선 탐색)
-
MST (최소 스패닝 트리)
-
Union-Find
-
Heap Sort
데이터 흐름 요약
-
입력 처리 – N, M과 나라의 matrix 입력
-
섬 라벨링 – 각 섬을 구분하는 rangeMatrix 생성
-
다리 후보 수집 – (시작, 끝, 길이) 정보를 roads 벡터에 저장
-
Union-Find 초기화 – 섬 그룹 정보를 저장하는 union_list 생성
-
최종 결과 계산 – 모든 섬이 연결되면 최소 비용 반환, 아니면 -1 반환
이번 문제는 단일 알고리즘 풀이가 아닌, 여러 알고리즘을 유기적으로 조합해야만 풀 수 있는 좋은 연습 문제였습니다.
다리를 찾는 과정, 최적 경로를 계산하는 과정, 그리고 연결성 검증까지
모든 단계를 직접 구현하면서 알고리즘 이해도와 구현 능력을 동시에 높일 수 있었습니다.
마무리
오늘은 플래티넘으로 가는 길 시리즈의 세 번째 포스팅을 진행했습니다.
이번에 다룬 문제 외에도 브루트포스 알고리즘을 활용한 여러 문제를 풀었는데,
그중에서 소개하지 못한 백준 16985번 – Maaaaaaaaaze(문제 링크)와
백준 16971번 – 배열 B의 값 문제를 추가로 추천드립니다.
이번 문제 풀이를 진행하면서 골드 2로 승급하게 되었는데,
골드까지는 빠르게 올라왔지만 플래티넘 진입은 확실히 쉽지 않은 도전이었습니다.
그래서 더더욱 달성했을 때의 성취감이 클 것 같습니다.
다음 포스팅에서는 BFS 알고리즘을 주제로 준비할 계획입니다.
모두 각자의 자리에서 좋은 결과 있으시길 바라며, 화이팅입니다!
