๋ฌธ์
1595๋ฒ: ๋ถ์ชฝ๋๋ผ์ ๋๋ก
์ ๋ ฅ์ ์ฌ๋ฌ์ค์ ๊ฑธ์ณ ์ฃผ์ด์ง๋ค. ์ ๋ ฅ์ ๊ฐ ์ค์ ์ธ ๊ฐ์ ์์ ์ ์๋ก ๊ตฌ์ฑ๋์ด์๋๋ฐ, ๊ฐ๊ฐ์ ์ฐจ๋ก๋๋ก ์๋ก ๋ค๋ฅธ ๋ ๋์์ ๋ฒํธ์ ๋ ๋์๋ฅผ ์ฐ๊ฒฐํ๋ ๋๋ก์ ๊ธธ์ด๋ฅผ ์๋ฏธํ๋ค. ๋ชจ๋ ๋๋ก๋
www.acmicpc.net
์ฝ๋
#include <iostream>
#include <vector>
#include <memory.h>
using namespace std;
vector<pair<int,int>>graph[10001];
bool visited[10001];
int max_cost, max_node;
void dfs(int node, int cost){
if(cost>max_cost){
max_cost = cost;
max_node = node;
}
visited[node] = 1;
for(auto next: graph[node]){
if(!visited[next.first]){
dfs(next.first, cost + next.second);
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int a, b, c;
while(cin>>a>>b>>c){
graph[a].push_back({b,c}); //a์์ b๊น์ง ๊ฐ๋๋ฐ c๋งํผ์ ๋น์ฉ์ด ๋ ๋ค.
graph[b].push_back({a,c});
}
dfs(1,0);
memset(visited, 0, sizeof(visited));
max_cost = 0;
dfs(max_node, 0);
cout<<max_cost;
}
ํ์ด
๊ฐ์ฅ ๊ฑฐ๋ฆฌ๊ฐ ๋จผ ๋ ๋์ ๊ฐ์ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅํ๋ ๋ฌธ์ ์ ๋๋ค.
๋ ธ๋์ ๊ฐฏ์๊ฐ ์ต๋ 10,000 ์ด๊ธฐ ๋๋ฌธ์ O(N^2) ๋ณต์ก๋๋ก๋ ํด๊ฒฐํ ์ ์๋ ๋ฌธ์ ์ ๋๋ค.
์ ๋ฌธ์ ๋ ๋ค์์ ๋ฌธ์ ์ ๋์ผํฉ๋๋ค.
[๋ฐฑ์ค,c++] 1167๋ฒ - ํธ๋ฆฌ์ ์ง๋ฆ
๋ฌธ์ 1167๋ฒ: ํธ๋ฆฌ์ ์ง๋ฆ ํธ๋ฆฌ๊ฐ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ค. ๋จผ์ ์ฒซ ๋ฒ์งธ ์ค์์๋ ํธ๋ฆฌ์ ์ ์ ์ ๊ฐ์ V๊ฐ ์ฃผ์ด์ง๊ณ (2 ≤ V ≤ 100,000)๋์งธ ์ค๋ถํฐ V๊ฐ์ ์ค์ ๊ฑธ์ณ ๊ฐ์ ์ ์ ๋ณด๊ฐ ๋ค์๊ณผ ๊ฐ์ด ์ฃผ์ด์ง๋ค.
dkswnkk.tistory.com
๋ชจ๋ ๋ ธ๋๋ฅผ ํ์ํ ํ์์์ด ๊ทธ๋ฅ ์๋ฌด ๋ ธ๋๋ ๊ธฐ์ค์ ์ผ๋ก ์ก๊ณ ์ถ๋ฐํด ๊ฐ์ฅ ๊ธด ๋ ธ๋๋ฅผ ์ฐพ์ ํ ํด๋น ๋ ธ๋์์ dfs๋ฅผ ๋๋ฆฌ๋ฉด O(N+M) ์๊ฐ ๋ณต์ก๋๋ก ๊ฐ์ฅ ๊ธด ๊ธธ์ด๋ฅผ ์ฐพ์ ์ ์์ต๋๋ค.
'Algorithm ๐ง๐ปโ๐ป > ๋ฐฑ์ค(BOJ)' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค,c++] 17521๋ฒ - Byte Coin (0) | 2022.08.18 |
---|---|
[๋ฐฑ์ค,c++] 11437๋ฒ - LCA (0) | 2022.08.17 |
[๋ฐฑ์ค,c++] 15900๋ฒ - ๋๋ฌด ํ์ถ (0) | 2022.08.15 |
[๋ฐฑ์ค,c++] 14267๋ฒ - ํ์ฌ ๋ฌธํ1 (0) | 2022.08.15 |
[๋ฐฑ์ค,c++] 19542๋ฒ - ์ ๋จ์ง ๋๋ฆฌ๊ธฐ (0) | 2022.08.14 |
[๋ฐฑ์ค,c++] 2250๋ฒ - ํธ๋ฆฌ์ ๋์ด์ ๋๋น (0) | 2022.08.14 |
๋๊ธ