[알고리즘] 백트래킹 풀이기록

https://www.acmicpc.net/problem/15649

 

개인적으로 백트래킹개념이 재귀이다보니까 이해하기가 헷갈렸다..OTL

백트래킹에서 핵심은 재탐색,DFS 인것같다.제일 유명한 n과 m문제를 많이 곱씹었다.

나는 처음 아래와 같이 예시를 풀어봤는데(답출력부분은 따로구현x), 아래처럼 path.pop과 depth-=1를 따로해줄바에 재귀 함수에 넣어주어야 더 깔끔한 코드를 만든다는것을 알았다.

 

아래에서 처음 내 실수는 path[:] 복사본을 생성하지않고 path를 넣어준것이다. 

 

Python에서 리스트는 가변 객체이다. 즉, 리스트를 다른 변수에 할당하거나 함수에 전달하면, 실제로는 그 리스트의 참조(주소)를 전달한다. 만약 ans.append(path)를 사용하면, ans 리스트에는 path 리스트의 참조가 추가된다. 따라서, 이후에 path 리스트가 변경되면, ans 리스트에 저장된 모든 path의 참조도 함께 변경되는 불상사가발생한것이다ㅜ유의하자..

 

모범풀이처럼 +[..]로 새 리스트를 생성하는게 베스트인것..

# N, M = int(int, input().split())
N, M = 4, 2


ans = []
visited = [False] * (N + 1)


def dfs(s, depth, path):
    # 종료 조건
    if depth == M:
        print("ans:", ans)
        ans.append(path[:]) #!!!!!!!!!!!!!!!!!!
        return

    for i in range(1, N + 1):
        if visited[i] == False:
            path.append(i)
            visited[i] = True
            depth += 1
            print("i th ", path)
            dfs(i + 1, depth, path)

            path.pop()
            visited[i] = False
            depth -= 1

dfs(0, 0, [])

# print(ans)

모범풀이

def dfs(n, lst):
    # 종료조건(n에 관련) 처리+정답처리
    if n==M:    # M개의 수열을 완성
        ans.append(lst)
        return

    # 하부단계(함수) 호출
    for j in range(1, N+1):
        if v[j]==0: # 선택하지 않은 숫자인 경우 추가
            v[j]=1
            dfs(n+1, lst+[j])
            v[j]=0

N, M = map(int, input().split())
ans = []            # 정답 리스트를 저장할 리스트
v = [0]*(N+1)       # 중복확인을 위한 visited[]

dfs(0, [])
for lst in ans:
    print(*lst)

자바로도 작성해봤다.

import java.util.Scanner;

public class P_15649 {
    static StringBuilder sb = new StringBuilder();
    static int N, M;
    static boolean[] visited;
    static int[] path;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        visited= new boolean[N+1];
        path = new int[M];

        dfs(0);

        System.out.println(sb);
        sc.close();
    }

    private static void dfs(int depth){
        if(depth==M){ // 종료조건
            for(int val : path){
                if (val!=0) sb.append(val).append(" ");
            }
            sb.append("\n");
            return;
        }
        for(int i = 1; i <= N; i++){
            if(!visited[i]) { // 노드 방문 X
                visited[i] = true;
                path[depth] = i;
                dfs(depth + 1);
                visited[i] = false;
            }
        }
    }
}