반응형
문제링크:www.acmicpc.net/problem/14267
14267번: 내리 칭찬
영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하
www.acmicpc.net
dfs 문제였습니다.
이때 완전탐색 횟수를 줄이는게 핵심인 문제였습니다.
우선 첫번째 코드를 먼저 보시죠.
#include <iostream>
#include <vector>
using namespace std;
int n = 0, m = 0;
int cost[100001] = { 0, };
vector <int> vec[100001];
int h, w;
void dfs(int current) {
cost[current] += w;
for (int i = 0; i < vec[current].size(); i++) {
dfs(vec[current][i]);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int temp;
cin >> temp;
if (i == 1) continue;
vec[temp].push_back(i);
}
for (int i = 1; i <= m; i++) {
cin >> h >> w;
dfs(h);
}
for (int i = 1; i <= n; i++) {
cout << cost[i];
if (i == n)
break;
cout << ' ';
}
cout << '\n';
return 0;
}
일반적으로 생각할 수 있는 방법입니다.
근데 이렇게 제출하면 당연히 시간 초과가 납니다.
좀더 효율적으로 탐색할 수 없을까 고민을 하던중에
dfs를 한번만 돌아도 되는 아이디어를 생각했습니다.
아래처럼 dfs(1)을 호출하고 줄줄이 이전 cost값을 더해주는 형태로 구현했습니다.
#include <iostream>
#include <vector>
using namespace std;
int n = 0, m = 0;
int cost[100001] = { 0, };
vector <int> vec[100001];
int h, w;
void dfs(int current) {
for (int i = 0; i < vec[current].size(); i++) {
cost[vec[current][i]] += cost[current];
dfs(vec[current][i]);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int temp;
cin >> temp;
if (i == 1) continue;
vec[temp].push_back(i);
}
for (int i = 1; i <= m; i++) {
cin >> h >> w;
cost[h] += w;
}
dfs(1);
for (int i = 1; i <= n; i++) {
cout << cost[i];
if (i == n)
break;
cout << ' ';
}
cout << '\n';
return 0;
}반응형
'알고리즘 > DFS' 카테고리의 다른 글
| [백준] 15686-치킨 배달(C++) (0) | 2021.01.11 |
|---|---|
| [백준] 2023-신기한 소수(C++) (0) | 2021.01.02 |
| [백준] 2580-스도쿠(C++) (0) | 2020.08.19 |
| [백준] 9663-N-Queen(C++) (0) | 2020.07.27 |
| [백준] 2573-빙산(C++) (0) | 2020.06.09 |
