[개념 정리] 완전 탐색 원상 복구

특정 경로를 탐색한 후,
그 상태값이 다른 경로에 영향을 미치지 않게 하기위해선 어떻게 해야할까요?

 

 

이 글은 큰돌의 터전님의 강의인 10주 완성 C++ 코딩테스트 알고리즘 개념 교안을 참고하여 작성했습니다.

 

 

완전 탐색 - 원상복구

원상 복구는 탐색 과정에서 특정 경로를 탐색한 후, 그 경로에 대한 상태를 이전 상태로 복구하는 과정입니다.

즉, 현재의 경로를 탐색하고 나서, 탐색한 경로에 대한 흔적을 제거해 다른 경로에 영향을 미치지 않는 것입니다.

 

코드적으로 접근 해보면, 원상 복구란 현재 경로를 탐색할 때 visited 배열에 방문 처리를 했다가, 해당 경로의 탐색이 끝난 후 다른 경로를 탐색하기 전에 방문 처리를 취소하는 행위를 의미합니다.

 

하나의 예시를 들어보겠습니다.

아래와 같은 그래프 모양에서 A→C→D와 A→C→E라는 모든 경로의 수를 출력하는 문제가 있다고 가정합니다.

 

 

먼저, 방문 배열을 사용해  A→C→D 경로를 탐색합니다.

그 다음,  A→C→E 경로를 탐색할 때, 이전에 방문 처리된 D 노드가 여전히 visited 배열에 남아 있다면, 이전 경로의 흔적이 다음 경로 탐색에 영향을 주는 상황이 됩니다.

따라서, 원상 복구를 통해 D 노드의 방문 처리를 취소해주는 과정이 필요합니다. 그래야  A→C→D  경로 탐색이 끝난 후, A→C→E 경로 탐색이 올바르게 동작할 수 있습니다. 즉, 서로 독립적인 경로 탐색이어야 하는데, 방문 배열이 초기화 되지 않으면 경로 간 간섭이 발생하는 문제가 생깁니다.

 

코드로 어떻게 구현할 수 있을까요?

public static void dfs(int curNode, List<Integer> list) {

        if(list.size() == 3) {
            convert(list);
            System.out.println();
            return;
        }

        for(int i = 0; i < graph.get(curNode).size(); i++) {
            int nextNode = graph.get(curNode).get(i);
            if(!visited[nextNode]) {
                visited[nextNode] = true;
                list.add(nextNode);
                dfs(nextNode, list);
                list.removeLast();
                visited[nextNode] = false;
            }
        }
    }

 

visited[curNode] = true로 방문 처리를 한 다음, 해당 경로가 완료될때, visited[nextNode] = false로 두어, 방문 처리를 철회합니다.

원상 복구를 사용해서 A→C→D와 A→C→E 경로를 서로 독립적으로 탐색할 수 있습니다.

 

원상 복구를 할때, list이기 때문에, 추가한 원소를 다시 제거해줘야 합니다.

visited[nextNode] = true;
list.add(nextNode);
dfs(nextNode, list);
list.removeLast();
visited[nextNode] = false;

 

 

출력 결과

 

원상 복구를 사용하는 간단한 문제를 풀면서 알아보겠습니다.

 

Q. 긍정왕 홍철이의 구걸 여행
홍철이는 3 * 3 맵에서 {0, 0} 지점에서 길을 잃어버렸다. 긍정왕 홍철이는 길을 잃어버린 김에 구걸을 하면서 돈을 모으면서 여행을 가려고 한다. 목적지는 {2, 2}이며 방문한 정점은 다시 방문할 수 없고, 해당 맵에 구걸로 얻을 수 있는 돈들이 있다. 홍철이는 4방향(상하좌우)로 움직일 수 있다. {2, 2}까지 간다고 했을 때 이 돈들을 모으는 모든 경우의 수를 출력하여라.

맵
{10, 20, 21},
{70, 90, 12},
{80, 110, 120}

 

구현한 코드

private static void dfs(int y, int x, List<Integer> path) {

    if(y == 2 && x == 2) {
        System.out.println(path);
        return;
    }

    for(int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];

        if(ny < 0 || ny >= 3 || nx < 0 || nx >= 3) continue;
        if(visited[ny][nx] == 0) {
            visited[ny][nx] = 1;
            path.add(map[ny][nx]);
            dfs(ny, nx, path);
            path.removeLast();
            visited[ny][nx] = 0;
        }
    }
}

 

visited[ny][nx] = 1;
path.add(map[ny][nx]);
dfs(ny, nx, path);
path.removeLast();
visited[ny][nx] = 0;

 

 

원상 복구를 사용해서 이전 탐색 경로의 상태값이 현재 탐색 경로의 상태값에 영향을 미치지 않도록 합니다.

 

 

출력 결과