-
[BOJ] 2162 : 선분 그룹
2162 : 선분 그룹 풀이 선분이 교차하면 묶어주면 된다 코드 #include <bits/stdc++.h> #define fst first #define snd second using namespace std; typedef pair<int, int> pi; int n, par[3003], cnt[3003]; pi p[6003]; int ccw(pi a, pi b, pi c) { int r = a.fst*b.snd + b.fst*c.snd + c.fst*a.snd; r -= a.snd*b.fst + b.snd*c.fst + c.snd*a.fst; if (r > 0) return 1; if (r < 0) return -1; return 0; } int iscross(pi a, pi b, pi...
-
[BOJ] 16168 : 퍼레이드
16168 : 퍼레이드 풀이 degree 짝수가 어쩌구 저쩌구 해서 풀어도 되는데 그냥 제곱 돌려도 된다. 근데 degree 어쩌구 저쩌구 할 때 유의해야 할 점은 connected graph가 아닐 수도 있어서 유니온파인드 같은 걸 해줘야한다. 잘 짜주면 된다. 코드 #include <cstdio> #include <cstdlib> #include <vector> using namespace std; int n, m, chk[3003][3003]; vector<int> gph[3003]; void dfs(int now, int num, int cnt) { if (cnt == m) { puts("YES"); exit(0); } for (int nxt : gph[now]) { if...
-
[BOJ] 3108 : 로고
3108 : 로고 풀이 사각형을 하나의 노드로 보자. 어떤 두 사각형 a, b가 겹친다면 두 사각형은 연결된 것으로 생각하자. 연결된 사각형들은 연필을 들지 않고 삥삥 돌며 잘 그릴 수 있다. 연필은 연결 요소의 개수 - 1번 들어주면 된다. 단, 시작점인 (0, 0)을 지나는 경우의 예외처리를 잘 해주자. (x1=0, y1=0, x2=0, y2=0)인 경우도 비교해주면 된다. Flood fill로 풀어도 된다. 코드 #include <cstdio> #include <algorithm> #define y1 fu using namespace std; const int n_ = 1000 +...
-
[BOJ] 1414 : 불우이웃돕기
1414 : 불우이웃돕기 풀이 미니멈 스패닝 트리를 쓰자. 크루스칼을 쓰자. 전체 랜선의 합에서 최소로 잇는 랜선의 합을 빼주자. 자잘한 처리가 조금 귀찮은 문제다. 코드 #include <stdio.h> #include <algorithm> #include <vector> using namespace std; struct edg { int x, y, w; edg(int x, int y, int w) :x(x), y(y), w(w) {} bool operator <(edg A)const { return w < A.w; } }; int n, pnt[101]; vector<edg> gph; int find(int u) { if (u == pnt[u]) return...
-
[BOJ] 4195 : 친구 네트워크
4195 : 친구 네트워크 풀이 새로운 친구들이 추가될 때 마다 merge를 해주자! 모든 노드에 대해 해당 원소가 속한 네트워크의 크기를 미리 구해두고 merge 할 때 합쳐주자! 이 문제에서는 map을 쓰면 편하게 구현할 수 있다. unordered_map을 사용하면 map보다 빠르게 구현할 수 있다. 자세한 건 cpp 레퍼런스를 참고하자. 코드 #include <iostream> #include <unordered_map> #include <string> #include <algorithm> using namespace std; const int n_ = 1e5 + 1; int pnt[n_ * 2], cnt[n_ * 2]; int find(int u)...
-
[BOJ] 13306 : 트리
13306 : 트리 풀이 엣지를 제거하면서 union find를 하려면 TLE가 난다. 문제를 거꾸로 생각하자. 원래의 문제는 간선이 모두 이어진 상태에서 하나씩 제거하는 형태이다. 그렇다면 역으로 간선을 다 끊어놓고 쿼리를 뒤에서 부터 돌면 되지 않을까?! 간선을 하나씩 이어주면서 union find를 돌리게 되면 빠르게 답을 구할 수 있다. 발상의 전환이 조금 어려운 문제인 것 같다. 코드 #include <bits/stdc++.h> using namespace std; const int n_ = 2e5 + 3; int n, q; int gph[n_], pnt[n_], q1[n_ * 2],...
-
[BOJ] 1922 : 네트워크 연결
1922 : 네트워크 연결 풀이 계절이 지나가는 하늘에는 가을로 가득 차 있습니다. 코드 #include <stdio.h> #include <vector> #include <algorithm> using namespace std; const int n_ = 1e3 + 1; const int m_ = 1e5 + 1; struct node { int u, v, w; } edg[m_]; int p[n_]; inline int find(int u) { if (u == p[u]) return u; return p[u] = find(p[u]); } void merge(int u, int v) { u = find(u), v = find(v);...
-
[BOJ] 1197 : 최소 스패닝 트리
1197 : 최소 스패닝 트리 풀이 크루스칼을 하자. 코드 #include <stdio.h> #include <vector> #include <algorithm> using namespace std; const int n_ = 1e4 + 1; const int m_ = 1e5 + 1; struct node { int u, v, c; bool operator <(node A)const { return c < A.c; } } edg[m_]; int n, m; int mom[n_]; int find(int u) { if (u == mom[u]) return u; return mom[u] = find(mom[u]); } void merge(int u, int...