hsw0194   3년 전

BFS나 DFS 를 구현할때 

방문을 체크해야 하는 노드가 매우 많을때,

예를 들어 14395 문제에서 탐색한 노드인지를 검사할때

방문해야하는 노드의 개수가 10^9개입니다.

이럴때는 visit 배열을 10^9의 크기로 유지하기에는 너무많고

메모리 초과이슈도 있는데

이럴때는 보통 어떻게 처리를 하는게 좋을까요?

skeep194   3년 전

그런 경우 보통 bfs나 dfs가 답이 아닌 경우가 더 많습니다. (10^9 번 방문하면 무조건 시간 초과를 받겠죠)

혹은 값 범위가 넓지만 탐색할 수 있는 공간은 한정된 경우 map<int,bool> visited; 이렇게 하기도 합니다.

hsw0194   3년 전

감사합니다!

14395번은 파이썬 set을 이용해 풀었습니다 ㅎㅎ

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