[백준] 15649 N과 M (1) (실버3) / 백트래킹

문제요약

나의 코드 및 설명

• 중복없이 M개를 고른 수열을 ans에 저장하기 위해 main 함수에서 visited 리스트를 생성하고, ans에 해당 수가 저장된다면 visited의 동일 인덱스에 1을 저장한다.

ans = []
def dfs(index): #index자리
    if len(ans) == m:
        print(" ".join(map(str, ans)))
        return
    if index == n:
        return 
    
    for i in range(1, n+1):
        if visited[i] == 0: #ans에 현재의 값이 들어있는지 확인
            visited[i] = 1 #지금 들어가니까 방문처리
            ans.append(i)
            dfs(index+1) #다음 자리를 결정하는 함수 호출
            visited[i] = 0
            ans.pop() #갔다와서는 마지막 자리를 빼줌


n, m = map(int, input().split())
visited = [0] * (n+1) #중복되는 수열이 들어가면 안된다.

dfs(0)

 

다시 풀은 나의 코드 및 설명

• 생각해보니 어차피 index(선택한 숫자의 개수)가 m이 된다면 리턴해주는 것이므로, 종료 시점에 대하여 n과는 무관하다.

def dfs(index, temp_list):
    if index == m:
        print(" ".join(map(str, temp_list)))
        return
    
    for i in range(1, n+1):
        if visited[i] == 0:
            visited[i] = 1
            temp_list += [i]
            dfs(index+1, temp_list)
            visited[i] = 0
            temp_list.pop()
    
n, m = map(int, input().split())

visited = [0] * (n+1)
dfs(0,[])

피드백

SWEA D3 풀다가 백트래킹, DFS, BFS 문제가 등장하기에 백준 단계별 풀어보기와 동영상 강의를 통해 공부할 계획이다. 아직 미숙하지만 DFS와의 차이점을 알 수 있었고, 반복 훈련을 통해 익숙해져야겠다. 앞으로 백트래킹이나 DFS, BFS 문제가 나오면 트리 등 그림을 그려서 풀이 과정을 찾는 연습을 해야겠다.