-
[BOJ] 11745: King’s Inspection
11745: King’s Inspection 풀이 M <= N+20이므로, 주어지는 그래프는 최대 20개의 간선만 제거하면 트리가 된다. 즉, 트리와 아주 유사하게 생겼다는 뜻이고, 이는 대부분 노드의 in/out degree가 1이라는 뜻이다. indegree 또는 outdegree가 2 이상인 노드를 special node로 두자. special node에서 다른 speical node까지의 경로를 압축하자. in/out degree가 1인 노드들을 모두 압축해서 하나의 간선으로 치는 것이다. 그러면 노드가 많아야 40개인 그래프가 나온다. 이 그래프에서 TSP를 하면 된다. 코드 #include <bits/stdc++.h> using namespace std; typedef long long ll;...
-
[BOJ] 9240 : 로버트 후드
9240 : 로버트 후드 풀이 로테이팅 캘리퍼스 코드 #include<cstdio> #include<algorithm> #include<tuple> #include<vector> #include<cmath> using namespace std; typedef long long ll; typedef pair<int,int> pii; struct POINT{ int x, y; bool operator <(POINT a)const { return x == a.x ? y < a.y : x < a.x; } POINT operator -(POINT a)const { return { x-a.x,y-a.y }; } }; int N; ll sq(int x){ return (ll)x*x; } ll dst(POINT A, POINT B) { return sq(A.x-B.x)+sq(A.y-B.y); } int...
-
[BOJ] 1062 : 가르침
1062 : 가르침 풀이 그냥 완전탐색하면 된다 근데 그냥 하면 시간 초과가 난다 앞뒤에 anta tica를 제거하고 잘 돌려야 한다 코드 #include <bits/stdc++.h> using namespace std; int n, k, dap, a[55]; char s[55]; int main() { scanf("%d %d", &n, &k); for (int i = 0; i < n; i++) { scanf("%s", s); for (int j = 0; s[j]; j++) a[i] |= (1<<(s[j]-'a')); } int x = (1<<0)|(1<<2)|(1<<8)|(1<<13)|(1<<19); for (int i = x; i < (1<<26);...
-
[BOJ] 5820 : 경주
5820 : 경주 풀이 트리에서 분할정복을 하자! linear 배열에서의 분할정복은 중앙을 기준으로 좌우로 쪼개어 내려간다. tree에서의 분할정복도 마찬가지로 중앙을 기준으로 들어가면 된다. 트리에서 중앙은 무엇일까? 트리에 centroid라는 것이 있다. centroid는 어떤 노드를 의미한다. 트리에서 어떤 정점을 제거하면 여러 subtree가 생기게 된다. 이때 생기는 모든 subtree의 크기가 N/2 이하가 되게하는 정점을 의미한다. 다시 말해, centroid는 제거하였을 때 모든 subtree의 크기 <= 노드 수/2가 되도록 하는 정점을 의미한다. 이 문제를 분할정복으로 풀기 전에 아래의 문제를 먼저 분할정복으로...
-
[BOJ] 5820 : 경주
5820 : 경주 풀이 트리에서 분할정복을 하자! linear 배열에서의 분할정복은 중앙을 기준으로 좌우로 쪼개어 내려간다. tree에서의 분할정복도 마찬가지로 중앙을 기준으로 들어가면 된다. 트리에서 중앙은 무엇일까? 트리에 centroid라는 것이 있다. centroid는 어떤 노드를 의미한다. 트리에서 어떤 정점을 제거하면 여러 subtree가 생기게 된다. 이때 생기는 모든 subtree의 크기가 N/2 이하가 되게하는 정점을 의미한다. 다시 말해, centroid는 제거하였을 때 모든 subtree의 크기 <= 노드 수/2가 되도록 하는 정점을 의미한다. 이 문제를 분할정복으로 풀기 전에 아래의 문제를 먼저 분할정복으로...
-
[BOJ] 16000 : 섬
16000 : 섬 풀이 문제를 조금 정리해 보자. 모든 섬 v에 대해, 최외곽 바다로 나가기 위해 반드시 거쳐야 하는 어떤 섬 u가 존재하는가? 섬들간의 어떤 관계에 대해서 묻고 있다. 관계는 항상 그래프로 나타낼 수 있다. 문제의 정의가 그래프스럽게 생겼으니, Flood-fill을 이용해 육지와 바다를 각각 노드로 묶어 그래프로 만들고 생각해보자. 그래프에서 최외곽 바다를 1번 노드로 두고 문제를 다시 생각해 보자. 모든 섬 노드 v에 대해, 1에서 v로 가기 위해 반드시 거쳐야 하는 섬 노드 u가 존재하는가?...
-
[BOJ] 14502 : 연구소
14502 : 연구소 풀이 삼성스럽다. 구현 문제다. 완전탐색 잘 짜주면 된다. 코드 #include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int dx[] = { 0,0,-1,1 }; const int dy[] = { -1,1,0,0 }; int n, m, s, a[11][11], chk[11][11]; vector<pair<int, int> > virus; int dfs(int x, int y) { int ret = 1; chk[x][y] = 1; for (int i = 0; i < 4; i++) { int nx = x+dx[i], ny...
-
[BOJ] 2842 : 집배원 한상덕
2842 : 집배원 한상덕 풀이 parametric search로도 풀릴 것 같은데 나는 투포인터로 풀었다. 높이가 될 수 있는 후보는 1000000개이지만 주어지는 그리드의 크기가 50*50이 최대이므로 많아야 2500개 후보가 있을 수 있다. 주어진 높이들을 정렬한 다음, 투포인터로 구간을 잡아 dfs를 돌려주자. 코드 #include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; const int dx[] = { 0,0,-1,1,-1,-1,1,1 }; const int dy[] = { -1,1,0,0,-1,1,-1,1 }; int n, sx, sy, k, b[55][55], chk[55][55]; char a[55][55]; vector<int>...
-
[BOJ] 2453 : 부서 배치
2453 : 부서 배치 풀이 어떤 두 사람의 친하고 친하지 않고를 나타내는 관계가 있다. 관계는 항상 그래프로 표현할 수 있다. 이 문제에서 주어진 관계들을 그래프로 표현하면, 이 관계들이 여러 개의 Connected Component로 나눠질 수 있다. 부서는 반드시 2개가 존재하니까, 컴포넌트마다 그룹1에 들어가는 사람 수와 그룹2에 들어가는 사람 수를 정할 수 있다. 이를 정하는 과정에서 모순이 발생하면 -1을 출력하고 종료해주면 된다. 여기까지 각 컴포넌트마다 두 그룹에 할당되는 인원 수를 정했다. 이제 한 그룹의 사람들을 부서1에 배치할지,...
-
[BOJ] 16174 : 점프왕 쩰리 (Large)
16174 : 점프왕 쩰리 (Large) 풀이 잘 짜주면 된다. 코드 #include <cstdio> int n, i, j, x, a[66][66] = {1}; int main() { scanf("%d", &n); for (i = 0; i < n; i++) for (j = 0; j < n; j++) { scanf("%d", &x); if (!a[i][j]) continue; if (i+x < n) a[i+x][j] = 1; if (j+x < n) a[i][j+x] = 1; } puts(a[n-1][n-1] ? "HaruHaru" : "Hing"); return 0; } 아무말 백준, 백준 온라인 저지,...
-
[BOJ] 16173 : 점프왕 쩰리 (Small)
16173 : 점프왕 쩰리 (Small) 풀이 잘 짜주면 된다. 코드 #include <cstdio> int n, i, j, x, a[66][66] = {1}; int main() { scanf("%d", &n); for (i = 0; i < n; i++) for (j = 0; j < n; j++) { scanf("%d", &x); if (!a[i][j]) continue; if (i+x < n) a[i+x][j] = 1; if (j+x < n) a[i][j+x] = 1; } puts(a[n-1][n-1] ? "HaruHaru" : "Hing"); return 0; } 아무말 백준, 백준 온라인 저지,...
-
[BOJ] 16169 : 수행 시간
16169 : 수행 시간 풀이 위상정렬 acm craft인가 그 문제랑 똑같은 것 같다. (사실 기억 안 남 ㅎ) 잘 짜주면 된다. 코드 #include <cstdio> #include <vector> #include <algorithm> using namespace std; int n, dap, l[101], t[101], d[101], r[101]; struct edg { int idx, dst; }; vector<edg> gph[101]; void go(int now) { dap = max(dap, r[now]); for (edg nxt : gph[now]) { r[nxt.idx] = max(r[nxt.idx], r[now] + t[nxt.idx] + nxt.dst); if (!(--d[nxt.idx])) go(nxt.idx); } } int...
-
[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] 16167 : A Great Way
16167 : A Great Way 풀이 잘 짜주면 된다. 코드 #include <cstdio> #include <queue> #include <vector> #define fst first #define snd second using namespace std; int n, m; struct abc { int idx, cst; }; vector<abc> gph[101]; pair<int, int> dp[101]; int main() { scanf("%d %d", &n, &m); while (m--) { int a, b, c, d, e; scanf("%d %d %d %d %d", &a, &b, &c, &d, &e); if (e > 10) c += ((e-10)*d); gph[a].push_back({ b,c...
-
[BOJ] 16166 : 서울의 지하철
16166 : 서울의 지하철 풀이 잘 짜주면 된다. 비트마스크 썼다. 코드 #include <cstdio> #include <queue> #include <map> using namespace std; int n, en; struct abc { int idx, hosun, cnt; bool operator <(abc a)const { return cnt > a.cnt; } }; map<pair<int, int>, int> cnt; map<int, int> subway; int main() { scanf("%d", &n); for (int i = 1, k; i <= n; i++) { scanf("%d", &k); for (int j = 0, x; j < k;...
-
[BOJ] 8093 : Credibility of Witnesses
8093 : Credibility of Witnesses 풀이 믿는다의 정의는 재귀적인데, 1. A는 A를 믿는다, 입력으로 주어진 쌍에 있는 사람들도 믿는다. 2. A가 B를 믿는다면, A는 B가 믿는 모든 사람들을 믿는다. 믿지 않는다의 정의도 재귀적인데, 1. A는 입력으로 주어진 쌍에 있는 사람들을 믿지 않는다. 2. A가 B를 믿는다면, A는 B가 믿지 않는 모든 사람들을 믿지 않는다. 그래서 모든 A에 대해서, A가 믿으면서 믿지 않는 B가 존재하는지 찾는 문제입니다. - said koosaga dfs를 n번 돌려서 O(n^2) 정도에 풀...
-
[BOJ] 15368 : Birokracija
15368 : Birokracija 풀이 트리에 존재하는 모든 노드에 대해, 각각의 노드에서 루트까지의 거리를 더하는 문제이다. 음… 그냥 짜면 된다. 코드 #include <cstdio> int n, par[200002], cnt[200002]; long long ans[200002]; int main() { scanf("%d", &n); for (int i = 2; i <= n; i++) scanf("%d", &par[i]); for (int i = n; i >= 1; i--) { ans[par[i]] += ++ans[i] + ++cnt[i]; cnt[par[i]] += cnt[i]; } for (int i = 1; i <= n; i++) printf("%lld ",...
-
[BOJ] 15267 : Justified Jungle
15267 : Justified Jungle 풀이 트리를 일단 나눴다면, 나눠진 후의 모든 컴포넌트에 속한 노드 수는 같아야 한다. 즉, 노드는 n의 약수로만 나눠질 수 있다. 100만 이하 자연수의 약수 개수가 최대 240개니까 O(240*n) 잘 커팅하면 6초 안에 될 거 같은데 안 됨 흠… 아무튼 나이브하게는 안 돌아가므로 조금 더 생각을 해야한다. 트리를 돌며 gcd(서브트리의 노드 개수, n)의 개수를 세어주자. 음… 그냥 코드를 보는 게 더 빠르겠다. 코드 #include <cstdio> #include <vector> using namespace std; int n,...
-
[BOJ] 15264 : Gambling Guide
15264 : Gambling Guide 풀이 1에서 N으로 가는 기댓값을 구해야 하는데 기댓값을 구할 수가 없다! 그러니까 N에서부터 1로, 거꾸로 가면서 구해주자. 코드 #include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; const int n_ = 3e5+3; int n, m, sdeg[n_]; double dp[n_], sdp[n_]; struct abc { int idx; double val; bool operator <(abc a)const { return val > a.val; } }; priority_queue<abc> pq; vector<int> gph[n_]; int main() { scanf("%d %d", &n, &m); for...
-
[BOJ] 11581 : 구호물자
11581 : 구호물자 풀이 공.강.시.러 코드 #include <cstdio> #include <cstdlib> #include <vector> using namespace std; int n, m, chk[102]; vector<int> gph[102]; void dfs(int now) { if (chk[now] == 1) { puts("CYCLE"); exit(0); } chk[now] = 1; for (int nxt : gph[now]) { if (chk[nxt] != 2) dfs(nxt); } chk[now] = 2; } int main() { scanf("%d", &n); for (int i = 1, u; i < n; i++) { scanf("%d", &m); while (m--) { scanf("%d", &u);...
-
[BOJ] 2056 : 작업
2056 : 작업 풀이 간단한 다이나믹으로 풀어도 되고 위상정렬스럽게 풀어도 된다 코드 #include <cstdio> #include <algorithm> using namespace std; int n, res, dp[10001]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { int c, m, x; scanf("%d %d", &c, &m); for (int j = 0; j < m; j++) { scanf("%d", &x); dp[i] = max(dp[i], dp[x]); } res = max(res, dp[i] += c); } printf("%d", res); return 0; }...
-
[BOJ] 15686 : 치킨 배달
15686 : 치킨 배달 풀이 삼성 인사 담당자님, 모든 경우의 수를 다 돌려보면 된답니다. 코드 #include <cstdio> #include <vector> #include <algorithm> using namespace std; int n, m, x, chk[14]; vector<pair<int, int> > a, b; int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { scanf("%d", &x); if (x == 1) a.push_back({ i,j }); if (x == 2) b.push_back({...
-
[BOJ] 2234 : 성곽
2234 : 성곽 풀이 안 돼요 더는 못해요 그대 없이 사는 일 나 때문에 그대 망가진다며 이별을 원한 건 나인데 코드 #include <cstdio> const int dx[] = { 0,-1,0,1 }; const int dy[] = { -1,0,1,0 }; int n, m, a[55][55], c[55][55], cnt[55*55]; int dfs(int x, int y, int num) { int ret = 1; c[x][y] = num; for (int i = 0; i < 4; i++) { int nx = x+dx[i], ny = y+dy[i];...
-
[BOJ] 5214 : 환승
5214 : 환승 풀이 이번 역은 욱제 욱제 역입니다. 수찬이나 사과역으로 갈아타실 고객께서는 이번 역에서 내리시기 바랍니다. 코드 #include <stdio.h> #include <vector> #include <algorithm> #include <queue> using namespace std; const int n_ = 1e5 + 1e3 + 1; int n, k, m, a, i, j, chk[n_]; queue<int> que; vector<int> gph[n_]; int main() { scanf("%d %d %d", &n, &k, &m); for (i = n + 1; i <= n + m; i++) { for (j =...
-
[BOJ] 1389 : 케빈 베이컨의 6단계 법칙
1389 : 케빈 베이컨의 6단계 법칙 풀이 돌리고 돌리고 돌리고~ 코드 #include <cstdio> #include <cstring> #include <vector> #include <queue> using namespace std; int n, m, dst[5005]; vector<int> gph[5005]; int bfs(int start) { int ret = 0; queue<int> que; memset(dst, 0, sizeof(dst)); que.push(start); while (!que.empty()) { int now = que.front(); que.pop(); ret += dst[now]; for (int nxt : gph[now]) { if (dst[nxt]) continue; dst[nxt] = dst[now] + 1; que.push(nxt); } } return ret; } int main()...
-
[BOJ] 10451 : 순열 사이클
10451 : 순열 사이클 풀이 . 코드 #include <iostream> #include <vector> #include <algorithm> #include <cstring> using namespace std; int t, n; vector<int> a[1001]; int ans, chk[1001]; void dfs(int now) { chk[now] = 1; for (int i = 0; i < a[now].size(); i++) if (chk[a[now][i]] != 1) dfs(a[now][i]); } int main() { cin >> t; while (t--) { cin >> n; for (int i = 1; i <= n; i++) { int v; cin >> v;...
-
[BOJ] 7562 : 나이트의 이동
7562 : 나이트의 이동 풀이 . 코드 #include <cstdio> #include <cstring> #include <queue> using namespace std; typedef pair<int, int> pii; const int dx[] = { 1,2,2,1,-1,-2,-2,-1 }; const int dy[] = { -2,-1,1,2,2,1,-1,-2 }; int n, x, y, a, b, dst[303][303]; queue<pii> que; int main() { int tc; for (scanf("%d", &tc); tc; tc--) { scanf("%d %d %d %d %d", &n, &x, &y, &a, &b); que.push({ x,y }); dst[x][y] = 1; while (!que.empty()) { pii now...
-
[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] 6118 : 숨바꼭질
6118 : 숨바꼭질 풀이 최단경로 가즈아~~~ 코드 #include <cstdio> #include <queue> #include <vector> #include <algorithm> using namespace std; const int n_ = 20000 + 2; int n, m, a, b, c, dst[n_]; vector<int> gph[n_]; int main() { scanf("%d %d", &n, &m); for (int i = 0, u, v; i < m; i++) { scanf("%d %d", &u, &v); gph[u].push_back(v); gph[v].push_back(u); } queue<int> que; que.push(1); while (!que.empty()) { int now = que.front(); que.pop(); for (int nxt :...
-
[BOJ] 15559 : 내 선물을 받아줘
15559 : 내 선물을 받아줘 풀이 boj에 내가 나왔으면 정말 좋겠네~ 정말 좋겠네~~~~ 코드 #include <iostream> using namespace std; int n, m, i, j, ans, cnt = 1, vst[1001][1001]; char a[1001][1001]; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> n >> m; for (i = 0; i < n; i++) cin >> a[i]; for (i = 0; i < n; i++) for (j = 0; j < m; j++) { if (vst[i][j]) continue; int y =...
-
[BOJ] 12784 : 인하니카 공화국
12784 : 인하니카 공화국 풀이 루트부터 내려가서 자식들을 끊는 게 좋을지 부모를 끊는 게 좋을지 봐보자. 코드 #include <cstdio> #include <vector> using namespace std; struct edg { int idx, dst; }; vector<edg> gph[1001]; int dfs(int prv, int now, int dst) { int ret = 0; for (edg nxt : gph[now]) if (prv != nxt.idx) ret += dfs(now, nxt.idx, nxt.dst); if (!ret) ret = dst; return ret < dst ? ret : dst; } int main()...
-
[BOJ] 1520 : 내리막 길
1520 : 내리막 길 풀이 메모이제이션 하면서 탐색해주자!! 코드 #include <stdio.h> const int dx[] = { 0,1,0,-1 }; const int dy[] = { 1,0,-1,0 }; int n, m, a[505][505], d[505][505]; int dfs(int x, int y) { if (x == n && y == m) return 1; if (~d[x][y]) return d[x][y]; d[x][y] = 0; for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if...
-
[BOJ] 2668 : 숫자고르기
2668 : 숫자고르기 풀이 사이클을 찾아주면 된다! 우아하게 코드를 작성해보자. 코드 #include <stdio.h> int n, cnt, CNT[101], a[101]; int gogo(int now, int start) { for (int i = 1; i <= n; i++) { now = a[now]; if (now == start) return (cnt++, CNT[now]++); } } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", a + i); for (int i = 1; i <= n; i++) gogo(i, i);...
-
[BOJ] 1991 : 트리 순회
1991 : 트리 순회 풀이 아 퇴사하고싶다 코드 #include <stdio.h> #define p(c) putchar(c); int n, i; char a, b, c, t[99][2]; void f(int x) { if (i == 0) p(x); if (t[x][0] != '.') f(t[x][0]); if (i == 1) p(x); if (t[x][1] != '.') f(t[x][1]); if (i == 2) p(x); } int main() { scanf("%d", &n); for (i = 0; i < n; i++) { scanf(" %c %c %c", &a, &b, &c); t[a][0] = b,...
-
[BOJ] 6603 : 로또
6603 : 로또 풀이 그댈 그린 밤들이 내게 욕심이란 걸 맘 아프게 알아 나를 택한 운명이 행여 그댈 맴돌아 붙잡지 못하게 이제 그대 곁에서 떠나가 코드 #include <stdio.h> int k, s[51], a[7]; void dfs(int len, int cnt) { if (cnt == 6) { for (int i = 1; i <= 6; i++) printf("%d ", a[i]); puts(""); return; } if (len >= k) return; a[cnt + 1] = s[len + 1]; dfs(len + 1, cnt +...
-
[BOJ] 1182 : 부분집합의 합
1182 : 부분집합의 합 풀이 완전탐색! dfs로 짜도 되고 n이 작으니까 비트마스킹 해도 된다. 코드 #include <stdio.h> int n, s, ans, a[21]; int main() { scanf("%d %d", &n, &s); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int i = 1; i < (1 << n); i++) { int sum = 0; for (int j = 0; j < n; j++) if (i & (1 << j)) sum += a[j]; ans...
-
[BOJ] 11725 : 트리의 부모 찾기
11725 : 트리의 부모 찾기 풀이 별 하나에 추억과 별 하나에 사랑과 별 하나에 쓸쓸함과 별 하나에 동경(憧憬)과 별 하나에 시와 별 하나에 어머니, 어머니 코드 #include <stdio.h> #include <vector> using namespace std; int n, pnt[100001]; vector<int> gph[100001]; void dfs(int now) { for (int nxt : gph[now]) if (pnt[now] ^ nxt) pnt[nxt] = now, dfs(nxt); } int main() { scanf("%d", &n); for (int i = 0, u, v; i < n - 1; i++) {...
-
[BOJ] 1967 : 트리의 지름
1967 : 트리의 지름 풀이 트리에서 임의의 노드 ㄱ을 고른 뒤 ㄱ에서 가장 먼 노드 ㄴ을 찾고 ㄴ에서 가장 먼 노드 ㄷ을 찾으면 ㄴ과 ㄷ이 트리의 지름이 된다 (!) 코드 #include <cstdio> #include <vector> #include <algorithm> using namespace std; const int n_ = 1e4 + 4; struct edg { int idx, dst; }; int n, abc, sum; vector<edg> gph[n_]; void dfs(int prv, int now, int dst) { if (sum < dst) sum = dst, abc...
-
[BOJ] 1693 : 트리 색칠하기
1693 : 트리 색칠하기 풀이 http://codersbrunch.blogspot.kr/2017/07/1693.html 읽고 구현한 코드입니다. 코드 #include <stdio.h> #include <vector> #include <algorithm> using namespace std; const int n_ = 1e5 + 5; int n, dp[n_][18]; vector<int> gph[n_]; void dfs(int prv, int now) { dp[now][0] = 2e9; for (int col = 1; col <= 17; col++) dp[now][col] += col; for (int nxt : gph[now]) { if (nxt == prv) continue; dfs(now, nxt); int fst = 0, snd = 0; for (int col...
-
[BOJ] 11724 : 연결 요소의 개수
11724 : 연결 요소의 개수 풀이 느낌있게 깊이우선탐색 코드 #include <iostream> #include <vector> using namespace std; int n, m, ans, vst[1001]; vector<int> gph[1001]; void dfs(int now) { vst[now] = 1; for (int nxt : gph[now]) if (!vst[nxt]) dfs(nxt); } int main() { ios_base::sync_with_stdio(0);cin.tie(0); cin >> n >> m; for (int i = 0, u, v; i < m; i++) { cin >> u >> v; gph[u].push_back(v), gph[v].push_back(u); } for (int i = 1; i <=...
-
[BOJ] 1005 : ACM Craft
1005 : ACM Craft 풀이 위상딱 위상딱 신나는 노래 나도 한 번 불러본다~ 코드 #include <iostream> #include <string.h> #include <vector> using namespace std; const int n_ = 1e3 + 3; int req[n_], dst[n_], idg[n_], ans[n_]; vector<int> gph[n_]; void dfs(int now) { idg[now]--; for (int nxt : gph[now]) { ans[nxt] = max(ans[nxt], ans[now] + req[nxt]); if (!(--idg[nxt])) dfs(nxt); } } int main() { ios_base::sync_with_stdio(0);cin.tie(0); int tc; cin >> tc; while (tc--) { int n, k, w;...
-
[BOJ] 2468 : 안전 영역
2468 : 안전 영역 풀이 DFS를 멋있게 폼나게 오지게 간지나게 돌려보자. 코드 #include <stdio.h> #include <string.h> const int dx[] = { 0,0,1,-1 }; const int dy[] = { 1,-1,0,0 }; int n, w, cnt, ans, mx, a[102][102], b[102][102]; inline int max(int a, int b) { return a > b ? a : b; } void dfs(int x, int y) { b[x][y] = 0; for (int i = 0; i < 4; i++) { int nx...
-
[BOJ] 13460 : 째로탈출 2
13460 : 째로탈출 2 풀이 늘 그랬었어 넌 참 예뻤어 말 할 때마다 웃는 눈도 내가 아니어도 누군가 사랑해 줄 사람 많을 거야 코드 #include <stdio.h> #include <queue> using namespace std; const int dx[] = { -1,0,1,0 }; const int dy[] = { 0,-1,0,1 }; struct ABC { int cnt, rx, ry, bx, by; }; queue<ABC> que; int n, m, rx, ry, bx, by; bool chk[11][11][11][11]; char toy[12][12]; int main() { scanf("%d %d\n", &n, &m);...
-
[BOJ] 14888 : 연산자 끼워넣기
14888 : 연산자 끼워넣기 풀이 완전탐색 완전탐색 신나는 노래~ 코드 #include <stdio.h> int n, i, mn = 2e9, mx = -2e9, a[11], op[4]; void dfs(int c, int v) { if (c == n) { mn = mn < v ? mn : v; mx = mx > v ? mx : v; return; } if (op[0]) --op[0], dfs(c + 1, v + a[c]), ++op[0]; if (op[1]) --op[1], dfs(c + 1, v - a[c]), ++op[1]; if...
-
[BOJ] 1987 : 알파벳
1987 : 알파벳 풀이 마음도 한자리 못 앉아 있는 마음일 때, 친구의 서러운 사랑 이야기를 가을 햇볕으로나 동무 삼아 따라가면, 어느새 등성이에 이르러 눈물나고나. 코드 #include <cstdio> const int dx[] = { 1,-1,0,0 }, dy[] = { 0,0,1,-1 }; int n, m, k, ch[99]; char s[22][22]; void dfs(int x, int y, int c) { if (k < c) k = c; if (k > 25) return; ch[s[x][y]] = 1; for (int i = 0; i...
-
[BOJ] 2580 : 스도쿠
2580 : 스도쿠 풀이 태양을 의논하는 거룩한 이야기는 항상 태양을 등진 곳에서만 비롯하였다. 코드 #include <stdio.h> #include <stdlib.h> #include <vector> using namespace std; struct ABC { int x, y, z; }; int a[9][9], x[9], y[9], z[9]; vector<ABC> p; void dfs(int now) { if (now == p.size()) { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) printf("%d ", a[i][j]); puts(""); } exit(0); } int nx...
-
[BOJ] 2458 : 키 순서
2458 : 키 순서 풀이 모든 노드에서 dfs를 정방향으로 한 번, 역방향으로 한 번 돌려주자! 정방향은 나보다 큰 친구들, 역방향은 나보다 큰 친구들의 개수(?)이다. 이 둘을 합한 값이 나를 제외한 n-1명과 같은지 알아보자! 코드 #include <bits/stdc++.h> using namespace std; int n, m, t, vst[2][501]; vector<int> gph[2][501]; int dfs(int now) { int ret = 1; vst[t][now] = 1; for (int nxt : gph[t][now]) if (!vst[t][nxt]) ret += dfs(nxt); return ret; } int main() { int u,...
-
[BOJ] 2583 : 영역 구하기
2583 : 영역 구하기 풀이 직사각형 영역에 체크를 해놓고 모든 칸을 돌면서 bfs나 dfs나 아무거나 돌려주면 된다. 입력이 좀 짜증난다 (…) 코드 #include <stdio.h> #include <vector> #include <algorithm> using namespace std; const int dx[] = { -1,0,1,0 }; const int dy[] = { 0,-1,0,1 }; int n, m, k, cnt, a[111][111]; vector<int> v; int dfs(int x, int y) { int ret = 1; a[x][y] = 1; for (int i = 0; i < 4; i++)...
-
[BOJ] 9466 : 텀 프로젝트
9466 : 텀 프로젝트E 풀이 위상정렬을 하자! 코드 #include <stdio.h> #include <memory.h> const int n_ = 100000 + 1; int ans, a[n_], idg[n_]; bool chk[n_]; void dfs(int n) { chk[n] = true; ++ans, --idg[a[n]]; if (!chk[a[n]] && !idg[a[n]]) dfs(a[n]); } int main() { int t, n, i, j; scanf("%d", &t); for (i = 1; i <= t; ++i) { ans = 0; scanf("%d", &n); memset(chk, 0, sizeof(chk)); memset(idg, 0, sizeof(idg)); for (j = 1; j...
-
[BOJ] 13023 : ABCDE
13023 : ABCDE 풀이 A-B-C-D-E 관계의 5명이 있는지 구하는 문제였다. dfs를 돌려주자. 코드 #include <stdio.h> #include <memory.h> #include <algorithm> #include <vector> using namespace std; const int n_ = 2000 + 1; bool ans, chk[n_]; int n, m; vector<int> v[n_]; void dfs(int now, int cnt) { if (cnt == 5) { ans = true; return; } chk[now] = true; for (int next : v[now]) { if (!chk[next]) dfs(next, cnt + 1); if (ans) return; } chk[now]...
-
[BOJ] 2150 : Strongly Connected Component
2150 : Strongly Connected Component 풀이 scc를 구현하자! 다른 블로그에 좋은 scc 설명이 많으니까 나는 구현만 해야겠다 원래 stl stack 써서 짰는데 메모리 많이 먹길래 기분 나빠서(?) 배열로 바꿨다. 처음 코드가 타잔, 다음 코드가 코사라주이다. 코드 타잔 #include <stdio.h> #include <algorithm> #include <vector> using namespace std; typedef vector<int> vi; const int v_ = 1e4 + 1; int v, e, cnt, pos, scc[v_], chk[v_], stk[v_]; vi gph[v_]; vector<vi> res; int dfs(int now) { chk[now] = ++cnt;...
-
[BOJ] 1412 : 일방통행
1412 : 일방통행 풀이 단방향과 양방향 간선이 섞여있는 그래프가 주어진다. 양방향 간선들을 모두 단방향 간선으로 바꾸었을 때, 사이클이 있는지 찾는 문제이다. 일단 솔루션부터 이야기하면, 양방향 간선들은 제껴두고 단방향 간선들만으로 사이클을 이루는지 검사하면 된다. 증명은 음… 증명이라고 하긴 뭐하지만 1->2, 1->3, 2->4, 3->4, 1-4, 2-3의 그래프를 가정하자. 단방향 간선들로 위상정렬을 하면, 1 2 3 4가 나올 것이다. 그리고 1-4와 2-3은 위상정렬 순서에 따라 단방향 간선으로 바꾸어주면 된다. (1->4, 2->3) 코드 #include <stdio.h> int n, vst[101], flag;...
-
[BOJ] 2667 : 단지번호붙이기
2667 : 단지번호붙이기 풀이 dfs를 돌려보자! 맵을 한 바퀴 쭉 돌면서, 아직 탐색하지 않은 단지를 만나면 dfs를 돌리자! 새로운 단지를 만날 때마다 단지 번호도 하나씩 늘려주자! 코드 #include <cstdio> #include <algorithm> const int dx[] = { 0,0,-1,1 }; const int dy[] = { -1,1,0,0 }; int n, k, cnt[26 * 26]; char arr[26][26]; void dfs(int x, int y) { arr[x][y] = '0', cnt[k]++; for (int i = 0; i < 4; i++) { int nx...
-
[BOJ] 11438 : LCA2
11438 : LCA2 풀이 이번엔 naive가 아닌 풀이! 이전의 naive한 풀이에서, 우리는 최악의 경우에 n번의 노드를 하나씩하나씩 올라가야했다. 하지만 이를 log(n)으로 줄일 수 있다! pnt[i][j] = i번 노드의 2^j번째 조상으로 두고 풀면 된다. 트리의 깊이를 구할 때 2^j번째 조상을 구해두자. tmp = anc[i][j-1]일 때, anc[i][j]는 anc[tmp][j-1]과 같다. 즉, i의 2^j번째 조상은 2^(j-1)번째 조상의 2^(j-1)번째 조상과 같다는 의미이다. i의 2^3=8번째 조상은 2^2=4번째 조상의 2^2=4번째 조상과 같다. naive한 코드에서 2^j를 도는 동작만 추가해주면 어렵지 않게(?) 훨씬 빠르게(!)...
-
[BOJ] 11437 : LCA
11437 : LCA 풀이 naive한 풀이! dfs 먼저 돌려서 각 노드마다 깊이를 구해준 뒤, u, v 두 노드 중 더 큰 노드의 깊이를 끌어 올려준 다음에 두 노드에서 동시에 하나씩 올라가며 같은 노드에서 마주칠 때 까지 올려주면 된다. 코드 #include <stdio.h> #include <algorithm> #include <vector> using namespace std; const int n_ = 5e4 + 3; int n, m; int dph[n_], pnt[n_]; vector<int> gph[n_]; inline void dfs(int now, int cnt) { dph[now] = cnt++; for (auto...
-
[codeforces] #403 div1 A (div2 C)
#403 div1 A. Andryusha and Colored Balloons 풀이 이전 노드의 색, 이번 노드의 색에 대한 정보를 가지고 dfs를 돌리면 해결할 수 있다. 추가로, (가장 큰 차수)+1만 가지고 최소로 색칠할 수 있다. 코드 #include <bits/stdc++.h> using namespace std; const int n_ = 2e5 + 10; int n, ans, col[n_]; vector<int> gph[n_]; void dfs(int prv, int cur) { int i = 1; for (auto nxt : gph[cur]) { if (col[nxt]) continue; while (col[prv] == i || col[cur]...
-
[BOJ] 1937 : 욕심쟁이 판다
1937 : 욕심쟁이 판다 풀이 dfs를 돌리자! 코드 #include <stdio.h> const int dx[] = { 0,0,-1,1 }; const int dy[] = { -1,1,0,0 }; const int n_ = 500 + 5; int n, a[n_][n_], dp[n_][n_]; inline int max(int a, int b) { return a > b ? a : b; } int dfs(int x, int y) { if (dp[x][y]) return dp[x][y]; dp[x][y] = 1; for (int i = 0; i < 4; i++) { int...
-
[BOJ] 1012 : 유기농 배추
1012 : 유기농 배추 풀이 DFS를 돌리자. 코드 #include <stdio.h> #include <memory.h> const int dx[] = { 0,0,-1,1 }; const int dy[] = { -1,1,0,0 }; int tc, n, m, k, i, j, x, y, ans; bool farm[52][52]; void dfs(int x, int y) { farm[x][y] = 0; for (int i = 0; i < 4; i++) if (farm[x + dx[i]][y + dy[i]]) dfs(x + dx[i], y + dy[i]); } int main() { scanf("%d", &tc); while...
-
[BOJ] 2623 : 음악프로그램
2623 : 음악프로그램 풀이 위상정렬을 하면 된다! 코드 #include <iostream> #include <vector> using namespace std; const int n_ = 1000 + 3; int n, m, idg[n_]; vector<int> ans; vector<int> edg[n_]; void dfs(int now) { idg[now] = -1; ans.push_back(now); for (auto nxt : edg[now]) if (!(--idg[nxt])) dfs(nxt); } int main() { int i, j, a, b, c; cin >> n >> m; while (m--) { cin >> a >> b; while (--a) { cin >> c;...
-
[BOJ] 4963 : 섬의 개수
4963 : 섬의 개수 풀이 dfs를 돌리자 코드 #include <stdio.h> const int dx[] = { 0,0,1,-1,1,1,-1,-1 }; const int dy[] = { -1,1,0,0,1,-1,-1,1 }; int n, m; int a[51][51]; void dfs(int x, int y) { a[x][y] = 0; for (int i = 0; i < 8; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= m)...
-
[BOJ] 2661 : 좋은 수열
2661 : 좋은 수열 풀이 재귀로 작은 숫자부터 들어가면서 문자를 비교해주자 코드 #include <bits/stdc++.h> using namespace std; int n, a[88]; void gogo(int cnt) { for (int i = 1; i <= cnt / 2; i++) { if (equal(a + cnt - i, a + cnt, a + cnt - i - i)) return; } if (cnt == n) { for (int i = 0; i < n; i++) printf("%d", a[i]); exit(0); } for (int i...
-
[BOJ] 3683 : 고양이와 개
3683 : 고양이와 개 풀이 이분그래프에서의 Maximum Independent Set(최대 독립 집합)을 구하는 문제이다. size(maximum independent set) + size(maximum matching) = size(vertices) 이거를 기억하자. 문제를 그래프화 시켜보자. 시청자를 노드, 의견 충돌을 엣지라고 두자. 시청자들은 cat을 남기고 dog를 떨어트리거나, dog를 남기고 cat을 떨어트리는 집단으로 나눌 수 있다. 그렇게 나눠서 엣지를 연결하면 이분그래프가 된다! 그런데 maximum independent set을 구하긴 힘드니까 위의 식을 정리해서, size(vertices) - size(maximum matching)를 구하자! 결국 이분매칭 문제가 되었다. 코드 #include <bits/stdc++.h> using namespace std;...
-
[BOJ] 12946 : 육각 보드
12946 : 육각보드 풀이 잘 생각해보면 보드는 최대 3개의 색으로 칠할 수 있다. 여기를 참고. 0과 1인 경우는 따로 처리해주고 DFS로 돌면서 이분그래프이면 답은 2, 아니면 3이다. 코드 #include <bits/stdc++.h> using namespace std; const int dx[6] = { -1,-1,0,0,1,1 }; const int dy[6] = { 0,1,-1,1,-1,0 }; int n, ans, col[51][51]; char e[51][51]; void dfs(int x, int y, int c) { col[x][y] = c; ans = max(ans, 1); for (int i = 0; i <...
-
[BOJ] 12101 : 1, 2, 3 더하기 2
12101 : 1, 2, 3 더하기 2 풀이 지금 생각해보니 스택으로 짜도 될 것 같다. 코드 #include <stdio.h> #include <vector> using namespace std; int N, K; int res; vector<int> ans; bool go(int sum, int cnt) { if (sum == N) ++res; if (res == K) return true; for (int i = 1; i <= 3; ++i) { if (sum + i <= N) { if (go(sum + i, cnt + 1)) { ans.push_back(i); return true;...
-
[BOJ] 13209 : 검역소
13209 : 검역소 풀이 이분 탐색(log n)을 돌면서 그리디(n)을 돌리면 O(n log n)에 해결할 수 있다. priority_queue를 사용하기 전에 벡터를 써서 정렬하는 생각을 먼저 했지만 코딩이 괴랄해져서 포기하고 우선순위큐를 사용했다. 바이너리 서치의 mid를 비축할 백신의 수라고 두고, 주어진 검역소만으로 mid를 충족시킬 수 있는지 그리디로 풀면 된다. 싸이클이 없고 임의의 a에서 b로 가는 경로가 단 하나이기 때문에 그리디로 풀 수 있다! dfs의 리턴값은 항상 mid를 넘지 않음이 보장된다. 물론 인구수가 mid를 넘을 수는 있다. 그건 left...
-
[BOJ] 2611 : 자동차경주
2611 : 자동차경주 풀이 처음 문제를 보자마자 다익스트라 풀이를 떠올렸는데 문제를 다시 읽어보니 1번 노드를 거치지 않고 다시 원래 노드로 돌아 올 수 없다 이거 싸이클도 없고 완전 DAG잖아? 위상정렬해서 풀려고 했는데 생각해보니 dp로 풀 수 있잖아? 코드 #include <stdio.h> #include <vector> using namespace std; const int n_ = 1000 + 1; int n, m, dp[n_], route[n_]; vector<pair<int, int> > gph[n_]; int dfs(int now) { if (!dp[now] && now != 1) for (auto nxt :...
-
[BOJ] 1260 : DFS와 BFS
1260 : DFS와 BFS 풀이 bfs를 돌리자! dfs도 돌리자! 코드 #include <cstdio> #include <queue> #include <cstring> using namespace std; int n, m, v, chk[1001], gph[1001][1001]; void dfs(int now) { chk[now] = 1; printf("%d ", now); for (int i = 1; i <= n; i++) if (!chk[i] && gph[now][i]) dfs(i); } void bfs(int now) { queue<int> que; que.push(now); chk[now] = 1; while (!que.empty()) { int now = que.front(); que.pop(); printf("%d ", now); for (int i =...
-
[BOJ] 1948 : 임계경로
1948 : 임계경로 풀이 문제를 다르게 생각해보자. 마지막에 도착하는 사람까지 도착을 하는 시간 이라는 문장은 결국 가장 먼 길을 선택하는 사람, 즉 최장 거리를 의미한다. 따라서 이 문제는 최장 거리와, 최장 경로들에 포함되는 모든 간선의 개수를 카운팅해서 출력하면 된다! 풀다보니까 이게 개수를 카운팅 할 때 뒤에서 부터 돌아야 할 것 같은데… 인접행렬이 아니라 백터를 써서 짰단 말이야 코드를 다시 짜긴 귀찮고 그래서 dp 배열을 아예 백트랙킹? 그런 느낌으로 구했다. get_max_len() 함수를 보면 일단 카운팅하기 전에...