프로그래머스 - 섬 연결하기
문제 링크입니다 : https://programmers.co.kr/learn/courses/30/lessons/42861# 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 그래프 문제였다. 최단 경로를 먼저 탐색하기 위해서 우선순위 큐를 사용하고 각 섬들이 서로 연결되어 있지 않은 상태라면 연결해주면 된다. 섬이 N개 라면 n - 1개 만큼의 노드를 연결해주어야 사이클이 생기지 않는다. #include #include #include #include using namespace std; vector parent; int findParent(int a) { if(parent[a] == a) return a; ..
백준 - 11085 군사 이동
문제 링크입니다 : https://www.acmicpc.net/problem/11085 11085번: 군사 이동 문제 전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재�� www.acmicpc.net 우선순위 큐 + 유니온 파인드 문제였다. 우선순위 큐로 가장 너비가 넓은 경로 순으로 꺼는 걸 반복하면서 유니온 파인드로 B와 C로 통하는 경로가 있는지 확인해서 경로가 있다면 끝내면 된다. #include #include #include using namespace std; int p, w; int b, c; vecto..
백준 - 3197 백조의 호수
문제 링크입니다 : https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있� www.acmicpc.net BFS + 유니온 파인드 문제였다. 호수 영역을 BFS로 나누고 유니온 파인드로 호수들이 합쳐쳤는지 확인하는 방법으로 구현했다. #include #include #include using namespace std; const int dy[4] = {0, 0, -1, 1}; const int dx[4] = {-1, 1, 0 ,0}; int R, C; vector board; ve..