[백준] 15649번 N과 M(1)

사용 언어 - Python3

15649번: N과 M(1) (실버3, DFS 백트래킹 문제)

문제 ★LG CNS 21년 상반기 코테랑 유사★

15649번: N과 M (1)

 

 

정답

DFS 백트래킹 재귀함수 문제 !! 15649,15450,15651,15652번은 세트로 공부

• 아래 백트래킹 문제 링크를 첨부합니다.

(정답 풀이) [1] -> [1,2] -> [1] -> [1,3] -> [2] -> [2,1] -> [2] -> [2,2] ->.... 

1. N=3, M=3을 리스트 형태로 입력받는다. ans 빈 리스트를 만든다. ans=[]

(오리지날  back 함수)

2.1. ans에 i가 없을 경우에만(중복되지 않기 위하여) i를 append한다. ans=[1] 

2.2. back 재귀함수를 다시 돌린다.

 

(재귀함수)

3.1. ans에 1이 있기 때문에 그 다음수인 2를 append한다. ans=[1,2]

3.2 back 재귀함수를 다시 돌린다.

 

(재귀의 재귀함수)

4.1. ans에 1,2가 있기 때문에 그 다음수인 3을 append한다. ans=[1,2,3]

4.2. back 재귀함수를 돌린다.

4.3. len(ans)가 M값인 3과 같아져서 더이상 탐색하지 않는다. ans.pop() 을 실행하여 마지막에 추가된 수를 삭제한 후 str 형태로 한칸씩 띄어서 출력해준다. ans = 1 2

---------------------

(재귀함수)

5.2. ans에 1이 있고, 2는 테스트했기 때문에 다음수인 3를 append한다. ans=[1,3]

5.3. 모든 숫자를 확인했으므로 print 한다.

---------------------

(오리지날 back 함수)

6.1. ans는 다시 빈 리스트가 되고, 1은 테스트했으니 2부터 다시 시작한다.

# 정답1
N, M = map(int, input().split())
ans = []

def back():
    if len(ans) == M:
        print(" ".join(map(str, ans)))
        return 
    for i in range(1, N+1):
        if i not in ans:
            ans.append(i)
            back()
            ans.pop()
            
back()

 

정답2의 아이디어!

+ 중복 방지를 위하여  False를 n개만큼 채운 visited 리스트를 만든다.

+ visited 값이 False인 경우에만(방문 기록이 없는 경우에만) ans에 append 해주고, 방문기록도 True로 바꿔준다.

+ 똑같이 재귀함수를 돌리면서, pop()해주고, 한 바퀴를 다 돌았으면 다시 방문기록을 False로 리셋해준다.

#정답2
N, M = map(int,input().split())
visited = [False] * (n+1)
ans = []

def back():
    if len(ans) == M:
        print(" ".join(map(str, ans)))
        return 
    for i in range(1,N+1):
        if not visited[i]:
            visited[i] = True
            ans.append(i)
            back()
            ans.pop()
            visited[i] = False
            
back()

 

visited 없이 간단한 재귀함수로 구현 가능

 

def recur(number):
    if number == m:
        print(*arr)
        return
    
    for i in range(1,n+1):
        if i in arr:
            continue # 중복이면 무시
        arr.append(i)
        recur(number+1)
        arr.pop() #반드시 배열 삭제해야함

n, m = map(int,input().split())
arr = []
recur(0)

 

 

정답3의 아이디어!

+ itertools의 permutations 파이썬 내장함수를 이용한다.

itertools.permutations(array,수열길이)

1부터 N까지 중복되지 않은 M개 길이의 수열을 만든다.

 

array = [1, 2, 3]
permutations(array, 2) => [1,2], [1,3], [2,1], [2, 3], [3, 1], [3, 2]
combinations(array, 2) => [1,2], [1,3], [2,3]

#정답3 - 내장함수 이용
import itertools

N, M = map(int, input().split())
arr = itertools.permutations(range(1,n+1),m)
for i in arr:
	print(" ".join(map(str,arr)))

 

공부한 내용  

DFS :  깊이우선탐색. 완전 탐색. 모든 노드 방문

백트래킹 : 불필요한 탐색은 건너뛰고, 이전 단계로 돌아와서 재탐색

 

 

---

레퍼런스

• 백준 백트래킹 15649,15450,15651,15652번은 세트로 공부해야한다.

백트래킹 문제 비교

• • 15649번 중복X 수열
  • 15650번 중복X 시작포인트 지정 수열
  • 15651번 중복O 수열
  • 15652번 중복O 시작포인트 지정 수열
  
  
  • 15649번 [1 2] [1 3] [1 4] [2 1] [2 3] [2 4] [3 1] [3 2] [3 4] [4 1] [4 2] [4 3]
  • 15650번 [1 2] [1 3] [1 4] [2 3] [2 4] [3 4]
  • 15651번 [1 1] [1 2] [1 3] [1 4] [2 1] [2 2] [2 3] [2 4] [3 1] [3 2] [3 3] [3 4] [4 1] [4 2] [4 3] [4 4]
  • 16652번 [1 1] [1 2] [1 3] [1 4] [2 2] [2 3] [2 4] [3 3] [3 4] [4 4]

백트래킹 단계

• 정답 참고 (설명이 잘되어있습니다)

[Python] 백트래킹 (+ DFS와 차이)

ㄴ

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부