-
[KATTIS] Grid MST
Grid MST 풀이 문제가 좋아서 가져왔다. 1000*1000 크기의 격자에 N(100,000)개의 점이 있다. 모든 점쌍 사이에 가중치가 w(두 점 사이의 맨하탄 거리)인 간선이 있다. 이 때, 이 그래프에서 만들 수 있는 MST의 최소 가중치 합은? 정점 10만개짜리 완전그래프이기에, 나이브한 방법으로 문제를 풀기에는 꽤나 어려워 보인다. MST를 구성하는 상황을 생각해 보자. a-b와 b-c가 있고, b를 지나는 것이 최단인 a-c가 존재한다면, a-c를 MST에 포함시키는 것 보다 더 나은 방법(a-b, b-c)이 항상 존재한다. 격자의 크기가 최대 1000*1000임에 주목하자. 우리는...
-
[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] 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] 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] 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] 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] 6191 : Cows on Skates
6191 : Cows on Skates 풀이 (1,1)~(r,c)까지의 경로를 찾아주자! 왜 이게 usaco gold 문제인지는 모르겠다 ㅋㅋㅋ 코드 #include <stdio.h> #include <algorithm> #include <queue> using namespace std; const int dx[] = { 0,0,-1,1 }, dy[] = { -1,1,0,0 }; struct ABC { int x, y; }; int n, m; char a[123][123]; ABC chk[123][123]; queue<ABC> que; void f(int x, int y) { if (x != 1 || y != 1) f(chk[x][y].x, chk[x][y].y); printf("%d %d\n", x, y); }...
-
[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] 7576 : 토마토
7576 : 토마토 풀이 bfs를 돌리자 코드 #include <cstdio> #include <queue> #include <algorithm> using namespace std; const int dx[] = { 0,0,-1,1 }; const int dy[] = { -1,1,0,0 }; int n, m, a[1003][1003]; queue<pair<int, int> > que; int main() { scanf("%d %d", &m, &n); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%d", &a[i][j]); if (a[i][j] == 1) que.push({ i,j }); }...
-
[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] 12869 : 뮤탈리스크
12869 : 뮤탈리스크 풀이 음 원래 dp로 풀려고 했는데 그냥 bfs로 풀었다. dp[i][j][k] = 1번, 2번, 3번 scv의 체력으로 두고 풀어도 된다. 코드 #include <bits/stdc++.h> using namespace std; int N, A[3], ans = 987654321; const int D[6][3] = { {1,3,9},{1,9,3},{3,1,9},{3,9,1},{9,1,3},{9,3,1} }; bool chk[61][61][61][20]; struct ABC { int a, b, c, x; ABC() {} ABC(int a, int b, int c, int x) : a(a), b(b), c(c), x(x) {} }; int main() { scanf("%d", &N); for (int...
-
[BOJ] 14442 : 벽 부수고 이동하기 2
14442 : 벽 부수고 이동하기 2 풀이 dp[x][y][부순 벽의 수 k]로 두고 풀자. BFS를 돌리면 된다. 하지만 중요한 건 문제 풀이가 아니고(!) memset이 byte 단위로 초기화하기 때문에 memset(dp, 1, sizeof(dp)) 하면 dp의 각 방이 0x01010101 이렇게 채워진다는 걸 배웠다. 그래서 987654321이나 1e9처럼 int_max 절반으로 초기화하고 싶으면 0x3f로 초기화하면 된다. 음… 어셈 공부하다 말았는데 계속 해야하나? ㅠㅠ 코드 #include <stdio.h> #include <queue> #include <algorithm> using namespace std; const int dx[] = { 0,1,-1,0 }; const int...
-
[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 =...