목록그래프 (36)
정화 코딩
[C++] 포항항 (백준 23817번)
https://www.acmicpc.net/problem/23817 이 문제 풀 때 고수들이 옆에 있었어서 그들이 걍 다 해줌. 저는 풀이를 듣고 음 그렇구나. 천재다. 구현해볼게. 했음다. 첫번째 풀이. vst 배열: 현재 위치 (i, j) + 어느어느식당 방문했는지 (길이가 20인 비트스트링) 길이가 20인 비트스트링 → 2^20 하면 너무 큼 → 근데 어차피 최대가 5개 켜지는 거임 → 2^20 중에 안 쓰는 게 너무 많음 (어떤 걸 안 쓰는지 모름) → map 이용 vector>> → 최단 거리를 두번째 int에 저장하는 셈 vector>> (= vector>>) → 방문 했는지 안 했는지를 bool에 저장하는 셈 근데 이렇게 하면 터짐... 두번째 풀이.모든 식당과 식당 (+시작점) 사이의 거..
[C++] 숨바꼭질 2 (백준 12851번)
https://www.acmicpc.net/problem/12851 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, k; cin >> n >> k; int maxs = 100001; vector vst = vector(maxs, false); int timea = 0; int cnt = 0; queue> q; q.emplace(n, 0); vst[n] = true; while (!q.empty()) { int cur = q.front().first; int t..
[C++] 최소비용 구하기 2 (백준 11779번)
https://www.acmicpc.net/problem/11779 #include #include #include using namespace std;int MAX_SIZE = 1000000000;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector>> g(n + 1); vector dst(n + 1, MAX_SIZE); vector route(n + 1); for (int i = 0; i > a >> b >> c; g[a].emplace_back(b, c); } int s, e; cin >> s >> ..
8회차 - BFS, DFS DFS와 BFShttps://www.acmicpc.net/problem/1260DFS, BFS 기본 문제입니다. 각 방식을 구현하고 방문하는 노드를 출력하면 됩니다.주의할 점 1. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 택해야 한다는 것입니다. 따라서 저는 입력을 받은 후 각 정점에 연결된 정점들에 대해 정렬을 한 번씩 진행해주었습니다.주의할 점 2. 탐색 여부 배열을 공유한다면 초기화가 필요합니다.#include #include #include #include using namespace std;vector vst;vector> g;void dfs(int cur) { vst[cur] = true; cout q; q.push(..
7회차 - graph, tree, map and set 집합https://www.acmicpc.net/problem/11723다양한 방법으로 풀 수 있는 문제입니다. 1. set을 사용한 풀이단순히 문제에서 설명하는 대로 코드를 작성하면 됩니다.#include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int m, n; string op; cin >> m; set s; for (int i = 0; i > op; if (op == "add") { cin >> n; s.insert(..
[C++] 이진 검색 트리 (백준 5639번)
https://www.acmicpc.net/problem/5639 #include #include using namespace std;vector a;void post(int s, int e) { if (s >= e) return; int idx = e; for (int i = s + 1; i a[s]) { idx = i; break; } } post(s + 1, idx); post(idx, e); cout > x) { a.push_back(x); } int n = a.size(); post(0, n);} 이 문제는 트리 구조를 만들어서 뭔갈 한다기 보다는 어떻게 하면 전위 순회..
[C++] A → B (백준 16953번)
https://www.acmicpc.net/problem/16953 #include #include #include using namespace std;int INTMAX = 1000000000;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); long long a, b; cin >> a >> b; queue> q; q.emplace(a, 0); int ans = -1; while (!q.empty()) { long long x = q.front().first; int cnt = q.front().second; q.pop(); if (x..
[C++] 벽 부수고 이동하기
https://www.acmicpc.net/problem/2206 #include #include #include using namespace std;int dx[] = {1, -1, 0, 0};int dy[] = {0, 0, 1, -1};int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector> g(n, vector(m)); vector> chk(n, vector(m, 0)); for (int i = 0; i > s; for (int j = 0; j > q; // {x index, y index, didBreak, coun..