BOJ 백트래킹

1548 단어 bojboj

백트래킹, DFS 개념을 몰라서 우선 백트래킹 개념을 예제를 통해 공부했다.
참고

문제

15649 N과 M (1)

N, M = map(int, input().split())
visited = [False] * N  # 탐사 여부 check
out = []  # 출력 내용

def solve(depth, N, M):
    if depth == M:  # 탈출 조건
        print(' '.join(map(str, out)))  # list를 str으로 합쳐 출력
        return
    for i in range(len(visited)):  # 탐사 check 하면서
        if not visited[i]:  # 탐사 안했다면
            visited[i] = True  # 탐사 시작(중복 제거)
            out.append(i+1)  # 탐사 내용
            solve(depth+1, N, M)  # 깊이 우선 탐색
            visited[i] = False  # 깊이 탐사 완료
            out.pop()  # 탐사 내용 제거

solve(0, N, M)

코드 출처
솔루션 중에 이해가 가장 쉬웠다.






좋은 웹페이지 즐겨찾기