[19542] 전단지 돌리기 - UCPC 2020 본선 A번, c++

<네이버에서 옮겨온 것>

---

한줄 후기 : 처음이자 마지막(?) 본선

 

https://www.acmicpc.net/problem/19542

19542번: 전단지 돌리기

 

전단지 돌리기 성공출처

Gold IV

깊이 우선 탐색그래프 이론그래프 탐색트리

난이도 제공: solved.ac — 난이도 투표하러 가기

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초 (추가 시간 없음)	1024 MB	381	182	162	51.266%

 

문제

현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이의 목표는 케니소프트에서 출발하여 모든 노드에 전단지를 돌리고, 다시 케니소프트로 돌아오는 것이다. 현민이는 힘이 좋기 때문에 현재 노드에서 거리가

D이하인 모든 노드에 전단지를 돌릴 수 있다.

날씨가 매우 덥기 때문에, 현민이는 최소한만 이동해서 목표를 달성하고 싶다! 현민이를 위해 현민이가 이동해야 하는 총 거리를 구해주자.

 

입력

첫번째 줄에는 노드의 개수 N(1≤N≤100 000)과 케니소프트의 위치 S(1≤S≤N), 힘 D(0≤D≤N)이 주어진다.두 번째 줄부터 N번째 줄까지, 트리의 간선 정보를 의미하는 두 자연수 x, y가 공백으로 구분되어 주어진다. 이는 x번 노드와 y번 노드가 연결되어 있음을 의미한다. (1≤x,y≤N, x≠y)

주어지는 연결관계는 트리를 구성하며, 모든 간선의 길이는 1이다.

 

출력

현민이가 목표를 완수하기 위해 이동해야 하는 최소 거리를 출력하여라.

 

예제 입력 1

6 1 1 1 2 2 3 2 4 3 5 5 6

 

예제 출력 1

6

 

 

 

 

출처

Contest > 전국 대학생 프로그래밍 대회 동아리 연합 여름 대회 > UCPC 2020 A번

 

애증의 UCPC 본선 문제..

우리팀에선 지혜랑 나랑 풀었다. + 다른팀에서는 하얀이가

처음에 보자마자 dfs네 하고 내가 코드를 짰다가 틀렸는데 바보같이 자식 개수로 갈지 안갈지를 비교했다. 이건 그런게 아니라 현재 위치에서 자식 전체의 깊이를 비교해야 하는 문제다.

그래서 그걸 어떻게 할 지 고민하다. 그래프 탐색을 2번 하는 것으로 방향을 잡고 풀었다.

1번째 DFS에서는 재귀로 돌면서 재귀가 끝날 때마다 즉, 거꾸로 올라가면서 내 뒤에 노드의 깊이를 저장해줬다. 2번 BFS 에서는 전체 탐색하면서 전단지를 어디까지 돌릴지 거리를 계산했다.

참고로 돌아올 때는 결국 똑같이 돌아올 거니 *2해주면 된다. 생각보다 심플한 문제인데 노드 10만개를 보고 탐색 2번이라 시간초과는 안날지, 거꾸로 깊이 저장을 어떻게 할지 우리가 너무 고민했다. 생각해보면 시간초과는 절대 안나는데 ㅋㅋㅋㅋㅋㅋㅋ

BFS와 DFS의 인접리스트 시간복잡도가 O(V+E)이니 두번을 동시에 돌린게 아니라 시간초과는 걱정 안해도 된다.

 

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<int> node[100001];
int a[100001];
bool visit[100001];
int n, s, d;
int dfs(int x) {
   int depth=0;
   bool leaf = true;
   visit[x] = true;
   for (int i = 0; i < node[x].size(); i++) {
      int y = node[x][i];
      if (!visit[y]) {
         leaf = false;
         depth = max(depth, dfs(y) + 1);
      }
   }
   if (!leaf)
      a[x] = depth;
   return a[x];
}
int main() {
   scanf("%d %d %d", &n, &s, &d);
   for (int i = 1; i < n; i++) {
      int x, y;
      scanf("%d %d", &x, &y);
      node[x].push_back(y);
      node[y].push_back(x);
   }
   for (int i = 1; i <= n; i++)
      visit[i] = false;
   dfs(s);
   

   int ans = 0;
   queue<int> q;
   q.push(s);
   for (int i = 1; i <= n; i++)
      visit[i] = false;
   visit[s] = true;
   if (a[s] > d) {
      while (!q.empty()) {
         int x = q.front();
         q.pop();
         for (int i = 0; i < node[x].size(); i++) {
            int y = node[x][i];
            if (!visit[y] && a[y] >= d) {
               q.push(y);
               visit[y] = true;
               ans++;
            }
         }
      }
   }
   printf("%d\n", ans * 2);
}

 

다른 후기들을 보니 BFS 한번에 구현한 팀도 있다더라 정말 대단해 나도 코드를 효율적으로 짜고 싶다 ㅋ..