와..완전탐색도 가물가물 가물치...
완전탐색 기초 문제인데 이 문제 푸는데 대체 몇시간이 걸린거지...?!!!
근데 백준 통과는 했는데 아직도 제대로 이해하면서 풀었다는 생각이 안든다.
어쩌면 원래도 제대로 코드를 이해하지 못하면서 완전탐색 문제들을 풀었던 걸지도?

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1

3 1

예제 출력 1

1
2
3

예제 입력 2

4 2

예제 출력 2

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

예제 입력 3

4 4

예제 출력 3

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

나의 코드

from sys import stdin as s

# s = open("input.txt", "rt")  # 주석 처리해야 하는 부분

n, m = map(int, s.readline().split())
visited = [0] * (n + 1)


def dfs(depth, visited, nums=[]):
    if depth == m:
        # nums를 문자열로
        print(' '.join(map(str, nums)))
        return
    for i in range(1, n + 1):
        if visited[i]:
            continue
        visited[i] = 1
        dfs(depth + 1, visited, nums + [i])
        visited[i] = 0


dfs(0, visited)

완전탐색 코드의 작동원리를 좀 더 깊이 파악해보기 위해 print(nums)를 if문 내부가 아니라 함수를 시작하자마자 있는

def dfs(depth, visited, nums=[]):
    print(nums)
    if depth == m:
    # ...(중략)

이 곳으로 옮기면 아래와 같이 출력된다.

[] # 함수 호출되자마자 출력
[1] # dfs(1, [0, 1, 0, 0, 0], [1]) 재귀호출하자마자 [1] 출력
[1, 2] # dfs(2, [0, 1, 1, 0, 0], [1, 2] 재귀호출하자마자 [1, 2] 출력
[1, 2, 3] # dfs(3, [0, 1, 1, 1, 0], [1, 2, 3] 재귀호출하자마자 [1, 2, 3] 출력
[1, 2, 3, 4] # dfs(4, [0, 1, 1, 1, 1], [1, 2, 3, 4] 재귀호출하자마자 [1, 2, 3, 4] 출력, depth == 4이므로 재귀 종료
[1, 2, 4] 다시 # dfs(3, [0, 1, 1, 1, 0], [1, 2, 3])를 호출했을 시점으로 돌아가보자. 이때 nums + [i]가 [1, 2, 3]이었다는 건 nums가 [1, 2]였다는 뜻이다. 그리고 depth + 1이 3이었다는 것은 이 때 depth가 2였다는 것이다. visited[3] = 0이 되고, for문에서 i가 4로 증가하면 visited[4] = 1이 된다. 이 때 dfs(3, [0, 1, 1, 0, 1], [1, 2, 4]) 재귀 호출 하자마자 [1, 2, 4] 출력. 
[1, 2, 4, 3] 아직 depth가 3이므로 for문 진입. 이때 visited[3] = 1이 되고 dfs(4, [0, 1, 1, 1, 1], [1, 2, 4, 3]) 재귀 호출하여 [1, 2, 4, 3] 출력 후 depth가 4 도달하여 재귀 종료.
[1, 3]
[1, 3, 2]
[1, 3, 2, 4]
[1, 3, 4]
[1, 3, 4, 2]
[1, 4]
[1, 4, 2]
[1, 4, 2, 3]
[1, 4, 3]
[1, 4, 3, 2]
[2]
[2, 1]
[2, 1, 3]
[2, 1, 3, 4]
[2, 1, 4]
[2, 1, 4, 3]
[2, 3]
[2, 3, 1]
[2, 3, 1, 4]
[2, 3, 4]
[2, 3, 4, 1]
[2, 4]
[2, 4, 1]
[2, 4, 1, 3]
[2, 4, 3]
[2, 4, 3, 1]
[3]
[3, 1]
[3, 1, 2]
[3, 1, 2, 4]
[3, 1, 4]
[3, 1, 4, 2]
[3, 2]
[3, 2, 1]
[3, 2, 1, 4]
[3, 2, 4]
[3, 2, 4, 1]
[3, 4]
[3, 4, 1]
[3, 4, 1, 2]
[3, 4, 2]
[3, 4, 2, 1]
[4]
[4, 1]
[4, 1, 2]
[4, 1, 2, 3]
[4, 1, 3]
[4, 1, 3, 2]
[4, 2]
[4, 2, 1]
[4, 2, 1, 3]
[4, 2, 3]
[4, 2, 3, 1]
[4, 3]
[4, 3, 1]
[4, 3, 1, 2]
[4, 3, 2]
[4, 3, 2, 1]

