[DFS & BFS] 메모리 초과할 때

BFS & DFS 문제를 풀다보면, 메모리 초과가 발생할 때가 있다. 

대부분 메모리 초과의 이유는 Stack에 담기는 요소가 계속해서 중복값을 넣고 제대로 필터링을 하지 않아서 발생한 문제이다.

Visited 의 위치가 중요하다. 

 

---

다음 코드를 보자, 

visited 선언에 따라서 결과가 다르게 반영된다. 자세하게 보자, 

첫번째의 경우 

만약 , Queue에 Node 1 , 2 , 3, 4 가 들어있는 상황에서 Node 1이 꺼내져서 bfs를 한다고 해보자, 

그리고, Node 1 에서 갈 수 있는 Node는 Node 2 , Node 3이라고 하자.

Node1 이 bfs를 하면서 Node 2가 당연히 아직 큐에 있으니, Visited[Node2] 는 false 이므로 또 넣게 되는 불상사가 생긴다. 

큐에 있는 Node들은 한 번 나오기 전까지 계속해서 중복 저장된다.

 

 

두번째 경우는 

중복된 Node를 큐에 넣긴 한다. 하지만, 꺼내서 나올 때 if(!visited[]) 로 모두 필터링 되어 한번만 실행됨을 보장한다. 

 

---

안전한 방법은

static void bfs(Point start) {
        int[] nx = { 1, -1, 0, 0 };
        int[] ny = { 0, 0, 1, -1 };
        Queue<Point> que = new ArrayDeque<>();
        que.add(start);
        visited[start.x][start.y] = true;   // 여기 넣고

        while (!que.isEmpty()) {
            Point curr = que.poll();
            if (curr.x == n - 1 && curr.y == m - 1) {
                answer.add(curr.dis);
                return;
            }
            for (int i = 0; i < 4; i++) {
                int nextx = curr.x + nx[i];
                int nexty = curr.y + ny[i];
                if (isValid(nextx, nexty)) {
                    que.add(new Point(nextx, nexty, curr.dis + 1));
                    visited[nextx][nexty] = true;   //여기 넣으면 안전 !
                }
            }
        }
    }

이렇게 할 수도 있다.