dfs2 [개쉬운 풀이] 백준 3197 백조의 호수 CPP (21일차) https://www.acmicpc.net/problem/3197 문제 생각1. 먼저 호수의 영역을 숫자로 표현하여 구분한다.2. 물에 닿은 영역을 set을 활용하여 저장한다. (중복 방지)3. for문을 활용하여 set의 영역을 물로 만들고 다음 날 바뀔 영역들을 저장한다.4. 이때 백조들도 물 취급을 해준다.5. 백조들의 현재 영역을 비교하면서 반복한다. 어려웠던 점1. 영역을 처음에는 dfs를 통해 계속 숫자를 바꿔주려고 했지만, 시간초과에 직면하였다.2. 따라서 union find와 비슷하게 루트 영역을 만들어서 호수의 영역끼리 만나면 merge하였다.3. 백조도 물 취급을 해서 백조 위치의 영역도 생각해주어야 한다.4. melting()이 진행되기 전에, 다음 날 녹을 얼음들을 저장하면서 are.. 2024. 12. 13. [개쉬운 풀이] 백준 19542 전단지 돌리기 문제현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이의 목표는 케니소프트에서 출발하여 모든 노드에 전단지를 돌리고, 다시 케니소프트로 돌아오는 것이다. 현민이는 힘이 좋기 때문에 현재 노드에서 거리가D이하인 모든 노드에 전단지를 돌릴 수 있다.날씨가 매우 덥기 때문에, 현민이는 최소한만 이동해서 목표를 달성하고 싶다! 현민이를 위해 현민이가 이동해야 하는 총 거리를 구해주자.생각위 문제는 트리 모양의 길 위에서 진행된다.따라서 가장 깊은 곳을 방문하고 돌아올때는 x2만 해주면 된다.또한 현민이는 D이하의 노드는 전단지를 돌릴 수 있다. D이하의 노드는 갈필요가 없다는 뜻이다.따라서 트리의 깊이를 고려하며 D이하의 자식 노드들은 무시하면 된다.풀이#include #includ.. 2024. 10. 16. 이전 1 다음
