๋ฌธ์
1167๋ฒ: ํธ๋ฆฌ์ ์ง๋ฆ
ํธ๋ฆฌ๊ฐ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ค. ๋จผ์ ์ฒซ ๋ฒ์งธ ์ค์์๋ ํธ๋ฆฌ์ ์ ์ ์ ๊ฐ์ V๊ฐ ์ฃผ์ด์ง๊ณ (2 ≤ V ≤ 100,000)๋์งธ ์ค๋ถํฐ V๊ฐ์ ์ค์ ๊ฑธ์ณ ๊ฐ์ ์ ์ ๋ณด๊ฐ ๋ค์๊ณผ ๊ฐ์ด ์ฃผ์ด์ง๋ค. ์ ์ ๋ฒํธ๋ 1๋ถํฐ V๊น์ง
www.acmicpc.net
์ฝ๋
#include <iostream>
#include <vector>
#include <memory.h>
using namespace std;
vector<pair<int,int>> graph[100001];
int max_len = 0, max_node;
bool visited[100001];
void find_max_len(int node, int len){
visited[node] = true;
if(len>max_len){
max_node = node;
max_len = len;
}
for(auto next: graph[node]){
if(!visited[next.first]){
visited[next.first] = true;
find_max_len(next.first, len + next.second);
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int V; cin>>V;
for(int i=0; i<V; i++){
int node_a = 0, node_b, cost;
for(int k=0;; k++){
if(k==0) cin>>node_a>>node_b>>cost;
else{
cin>>node_b;
if(node_b == -1) break;
cin>>cost;
}
graph[node_a].push_back({node_b, cost});
}
}
find_max_len(1, 0);
memset(visited, 0 ,sizeof(visited));
max_len = 0;
find_max_len(max_node, 0);
cout<<max_len;
}
ํ์ด
[๋ฐฑ์ค,c++] 1967๋ฒ - ํธ๋ฆฌ์ ์ง๋ฆ
๋ฌธ์ 1967๋ฒ: ํธ๋ฆฌ์ ์ง๋ฆ ํ์ผ์ ์ฒซ ๋ฒ์งธ ์ค์ ๋ ธ๋์ ๊ฐ์ n(1 ≤ n ≤ 10,000)์ด๋ค. ๋์งธ ์ค๋ถํฐ n-1๊ฐ์ ์ค์ ๊ฐ ๊ฐ์ ์ ๋ํ ์ ๋ณด๊ฐ ๋ค์ด์จ๋ค. ๊ฐ์ ์ ๋ํ ์ ๋ณด๋ ์ธ ๊ฐ์ ์ ์๋ก ์ด๋ฃจ์ด์ ธ ์๋ค.
dkswnkk.tistory.com
์ ๋ช ํ ๋ฌธ์ ์ ๋๋ค. ์ด์ ์ ํ์๋ ์ ๋ฌธ์ ์ ๊ฑฐ์ ๋์ผํฉ๋๋ค.
์ด ๋ฌธ์ ๋ ์๊ฐ ์ด๊ณผ์ ์ ์ํด์ผ ํ๋๋ฐ ์ ๋ ์ฒ์์ ์๋์ ๊ฐ์ด ๋ชจ๋ ๋ ธ๋๋ค์ ํ์ํ๋ฉด์ ๊ฐ์ฅ ๊ธด ์ง๋ฆ์ ์ฐพ์์ต๋๋ค.
for(int i=1; i<=V; i++){
find_max_len(i, 0);
memset(visited, 0 ,sizeof(visited));
}
ํ์ง๋ง ๋น์ฐํ๊ฒ๋ ํด๋น ์ฝ๋๋ O(100,000 ^ 100,000)์ผ๋ก ์๊ฐ ์ด๊ณผ๊ฐ ๋ฐ์ํฉ๋๋ค.
๊ณ ๋ฏผํ๋ ๋ถ๋ถ์ ๊ณผ์ฐ ์ด๋ป๊ฒ ๊ฐ์ฅ ๊ธด ๋ ธ๋๋ฅผ ๋ฐ๋ก ์ฐพ์ ์ ์์๊น ์ธ๋ฐ, ์ฌ์ค ์ด ๋ถ๋ถ์ ๋ฑ ํ ๋ฒ๋ง ์๋ฌด ๋ ธ๋๋ ์ก๊ณ ๊ฐ์ฅ ๋ฉ๋ฆฌ ์๋ ๋ ธ๋๋ฅผ ์ฐพ์ผ๋ฉด ๋ฉ๋๋ค.
5
1 3 2 -1
2 4 4 -1
3 1 2 4 3 -1
4 2 4 3 3 5 6 -1
5 4 6 -1
์์ ๊ฐ์ ์ ์ถ๋ ฅ์์ ์ด๋ ๋ ธ๋(1, 2, 3 ,4, 5)๋ฅผ ์ก๊ณ ์์ํด๋ 1 ํน์ 5๋ก ๋์ค๊ฒ ๋ฉ๋๋ค.
๋ฐ๋ผ์ 1์ด ๋์๋ค๋ฉด 1์์ ๊ฐ์ฅ ๋ฉ๋ฆฌ ์๋ ๋ ธ๋(5)๊น์ง์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๊ณ , 5๊ฐ ๋์๋ค๋ฉด 5์์ ๊ฐ์ฅ ๋ฉ๋ฆฌ์๋ ๋ ธ๋(1)๊น์ง์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ฉด ๋ฉ๋๋ค.
๋ฐ๋ผ์ ์๊ฐ๋ณต์ก๋ O(100,000 + 100,000)๋ง์ ๊ตฌํ ์ ์์ต๋๋ค.
'Algorithm ๐ง๐ปโ๐ป > ๋ฐฑ์ค(BOJ)' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค,c++] 2812๋ฒ - ํฌ๊ฒ ๋ง๋ค๊ธฐ (0) | 2022.07.29 |
---|---|
[๋ฐฑ์ค,c++] 13164๋ฒ - ํ๋ณต ์ ์น์ (0) | 2022.07.27 |
[๋ฐฑ์ค,c++] 2138๋ฒ - ์ ๊ตฌ์ ์ค์์น (0) | 2022.07.27 |
[๋ฐฑ์ค,c++] 9489๋ฒ - ์ฌ์ด (0) | 2022.07.26 |
[๋ฐฑ์ค,c++] 20924๋ฒ - ํธ๋ฆฌ์ ๊ธฐ๋ฅ๊ณผ ๊ฐ์ง (0) | 2022.07.24 |
[๋ฐฑ์ค,c++] 20365๋ฒ - ๋ธ๋ก๊ทธ2 (0) | 2022.07.24 |
๋๊ธ