๋ฌธ์
19542๋ฒ: ์ ๋จ์ง ๋๋ฆฌ๊ธฐ
ํ๋ฏผ์ด๋ ํธ๋ฆฌ ๋ชจ์์ ๊ธธ ์์์ ์คํ ๋ฐ์ด๋ฅผ ํ๊ณ ์ ๋จ์ง๋ฅผ ๋๋ฆฌ๋ ค๊ณ ํ๋ค. ํ๋ฏผ์ด์ ๋ชฉํ๋ ์ผ๋์ํํธ์์ ์ถ๋ฐํ์ฌ ๋ชจ๋ ๋ ธ๋์ ์ ๋จ์ง๋ฅผ ๋๋ฆฌ๊ณ , ๋ค์ ์ผ๋์ํํธ๋ก ๋์์ค๋ ๊ฒ์ด๋ค. ํ๋ฏผ
www.acmicpc.net
์ฝ๋
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int>graph[100001];
int depth[100001];
int N, S, D, ans = 0;
int dfs(int node, int before){
for(auto next: graph[node]){
if(next != before){
depth[node] = max(depth[node], dfs(next, node)+1); // ๊ฐ ๋
ธ๋์ ๊น์ด ์์๋ค ์ค ๊ฐ์ฅ ๊น์ ๋
ธ๋์ ๊น์ด๋ฅผ ์ ์ ์์
}
}
if(depth[node]>=D && node != S) ans++;
return depth[node];
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>N>>S>>D;
for(int i=0; i<N-1; i++){
int a,b; cin>>a>>b;
graph[a].push_back(b);
graph[b].push_back(a);
}
dfs(S, -1);
cout<<ans*2;
}
ํ์ด
์ ๋ ฅ์์ ๋ ธ๋์ ๊ฐ์๊ฐ 100,000๊น์ง ๋ค์ด์ค๊ธฐ ๋๋ฌธ์ dfs๋ฅผ ํ ๋ฒ๋ง ๋์์ ํ์ด์ผ ํด๊ฒฐํด์ผ ํ๋ ๋ฌธ์ ์ ๋๋ค.
์ด ๋ฌธ์ ๋ ์ ์ฝ๋์ ์ด ๋ถ๋ถ์ด ๊ฐ์ฅ ํต์ฌ ๋ก์ง์ ๋๋ค.
depth[node] = max(depth[node], dfs(next, node)+1); // ๊ฐ ๋
ธ๋์ ๊น์ด ์์๋ค ์ค ๊ฐ์ฅ ๊น์ ๋
ธ๋์ ๊น์ด๋ฅผ ์ ์ ์์
์ ๋ก์ง์ ๋๊ฒ๋๋ฉด depth๋ ์ ์ด๋ฏธ์ง์ ๊ฐ์ด ์ ์ฅ๋๊ฒ ๋ฉ๋๋ค.
- depth[node]๋ ๊ฐ ๋ ธ๋ ์๋๋ก ์ฐ๊ฒฐ๋ ๋ ธ๋๋ค ์ค ๊ฐ์ฅ ๊ธธ๊ฒ ์ฐ๊ฒฐ๋ ๋ ธ๋์ ๊ธธ์ด๋ฅผ ์๋ฏธํฉ๋๋ค.
- 2๋ฒ ๋ ธ๋์ ๊ฒฝ์ฐ๋ 3๋ฒ๊ณผ 4๋ฒ ๋ ๊ฐ๊ฐ ์ฐ๊ฒฐ๋์ด ์์ง๋ง, 3๋ฒ ๋ ธ๋๊ฐ 5, 6๋ฒ ๋ ธ๋ ๋ ๊ฐ๋ฅผ ๊ฐ์ง๊ฒ ๋์ด 4๋ฒ ๋ ธ๋๋ณด๋ค ๊ธธ์ด์ ธ 2๋ฒ ๋ ธ๋์ depth๋ 3๋ฒ ๋ ธ๋๋ฅผ ํฌํจํ 3์ด ๋ฉ๋๋ค.
depth[node]๊ฐ D์ด์์ด ๋๋ฉด ํด๋น ๋ ธ๋๋ ํ์๋ก ๋ฐฉ๋ฌธํด์ผ ํ๊ธฐ ๋๋ฌธ์ ans++์ ํด์ค๋๋ค. (์ฒซ ๋ฒ์งธ ์์์ ์ผ๋ก ์ด๋ํด์ผ ํ๋ ๊ฑฐ๋ฆฌ๊ฐ ์๋๊ธฐ์ ํฌํจํ์ง ์์ต๋๋ค.)
๊ทธ ํ ์๋ณต์ ํ๋ ๊ฒ์ด๊ธฐ์ ans *2๋ฅผ ํ์ฌ ์ถ๋ ฅํฉ๋๋ค.
'Algorithm ๐ง๐ปโ๐ป > ๋ฐฑ์ค(BOJ)' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค,c++] 15900๋ฒ - ๋๋ฌด ํ์ถ (0) | 2022.08.15 |
---|---|
[๋ฐฑ์ค,c++] 1595๋ฒ - ๋ถ์ชฝ๋๋ผ์ ๋๋ก (0) | 2022.08.15 |
[๋ฐฑ์ค,c++] 14267๋ฒ - ํ์ฌ ๋ฌธํ1 (0) | 2022.08.15 |
[๋ฐฑ์ค,c++] 2250๋ฒ - ํธ๋ฆฌ์ ๋์ด์ ๋๋น (0) | 2022.08.14 |
[๋ฐฑ์ค,c++] 19637๋ฒ - IF๋ฌธ ์ข ๋์ ์จ์ค (0) | 2022.08.02 |
[๋ฐฑ์ค,c++] 2812๋ฒ - ํฌ๊ฒ ๋ง๋ค๊ธฐ (0) | 2022.07.29 |
๋๊ธ