백준 15649 N과 M(1)

15649번: N과 M (1) (acmicpc.net)

15649번: N과 M (1)

첫 백트래킹(DFS) 문제였다.

처음이어서 답을 참고했지만 다음부턴 스스로 풀도록 하자.......

N,M = map(int, input().split())
visited = [False] * N
lst = []
def dfs(depth):
    if depth == M:
        print(' '.join(map(str, lst)))
        return
    for i in range(N):
        if not visited[i]:
            visited[i] = True
            lst.append(i + 1)
            dfs(depth + 1)
            visited[i] = False
            lst.pop()
dfs(0)

<새로 안 상식>

1.map(str, lst) => map함수는 여러 요소들을 한 번에 형식 변환을 하기 위해 쓰이는 함수로

이렇게 썼을 때는 lst의 모든 요소를 한 번에 str로 바꾼다는 뜻이다.

2.' '.join(lst) : lst의 요소들을 공백을 통해 합한다는 뜻이다.

3.DFS의 기본 구조

 - 1.depth의 길이에 해당하는 visited라는 'False' 요소로 이루어진 리스트를 만든다.

 - 2.dfs라는 함수는 0부터 시작하여 depth까지 내려가는데, depth에 도달하면 print로 출력하고 return 한다.

 - 3.depth에 도달하기 전에는 for문으로 한 타임에 출력해야할 길이만큼 for문을 돌린다.

       (이 과정에서 깊이 우선 탐색이 이루어짐)

     * 한 번 for문이 돌아갈 때마다 해당하는 visited 의 index가 true로 바뀌며 lst에도 값이 추가된다.

     * 그 다음에 재귀로 dfs(depth + 1)로 들어간다. 

     * 재귀문 실행 뒤에는 빠져나왔기 때문에 빠져나온 만큼 visited를 false로 다시 바꿔주고, lst도 참고할 시 pop으로 마찬가지로 한 요소를 꺼내줘야 함