항상 동일한 로직으로 dfs를 풀었었는데, 이 문제는 시간초과(93%)가 해결되지가 않네요.

제가 해본건 Scanner대신 BufferedReader 사용했고, 메모리때문에 인접행렬 대신 인접리스트 사용했고, LinkedList보다 조금이라도 데이터 조회시 시간복잡도가 낮은 ArrayList 사용했고, 출력문제인가 싶어 Stringbuilder사용해봤습니다. 

현재 코드에서 시간을 많이 잡아먹는 부분이 while문 내에서 인접 리스트를 순차탐색하면서 visited되지 않은 노드를 linear하게 체크하는 부분(

for(int i=0; i<adList[peek].size(); i++)

)이라고 생각하는데, 이 부분도 줄일 수 있는 방법이 있을까요? 아니면 어디가 문제인걸까요...

댓글을 작성하려면 로그인해야 합니다.