백준 알고리즘 21738 얼음깨기 펭귄 C++ 코드
남극에 펭귄 한 마리와 크기와 모양이 동일한 N 개의 얼음 블록이 있습니다.
펭귄은 N개의 얼음 블록 중 한 곳 위에 서 있습니다.
펭귄이 서있는 얼음 블록 (이하 블록)을 기준으로 다른 블록들이 연결되어 있으며, 각 블록으로 이동할 수 있는 경로는 한 가지만 존재합니다.
N개의 얼음 블록 중 M 개의 블록은 지지대 블록으로, 일반 블록들이 무너지지 않도록 지탱해주는 역할을 합니다.
일반 블록들은 지지대 블록이 하나라도 연결되어 있으면 무너지지 않습니다.
또한, 지지대 블록들 사이에 이동을 위해서는 반드시 펭귄이 서있는 블록 (이하 루트 블록)을 거쳐야 합니다.
또한, 루트 블록이 무너지지 않기 위해서는 지지대 블록이 반드시 두개 이상 연결되어 있어야 합니다.
또한, 루트 블록이 무너지지 않기 위해서는 지지대 블록이 반드시 두개 이상 연결되어 있어야 합니다.
이 문제는 펭귄이 서있는 루트 블록을 루트 노드로 하는 트리 구조 문제로 볼 수 있습니다.
루트 블록이 무너지지 않으려면 지지대 블록 두개만 연결되어 있으면 되기 때문에, 루트 블록과 가장 가까운 지지대 블록 두개를 찾기만 하면 됩니다.
트리 구조에서 특정 노드를 찾는 방법은 너비우선탐색과 깊이우선탐색이 있는데, 루트블록과 가장 가까운 블록을 빠르게 찾기 위해서는 가까운 블록부터 먼저 검사하는 너비우선탐색을 사용하면 됩니다.
방법을 설명하기 위해 위 그림과 같이 10개 블록이 연결되어 있다고 가정하겠습니다.
큐에 루트 블록과 인접한 블록인 1, 2, 3번 블록을 삽입합니다. 그리고 큐가 빌 때 까지 다음의 작업을 반복합니다.
큐에서 추출한 1번 블록이 지지대 블록인지 검사합니다. 만약 지지대 블록이 아닌 일반 블록이라면, 해당 블록에 연결된 자식 블록인 4, 5번 블록을 큐에 삽입합니다. 그리고 큐에서 다음 블록을 추출하여 같은 작업을 반복합니다.
다음으로 추출한 2번 블록은 지지대 블록이기 때문에 해당 블록과 루트블록까지의 거리를 계산하여 지지대 블록 거리 배열 PD에 삽입합니다. 현재는 거리가 1이기 때문에 1을 삽입하였습니다.
루트 블록이 무너지지 않으려면 지지대 블록이 2개 존재해야 하는데, 현재 지지대 블록 거리 배열에는 원소가 한 개 밖에 없기 때문에 이전과 마찬가지로 2번 블록의 자식 블록인 6번과 7번을 큐에 삽입합니다.
큐에서 추출한 3번 블록은 지지대 블록이 아니기 때문에 마찬가지로 8번 블록과 9번 블록을 큐에 삽입합니다.
다음으로 추출한 4번 블록은 지지대 블록이기 때문에 해당 블록과 루트 블록까지의 거리인 2를 지지대 블록 거리 배열에 삽입합니다.
그리고 지지대 블록 거리 배열의 원소 개수가 2가 되었으므로, 큐를 이용한 블록 탐색을 종료하고 반복문을 탈출합니다.
최종적으로, 위의 그림과 같이 두 지지대 블록과 루트 블록 개수인 4개를 제외한 나머지 블록을 무너뜨릴 수 있습니다. 이를 계산하기 위해, 전체개수인 10에서 지지대 블록 거리 배열의 원소 합 (1+2)인 3과 루트 블록 1을 더한 4를 빼서 얻은 값인 6개의 블록을 무너뜨릴 수 있게 됩니다.
[소스코드]
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;
struct node_struct_t {
int currNode;
int rootNode;
};
//INFO: 블록 개수
int numBlocks{ 0 };
//INFO: 지지대 개수
int numProps{ 0 };
//INFO: 펭귄위치
int kingPos{ 0 };
//INFO: 펭귄과 가까이 있는 노드 목록
vector<int> nearNodeArr;
//INFO: 너비 우선탐색에 사용되는 큐
queue<node_struct_t> que;
//INFO: 각 블록에 연결된 노드 집합
unordered_map<int, unordered_set<int>> blockMap;
//INFO: 현재 노드와 펭귄 노드 사이의 거리 정보
unordered_map<int, int> nodeDist;
//INFO: 펭귄으로부터 발견한 지지대까지의 거리
vector<int> propDist;
//INFO: 지지대를 찾은 뿌리 노드 집합
unordered_set<int> finishNodeSet;
/* INFO: 알고리즘 계산 함수 */
void findMethod() {
while (que.empty() == false) {
node_struct_t& nodeInfo = que.front();
//printf("currNode: %d, rootNode: %d\n", nodeInfo.currNode, nodeInfo.rootNode);
que.pop();
int& currNode = nodeInfo.currNode;
int& rootNode = nodeInfo.rootNode;
if (finishNodeSet.count(rootNode) != 0) {
//INFO: 지지대가 이미 발견된 뿌리 노드면 continue
continue;
}
int dist = nodeDist[currNode];
if (currNode <= numProps) {
//INFO: 지지대 블록 찾음
finishNodeSet.insert(rootNode);
propDist.push_back(dist);
//INFO: 가장 가까운 지지대 두개를 찾았으므로 끝
if (propDist.size() == 2) {
break;
}
}
auto& childList = blockMap[currNode];
//INFO: 연결된 자식 노드를 큐에 추가
for (auto& child : childList) {
nodeDist[child] = dist + 1;
node_struct_t nodeInfo;
nodeInfo.currNode = child;
nodeInfo.rootNode = rootNode;
que.push(nodeInfo);
blockMap[child].erase(currNode);
}
}
}
int main() {
scanf("%d %d %d", &numBlocks, &numProps, &kingPos);
//INFO: 블록들의 거리를 최대값으로 초기화
for (int i = 1; i <= numBlocks; i++) {
nodeDist.insert(std::make_pair(i, 1000000));
}
nodeDist.insert(std::make_pair(kingPos, 0));
for (int i = 1; i < numBlocks; i++) {
int val1, val2;
scanf("%d %d", &val1, &val2);
//INFO: 인접 노드 찾기
if (val1 == kingPos) {
nearNodeArr.push_back(val2);
}
else if (val2 == kingPos) {
nearNodeArr.push_back(val1);
}
//INFO: 블록 정보 입력
blockMap[val1].insert(val2);
blockMap[val2].insert(val1);
}
//INFO: 처음에 계산할 노드 큐에 삽입
for (int i = 0; i < nearNodeArr.size(); i++) {
int& nearNode = nearNodeArr[i];
nodeDist[nearNode] = 1;
//INFO: 현재 노드와 뿌리 노드 정보를 함께 전달
node_struct_t nodeInfo;
nodeInfo.currNode = nearNode;
nodeInfo.rootNode = nearNode;
que.push(nodeInfo);
blockMap[nearNode].erase(kingPos);
}
findMethod();
//INFO: 펭귄위치부터 지지대까지의 거리
int sum = propDist[0] + propDist[1] + 1;
//INFO: 전체 블록 개수에서 sum을 빼면 나머지는 전부 제거 가능
int result = numBlocks - sum;
printf("%d\n", result);
return 0;
}