BFS나 DFS 를 구현할때
방문을 체크해야 하는 노드가 매우 많을때,
예를 들어 14395 문제에서 탐색한 노드인지를 검사할때
방문해야하는 노드의 개수가 10^9개입니다.
이럴때는 visit 배열을 10^9의 크기로 유지하기에는 너무많고
메모리 초과이슈도 있는데
이럴때는 보통 어떻게 처리를 하는게 좋을까요?
그런 경우 보통 bfs나 dfs가 답이 아닌 경우가 더 많습니다. (10^9 번 방문하면 무조건 시간 초과를 받겠죠)
혹은 값 범위가 넓지만 탐색할 수 있는 공간은 한정된 경우 map<int,bool> visited; 이렇게 하기도 합니다.
감사합니다!
14395번은 파이썬 set을 이용해 풀었습니다 ㅎㅎ
댓글을 작성하려면 로그인해야 합니다.
hsw0194 3년 전
BFS나 DFS 를 구현할때
방문을 체크해야 하는 노드가 매우 많을때,
예를 들어 14395 문제에서 탐색한 노드인지를 검사할때
방문해야하는 노드의 개수가 10^9개입니다.
이럴때는 visit 배열을 10^9의 크기로 유지하기에는 너무많고
메모리 초과이슈도 있는데
이럴때는 보통 어떻게 처리를 하는게 좋을까요?