ehdbs0903 ehdbs0903

문제https://www.acmicpc.net/problem/10282 코드#include #include #include using namespace std;// 2. 우선순위 큐 비교 함수자 Compare// pair(v, w)에서 '시간 w'가 작은 것이 먼저 나오도록(min-heap처럼) 설정struct Compare { bool operator()(const pair& a, const pair& b) { return a.second > b.second; }};// 3. 다익스트라 dijkstra(start, n, graph)// start에서 감염이 퍼지는 최단 시간을 구하고// 감염된 컴퓨터 수와 마지막 컴퓨터까지 걸린 최대 시간을 반환pair di..

문제https://www.acmicpc.net/problem/4195 코드#include #include #include using namespace std;// 2. find(name): 경로 압축으로 대표(루트) 찾기string find(string name, unordered_map& parent) { if (name == parent[name]) return name; // 2-1. 자기 자신이 루트면 그대로 return parent[name] = find(parent[name], parent); // 2-2. 경로 압축}// 3. unite(a, b): 두 집합 합치고 합쳐진 네트워크(집합) 크기 반환int unite(string a, string b, ..

문제https://www.acmicpc.net/problem/13549 코드#include #include #include using namespace std;const int MAX = 100001; // 유효 좌표: 0 ~ 100000const int INF = 1e9;// 2. 0-1 BFS 함수 bfs(n, k)// 순간이동 x->2x 는 비용 0, 걷기 x->x±1 은 비용 1int bfs(int n, int k) { deque dq; vector dist(MAX, INF); // dist[pos] = n에서 pos까지의 최소 시간 // 2-1. 시작 초기화 dist[n] = 0; dq.push_front(n); // 2-2. 덱을 이..

문제https://www.acmicpc.net/problem/10844 코드#include #include using namespace std;const int MOD = 1000000000;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; // 1. DP 1차원 롤링 배열 준비 // current[d]: 현재 길이의 마지막 자리가 d인 계단 수 개수 // next[d]: 다음 길이(한 자리 늘렸을 때)의 마지막 자리가 d인 계단 수 개수 vector current(10), next(10); // 2. 초기화 (길이 1인 계단 수) // ..

문제https://www.acmicpc.net/problem/20007 코드#include #include #include #include using namespace std;using pii = pair;constexpr int INF = 1'000'000'000;// 2. k번째가 아닌 최단 경로에 쓰이는 비교 구조체 Compare// 우선순위 큐에서 거리가 작은 순으로 처리되도록 설정struct Compare { bool operator()(const pii& a, const pii& b) { return a.second > b.second; }}// 3. 다익스트라 함수 dijkstra(start, n, graph)// 시작 노드 start에서 각 노드까지 ..

문제https://www.acmicpc.net/problem/26009 코드#include #include #include using namespace std;// 3. BFS 탐색 함수 정의 bfs()// 그리드에서 4방향으로 이동하며 최단 경로 계산void bfs(int r, int c, int n, int m, vector>& graph) { // 3-1. 4방향 이동 벡터 int dx[] = { -1, 1, 0, 0 }; int dy[] = { 0, 0, -1, 1 }; // 3-2. BFS 큐 및 시작점 방문 처리 queue> q; q.push({ r, c }); graph[r][c] = 1; // 시작점 거리 1로 설정 // 3-3. B..

문제https://www.acmicpc.net/problem/1854 코드#include #include #include using namespace std;constexpr int INF = 1e9;// Compare: priority_queue에서 거리가 작은 순으로 정렬하기 위한 비교 구조체struct Compare { bool operator()(const pair& a, const pair& b) const { return a.second > b.second; }}// 2. k번째 최단 경로 탐색 함수 dijkstra()// modified Dijkstra로 각 노드마다 최대 k개의 최단 경로를 유지하며 탐색vector dijkstra(int k, const v..

문제https://www.acmicpc.net/problem/17071 코드#include #include using namespace std;const int MAX = 500000;int N, K;bool visited[2][MAX + 1];// 2. BFS 탐색 함수 bfs()// 시간에 따른 동생 위치 변화와 parity BFS를 통해 만나는 최소 시간 반환int bfs() { // 2-1. 시작 위치와 목표가 같으면 0초에 만남 if (N == K) return 0; // 2-2. BFS 큐 및 방문 배열 초기화 queue> q; // {현재 위치, 현재 시간} q.push({ N, 0 }); visited[0][N] = true; int t..