[알고리즘/백트래킹] 15649번 : N과 M(1) - python

링크 : https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

---

• 문제
• 소요시간: 연습 문제

 

---

• 설계하기(접근방법) 

1. 입력받기

n, m 을 입력받는다

 

2. 구현하기

백트래킹 연습문제를 풀었다

 

백트래킹은 재귀 함수를 만들 때 구조화 하는 것이 중요하다

 

탐색 중복 방지를 위해

visited을 선언해줘야 한다.

이 visited는 재귀함수 들어가기 전에 1로 바꿔주고

재귀함수가 끝났을 때 = 종료조건  이면

다시 visited를 0으로 바꾸어준다

 

또한 재귀적으로 탐색을 할 것이기 때문에

종료 조건을 함수에 선언해주어야 한다.

 

그 종료 조건은 함수의 인자가 들어가는 것이

코드가 깔끔해진다

 

 

 

 

 

3. 출력하기

ans list의 내용을 출력한다

 

 

---

• 코드(출력)

def dfs(cnt, arr):
    if cnt == m:
        ans.append(arr)
    for i in range(1, n + 1):
        if visited[i] == 0:
            visited[i] = 1
            dfs(cnt + 1, arr + [i])
            visited[i] = 0

n, m = map(int,input().split())

ans = []
visited = [0 for _ in range(n + 1)]
dfs(0, [])

for i in ans:
    print(*i)

---

• 얻어갈 부분

1. 백트래킹 구현 시 주의해야 할 점들, 구조화 해야할 것들을 배웠다