[AC] 1325 효율적인 해킹

출처 : https://www.acmicpc.net/problem/1325

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/1325.cpp

이 문제는 DFS로 풀었는데..풀었지만 이해가 되지 않는다. 왜 정답인지 모르겠다. 분명 느린 답안인데...

알고리즘은 다음과 같다. A가 B를 신뢰할때 B를 해킹하면 A가 해킹되므로 입력을 반대로 받는다.

그리고 모든 컴퓨터에 대하여 DFS를 구해 몇개나 연결되어있는지 확인하는 방법인데, 매 진행할때마다 chk를 초기화 해야 하며, 중복도 심하게 일어난다. 그런데도 불구하고 정답이 나온게 신기하다.

암튼 dfs를 통해 몇단계까지 갔는지 리턴하게 되고 그 값을 sava라는 배열에 담고 그중 최고값을 찾아 다시 처음부터 검색하여 최고값과 같을때만 출력하게 하면 된다.

처음에 if(chk[][])이  확인을 함수 맨앞에 배치했는데 이러니 간혹 문제가 발생했다. 

생각해보니 이렇게 하면 중첩이 발생 할 가능성이 생긴다. 노드가 얽혀있을때 저런 표현은 중간에 값을 사라지게 할 가능성이 농후하다. 저러면 안되겠다고 느꼈다.