백준[1774] 우주신과의 교감
2021. 6. 22. 15:35
Algorithm/BOJ
풀이 방법 크루스칼 알고리즘을 이용하여 풀이한다. 이미 연결 된 간선은 미리 연결해놓고 가장 거리가 짧은 간선을 뽑아 사이클이 있는지 확인하고 연결한다. 코드 우선순위큐를 이용한 구현 #include #include #include #include #include using namespace std; using ll = long long; using pll = pair; using pdll = pair; pll arr[1003]; ll N, M, par[1003], cnt, lev[1003]; priority_queue pq; ll dist(pll a, pll b) { return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (..
백준[4386] 별자리 만들기
2021. 6. 22. 00:39
Algorithm/BOJ
풀이 방법 최소 신장 트리(MST)를 구하는 문제이다. MST는 prim 알고리즘과 kruskal 알고리즘을 통해 구할 수 있다. 이 풀이는 prim 알고리즘을 이용했다. cf) prim 알고리즘을 모른다면 여기를 참고하세요 코드 #include #include #include using namespace std; using pdd = pair; using pdi = pair; pdd arr[102]; bool visited[102]; priority_queue pq; // 최소 힙 int N; double ans; //점과 점 사이의 거리 double dist(pdd a, pdd b) { return sqrt((a.first - b.first) * (a.first - b.first) + (a.secon..
백준[9372] 상근이의 여행
2021. 6. 21. 23:54
Algorithm/BOJ
풀이 방법 spanning tree의 간선의 개수를 구하는 간단한 dfs 문제다. spanning tree의 간선의 개수는 dfs 또는 bfs 탐색 중 사용하는 간선을 모으면 된다. 코드 #include #include #include using namespace std; bool visited[1003]; vector v; int ans; void dfs(int s) { visited[s] = true; ans++; for (auto i : v[s]) { if (!visited[i]) dfs(i); } } int main() { int T; scanf("%d", &T); while (T--) { int N, M; scanf("%d %d", &N, &M); v.clear(); v.resize(N + 1)..
백준[20040] 사이클게임
2021. 6. 21. 23:26
Algorithm/BOJ
풀이 방법 유니온 파인드라는 자료구조를 이용하여 풀이하였다. 입력받은 두개의 루트 노드가 같으면 사이클이 형성되었다고 판단하고, 다르다면 두개의 트리를 합친다. 코드 #include #include using namespace std; int par[500005], level[500005]; int find(int x) { if (x == par[x]) return x; return par[x] = find(par[x]); } void merge(int x, int y) { int a = find(x), b = find(y); if (a == b) return; if (level[a] > level[b]) swap(a, b); if (level[a] == level[b]) level[b]++; par[a..
백준[2629] 양팔저울
2021. 5. 3. 22:19
Algorithm/BOJ
풀이 방법 dp[i][j] : i번째 추까지 사용했을 때 무게 j를 만들 수 있는지 여부 i번째 상태는 i - 1번째 상태에 i번째 무게만큼 더할 것인지 뺄 것인지 아무것도 안 할 것인지로 정의할 수 있다. 코드 무게가 음수인 경우를 커버하기 위해 40000을 기본값으로 했다. #include int weight[32]; bool dp[32][80004]; int main() { int N; scanf("%d", &N); for (int i = 1; i