[백준] 1325번 효율적인 해킹 - C++ (DFS, 그래프)
2022. 11. 10. 18:56
solving/C, C++
발상 1. 우선 그래프를 이용하는 문제인데 - A가 B를 신뢰할 경우 B를 해킹하면 A도 해킹할 수 있다는 것은, B가 부모 노드이고 A가 자식 노드인 것으로 생각하였다. B->A로 간선이 이어져서 B에서 해킹할 수 있는 자식 노드들을 모두 동시에 해킹할 수 있는 것들로 보았다. 2. DFS를 이용해 1~N까지 각 노드에서 출발했을 때 총 몇 개의 노드를 방문할 수 있는지를 계산하면 되는 문제이다. 3. dfs 함수를 int로 설정하였다. for문을 이용해 1~N까지 반복문을 설정하고, 각 node에서 출발하여 새로운 node를 방문할 때 (check값이 false인 자식 노드) ans에 해당 node에서의 dfs 값을 더하도록 했다. (해당 노드+거기에 연결된 자식 노드의 수) 4. 반환된 ans값을 ..