[백준] python 파이썬-15649 N과 M (1)

 

안녕하세요. 문님입니다.

 

오늘 풀어볼 문제는 [백준 N과 M(1) - 15649] 입니다.

 

15649번: N과 M (1) (acmicpc.net)

15649번: N과 M (1)

 

1. Problem

 

 

 

2. Thinking

 

백트래킹 문제이다.

백트래킹 구현: 해를 구하는 도중에 해가 아니면 직전으로 돌아가 다른 방법으로 해를 구하는 기법(가지치기)

재귀를 이용하여 풀게 되는데 더이상 탐색을 할 필요가 없다면 재귀를 멈추게 된다.

 

dfs = depth first search

깊이를 우선으로 탐색하는 방법을 사용한다.

다른 방법으로는 bfs(breadth first search, 너비 우선 탐색)가 있다.

 

dfs 함수를 만들어서 실행한다.

  1.  visited = [False] * (n+1)

방문 여부를 저장하는 visited

방문 여부를 체크할 요소들의 중복을 제거하기 위해 n+1 개의 False를 선언

if,  방문한 적이 있다면 visited[i] = True, 방문한 적이 없다면 visited[i] = False

 

  2. dfs 함수

if len(out) == m

수열의 길이인 m과 out 리스트의 길이(요소의 개수)가 같다면 out 리스트를 출력

그러나 len(out) == m가 아니라면 for문이 실행된다.

 

  3. for문 

초반에 False로 선언한 visited[i] 값을 True로 일시적으로 변경하는 것은 방문 여부 탐색을 시작한다는 것을 뜻한다.

out 리스트에 i 값을 추가 = 탐사 내용 추가

dfs() dfs 함수 재귀 호출

out.pop() : 탐사한 값을 제거

   pop() 함수: 가장 선두에 있는 값을 출력과 동시에 제거하는 함수

visited[i] = False : True로 일시적으로 변경된 값을 False로 변경, 깊이 탐사 완료

 

3. Code

def DFS():
    if len(out) == M:
        print(*out)
        return

    for i in range(1, N+1):
        if visited[i]:  
            continue
        visited[i] = True
        out.append(i)
        DFS()  
        out.pop() 
        visited[i] = False


        
N, M = map(int, input().split())  # N:주어진 수, M:수열의 길이
out = []  
visited = [False] * (N+1) 
DFS()

 

4. Add

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

map(str, out)

map(a,b) 함수는 다수의 b값들을 a의 형태로 한 번에 변환시켜주는 함수이다.

ex. 입력 받을 n,m 값을 모두 정수 형태로 변환