이렇게 파헤쳐본 이유는 (앞부분 밖에 못했는데 이마저도 오래걸림,, ㅎㅎ) 완전탐색 작동 원리가 머릿속에 탄탄히 정립되어 있지 않아 이번에 오랜만에 문제를 풀면서 헤매는 시간이 길어졌다고 생각했기 때문이다.

이전에 완전탐색 코드의 작동 원리를 파헤치려다가 실패한 적이 있었는데, 그거에 비하면 그래도 많이 오긴 왔다. 일단 코드를 외워놓고 문제들이 죄다 풀리니까 여태 완전탐색 코드 안다고 착각하고 있던 게, 알고리즘 손놓고 있다가 까먹은 것의 주요 원인인 것 같다. 그래서 일단 [1, 2, 4, 3]까지만 파헤쳐봤는데... 여전히 뒷 부분은 아직 어렵다... 그래도 여기까지 해보니 조금이나마 코드순서와 작동 원리가 다시 감이 온다.

++ 실패했던 시도

• 처음에 nums를 아예 매개변수에 선언할 생각을 못했었고, 대신 visited[i]에 매 반복문 회차마다 depth를 할당하는 문제라고 잘못 생각했다. visited[i]에 depth를 할당했었는데, 처음에는 의도한대로 출력되는 건가...? 싶어서 스크롤을 내려보면 숫자가 순서대로 출력되지 않았다. 알고보니 visited는 그저 방문 여부를 확인하는 용도로 사용해야하는 것이었다.

---

오늘은 하루 지난 8월 11일!

이렇게 손으로 써보면서 코드의 흐름을 따라가니까 좀 더 이해가 잘된다.

함수가 신규 호출, 또는 재귀 호출 되자마자 현재 depth, nums, visited를 출력하고, for문에 진입했을 때 재귀 호출하며 넘겨주는 인수들이 어떤지 한 줄 한 줄 써보니 조금씩 흐름이 잡힌다.

그리고 오늘은 N과 M (2)도 풀어보았다.

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
고른 수열은 오름차순이어야 한다.
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1

3 1

예제 출력 1

1
2
3

예제 입력 2

4 2

예제 출력 2

1 2
1 3
1 4
2 3
2 4
3 4

예제 입력 3

4 4

예제 출력 3

1 2 3 4

나의 코드

from sys import stdin as s

# s = open("input.txt", "rt")  # 주석 처리해야 하는 부분

n, m = map(int, s.readline().split())

visited = [0] * (n + 1)


def dfs(depth, visited, nums=[], start=1):
    if depth == m:
        print(" ".join(map(str, nums)))
        return

    for i in range(start, n + 1):
        if visited[i]:
            continue
        visited[i] = 1
        dfs(depth + 1, visited, nums + [i], i + 1)
        visited[i] = 0


dfs(0, visited)

기존 N과 M 코드에 start 매개변수를 추가하고, 재귀 호출할 때마다 i + 1을 인자로 넘기는 백트래킹 가지치기이다.

가지치기 문제는 백준 치킨 거리 문제 풀 때 한 번 접해보았었다. 물론 가물가물가물치이지만,,

치킨 거리 포스팅
https://velog.io/@jasmine0714/%EB%B0%B1%EC%A4%80-gold5-%EC%B9%98%ED%82%A8-%EA%B1%B0%EB%A6%AC

기존 N과 M 문제에서는 한 번 나온 숫자 조합이더라도 순서가 다르면 다시 출력될 수 있고, N과 M (2)에서는 한 번 나온 숫자 조합은 다시 나오지 않는다.

즉, N과 M 문제에서 출력되는 숫자 세트의 개수는 퍼뮤테이션 개념이고, N과 M (2) 문제에서 출력되는 숫자 세트의 개수는 컴비네이션 개념이다.

이번에도 직접 손으로 써보며 코드 흐름을 하나씩 따라가보았다.

앞으로 완전탐색 풀면서 헷갈릴 때마다 이렇게 수기로 써보며 흐름을 파악해야겠다. 아직도 100% 파악된 건 아니지만 어제의 나보다는 많이 이해하고 있는 것 같다.