[BOJ]9466:텀 프로젝트

애증의 문제다...

 

문제만 보면 내가 전혀 못풀리 없어 보여서(??) 이 악물고 풀어봤지만 항상 시간 초과가 떴었다.

이 문제에서 시간초과를 줄이기 위해서는 순차탐색을 하며

1. i번째가 사이클인지 판별할때, 발견된 사이클은 다시 방문하지 않는다.(i를 포함하지 않는 사이클이라도)

2. 이미 방문한(하지만 사이클은 아닌) 경우도 방문하지 않는다.

두개로 시간을 줄여나가야하는데 BFS에만 매달렸던 나는 도저히 1번을 구현할 수가 없었다...

 

결국 bfs코드를 쫙 지워버리고 dfs로 풀었더니 구현과정에서 start와 next를 체크하는게 다소 헷갈렸지만 한번에 맞을 수 있었다.. 

빠르게 정답에 맞는 솔루션을 선택하는 연습도 필요한것 같다

https://github.com/SuyeonChoi/Algorithms/blob/master/BaekJoon/Java/BFS.DFS/p9466.java

SuyeonChoi/Algorithms

 

 

 

 

한달동안 글을 안썼다니..

다시 한번 파이팅할 때다....