최근 풀이 241130

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

• 아이디어
  : b에서 a로 간선을 만들고, 모든 정점에 대해서 dfs 를 진행하는 시퀀스를 작성함.

• 카운팅을 하자. 아래 입력 예제를 보면, 1->3->4 복귀 다시 1->3->5 총
  4개의 카운팅인다.
  : 그래서 이와같이 작성했는데, 시간초과 발생함.
  

• 생각할부분 : 만약에 3 1 이 있는데 다음 줄에 1 3 이 있다고 한다면 무한재귀 발생한다. 그래서 방문 처리가 반드시 필요하다.
  visited 변수를 참조로 하고, 초기화하면서 처리했다.
  

---

첫번째 풀이 241031

: 시간초과 발생한다.
이유는 dfs가 아닌 완탐으로 풀었다. 1만으로 모든 정점을 탐색하니까.
결국 1억의 시간복잡도를 가지고 온다.

https://www.acmicpc.net/submit/1325/85859377

• 네이버 블로그 완탐 부분 다시 공부하자.

: 방문한 정점을 다시 방문할 필요가 없다.

두번째 풀이

https://www.acmicpc.net/submit/1325/85866521

• 왜 dfs를 해야하나?
  : 1-3-4 / 1-3-5 인데 만약에 이렇게 되면 어떻게 될까?
  1-3-4-1 -> 이런식으로 되면 순환구조를 이루게 된다.
  -> 무한 뺑뺑이가 발생한다. 그래서 나는 위에서 시간 초과 발생했다.

따라서 visited 불변수를 이용해서 방문 체크를 하면서 재귀를 해야 한다.

• 알아야 할 점
  : 재귀를 할 때 간단하게 res를 계산하고 반환하는 코드인데
  
  -> 위 코드를 이해하는 것이 정말 중요하다. 반환처리 어떻게 진행되는지.

• 변경하기 전에는 dfs에다가 매개변수를 넣고 int _cnt 넣고, 누적하는 방식으로 했는데, 이렇게 하게 되면, 되지 않는다.