BOJ 9466

오늘 백준님께 시간초과에 대해 여쭤보고 완전히 납득은 안되었지만
그래도 자세한 설명과 문제해결에 관한 실마리 덕분에
불과 몇시간 전만해도 꽉 막혀있던 생각이 시원하게 뚫린 느낌이다.
이런 걸 정말 우물안 개구리라고 하나보다... 불과 몇시간 전만해도 꽉 막혀서
잘못된 방향으로 굳게 믿고 혼자....휴
정말 열심히 하자!


본론으로 들어가서 맞는지 틀린지 모르겠지만 일단 내 생각은 이렇다.
여태까지 난 싸이클이 형성이 된 것을 확인한 후 그 것에 대해서만 visit했다고 check를
true로 바꿔줬었는데, 싸이클이 형성이 안된다면 그 싸이클의 시작점은 바로 true로 바꿔주고 더이상 탐색할 필요가 없다는 것을 깨달았다. 그 점을 지나봤자 싸이클이 형성될 수가 없다!!! 그러니 바로 false로 해줘야한다.

지금 고민중인건 아예 그 점부터 시작해서 방문한 모든점을 (싸이클이 없을 시에) 다 true로 바꿔주는 것도 고민중인데, 그 점을 포함해서는 싸이클이 아니더라도 그 점을 빼고는 싸이클이 있을 수 있으니.. 무작정 true로 만들어버릴 수는 없는 노릇이다.

그래서 일단은 그 시작점만 true로 바꿔보도록 하겠다.
근데 여전히 시간초과...
음 그럼 싸이클이 안될 경우 전부 true로 할 수 있게 싸이클 판별 조건을 수정해야되나...

아 보니깐 내 cycle함수에서 방문해도true로 안바꿔버리는 것도 있고해서... 싸이클을 포함하는 싸이클이 아닌 것의 경우 무한반복이 될 수 있을 것 같다...
수정해야겠다...

생각해보니 .... 음.. 이게 어차피 한 노드에서 여러갈래가 나오는 게 아니므로...
방문한 점을 1로 해놓고, dfs하던 중 방문한 점을 또 만나게되면 싸이클이 있는 것이고..
그렇다면 여기서 구하고자하는 싸이클에 포함안된 점은 어떻게 구하냐?
싸이클이 생기면 즉 방문한 점을 또 만나게 되면 거기서 부터 dfs를 다시 해서 1씩 더해줘서 싸이클에 속해있는 점은 체크값을 2를 갖게 하는 것이지.. 그렇게 구별하는 거지..
한번 해보자.

음 아니구나 방문한 점을 만난다해서 싸이클이 있는게 아니지... 휴...
일단 싸이클은 그럼 첫 출발점과 같으면 있는 것으로 하고, 싸이클이 있을 경우
체크값을 2를 갖도록 해버리자.

음 역시 또 다른 문제가....
그래도 계속 고민하다보니 문제에 대한 이해도가 올라가고
풀릴 것 같다...