백트래킹> 15649. N과 M (1)

 

<문제링크: www.acmicpc.net/problem/15649>

15649번: N과 M (1)

문제설명: 숫자 N과 M이 주어지고, 1부터 N까지의 숫자를 활용하여

M개 길이의 수열을 만들어 출력하면 된다.

 

 

[1차 시도]

def find(cur,cnt):
    #(2)
    global N,M
	
    #(3)
    if cnt == M:
        print(' '.join(cur))
        return
        
    else:
        #(4)
        visited[int(cur[-1])] = 1
        for i in range(1, N + 1):
        
            #(5)
            if not visited[i]:
                visited[i] = 1
                #(6)
                find(cur + str(i), cnt + 1)
                #(7)
                visited[i] = 0

#(1)
N, M = map(int,input().split())
for i in range(1,N+1):
    visited = [0] * (N + 1)
    find(str(i),1)

 

풀이:

 

#(1)

N,M을 입력값으로 받고 for문으로 1부터 N까지 돌아 수열의 첫 번째 자리를 픽스한다.

 

그리고 새로운 수열이 만들어질 때마다 수열에 포함하는 숫자들이 사용되었는지

방문여부를 체크하기 위해 0으로 채워진 빈 리스트를 만들어준다.

 

find 함수에 현재 수열의 첫 번째 자리와 현재 수열의 길이인 1을 인자로 넘겨준다.

 

 

수열을 완성해나가기 위한 find 함수를 만들어준다.

 

#(2)

global로 N과 M을 전역변수로 선언해주어 find 함수에서

수열에 포함할 숫자의 범위 지정과 수열의 길이를 체크한다.

 

#(3)

만약 현재까지 완성된 수열의 길이가 M과 일치하다면, 현재 수열 cur을 형식에 맞게 출력해주고 return으로 종료한다.

 

#(4)

만약 아직 수열이 완성되기 전이라면, 마지막으로 추가된 숫자인 cur[-1] 값을 방문했다고 표시하기 위해

visited 배열의 인덱스 자리를 찾아 1로 갱신한다.

 

#(5)

그 다음 자리의 숫자를 찾기 위해 for문으로 1부터 N까지 탐색하며 만약 아직 방문(사용)하지 않은 숫자가 있다면, 

0을 1로 바꾸어 방문표시를 해준다.

 

#(6)

재귀함수로 find함수에 (현재 수열+추가 숫자), (수열 길이+1)을 인자로 넣어 넘겨준다.

 

#(7)

그리고 다시 현재의 고려대상인 수열의 visited 배열은 다음 번 수열이 생성 가능한 경우의 수에서 사용할 수 있도록

현재 인덱스의 방문 표시를 0으로 갱신한다.  

 

이렇게 하면 생성 가능한 수열에서 숫자의 중복이 가능하다.

ex) 1 2 3 4

     1 2 4 3

 

 

 

채첨결과: 정상적으로 잘 통과한다.

 

 

 

 

'쫄보의삽질' 블로그 탄생 스토리가 궁금하다면:

Git push 취소 방법 (feat. '쫄보의삽질' 블로그 탄생 배경)