-
백준 1939 중량제한 - C++, BFS, 이진탐색쾌락없는 책임 (공부)/알고리즘 문제풀이 2021. 3. 28. 18:40반응형
백준 1939 : www.acmicpc.net/problem/1939
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstring> using namespace std; int n, m, s, f; vector<pair<int, int>> road[10001]; bool visit[10001]; bool Bfs(int input){ queue<int> q; q.push(s); visit[s] = true; while (!q.empty()){ int cur = q.front(); q.pop(); if(cur == f) return true; for(int i = 0; i < road[cur].size(); i++){ if(!visit[road[cur][i].first] && input <= road[cur][i].second){ visit[road[cur][i].first] = true; q.push(road[cur][i].first); } } } return false; } int main(){ scanf("%d %d", &n, &m); int MAX = 0; for(int i = 0; i < m; i++){ int a, b, c; scanf("%d %d %d", &a, &b, &c); road[a].push_back(make_pair(b,c)); road[b].push_back(make_pair(a,c)); MAX = max(MAX, c); } scanf("%d %d", &s, &f); // 이진 탐색 시작 int left = 0, right = MAX; while (left <= right){ memset(visit, false, sizeof(visit)); int mid = (left + right) / 2; if(Bfs(mid)) left = mid + 1; else right = mid - 1; } printf("%d\n", right); }
1. 각 입력값을 받아 온다.
2. 다리와 중량의 정보를 받아올때 pair을 이용하고 bfs탐색에서 사용할 수 있도록 양방향으로 저장
3. 한번의 이동에서 가장 무겁게 옮길 수 있는 중량을 구하는거니 left, right를 선언해 이진탐색 시작.
4. mid 값이 정해지면 Bfs 함수에 넣어서 '갈 수 있는지'를 검증 (이를 위해서 bool로 선언)
5. while문이 끝나면 나오는 right값이 최대 무게의 값입니다.
반응형'쾌락없는 책임 (공부) > 알고리즘 문제풀이' 카테고리의 다른 글
백준 6198 옥상 정원 꾸미기 - C++ 스택 (0) 2021.04.04 백준 2437 저울 - C++ 그리디 알고리즘 (0) 2021.04.02 백준 2109 순회강연 - C++ 라이브러리로 간단하게 (0) 2021.03.26 백준 9251, 9252 - Longest Common Subsequence (0) 2021.03.04 백준 14226 이모티콘 - 큐를 이용한 너비 우선 탐색 (0) 2021.02.26