(백준/c++) 17472번 - 다리만들기

17472번: 다리 만들기 2 (acmicpc.net)

17472번: 다리 만들기 2

 유니온 파인드, 크루스칼, BFS

void InputFunc(); 
- 입력 받는 함수

void CreateGroup();
void CreateGroupBFSFunc(int pX, int pY, int pGroupNum);
- 섬을 찾아서 그룹을 만들고 번호를 부여함.

void BridgeConnection();
void FindAllBridge(int pX, int pY);
- 동서남북 방향으로 갈 수 있는 곳까지 출발한 섬 번호와 다른 번호를 만났을때 다리를 연결해줌.
- 길이가 2인 모든 경우를 넣어줌. 

void IslandUnion(int pIsland01, int pIsland02); 
bool IslandFind(int pIsland01, int pIsland02);
int  GetParent(int pNum);
- 일반적인 유니온 파인드 코드

void MSTKruskal();
- 크루스칼 알고리즘을 통해 가장 짧은 거리부터 연결해줌.
- 모두 연결 후 모든 섬이 연결 되었는지 확인함. <- 이 부분 때문에 하루 잡아 먹은듯 ..