[BOJ 15649] N과 M(1) 파이썬 풀이

문제

​
​

백트레킹

💡 백트레킹

해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾아가는 기법
(모든 경우의 수를 탐색하는 대신, 조건을 걸어 유망한 경우로 탐색하기)

불필요한 부분을 줄이고 최대한 올바른 쪽으로 간다!
→ 특정한 조건을 만족하는 경우만 살펴보는 것

​

깊이 우선 탐색(DFS) 과의 차이점

DFS는 가능한 모든 경로를 탐색하므로 경우의 수를 줄이지 못한다.
N! 가지의 경우의 수를 가진 문제는 DFS로 풀지 못함!

​

문제풀이 팁

조건문 등을 걸어서 답이 절대 될 수 없는 상황을 정의
→ 그러한 상황일 때 탐색 중지, 그 이전으로 돌아가 다른 경우 탐색하게끔

​
​

코드

def backTracking () :
    if len(s) == m : # m개가 쌓이면 출력
        print(' '.join(map(str, s)))
        return

    for i in range(1, n+1) :
        if visited[i] :
            continue
        visited[i] = True
        s.append(i)
        backTracking()
        s.pop()
        visited[i] = False


n, m = map(int, input().split())
s = []
visited = [False] * (n+1)

backTracking()

​
​

풀이

1. 문제 조건인 '1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열'을 위해 if문을 걸어주었다.
2. 이후에는 첫번째에 쓰인 수를 피해 중복 없이 수열을 만들어야하므로 visited 배열을 사용했다. 이미 방문한 수일 경우 if문을 통해 continue되고, 방문하지 않은 경우 s배열에 해당 수(i)를 추가해준다.
3. 다음 줄에서 재귀방식으로 다시 backTracking 함수를 부르고 위 내용을 반복한다.
4. 첫번째 if문에서 s배열에 m개만큼 숫자가 쌓이면 이를 출력한 후 return하여 함수를 빠져나온다.
5. 이를 반복한다.

​

상세 풀이

n = 4, m = 2일 경우 실행될 코드를 한 줄씩 풀어본다면 아래와 같다.

n = 4
m = 2
visited = [False, False, False, False, False]

backtracking() ->
	len(s) => 0. if문 넘어감
	i = 1
		visited => False이므로 if조건 해당 안됨
		visited[1] = True
		s.append(1)
		backTracking()
			len(s) => 1. if문 넘어감
			i = 1
				visited[1] => True이므로 if조건 해당됨
			i = 2
				visited => False이므로 if조건 해당 안됨
				visited[2] = True
				s.append(2)
				backTracking()
					len(s) => 2. if문 들어감
						print -> “1 2”
						return
				s.pop() =====> 1
				visited[2] = False
			i = 3
				visited[3] => False이므로 if조건 해당 안됨
				visited[3] => True
				s.append(3) ========> 1 3
				backTracking()
					len(s) => 2. if문 들어감
						print -> “1 3”
						return
				s.pop() ======> 1
				visited[3] = False =====> [False, true, false, false, false]
			i = 4
				visited[4] => False이므로 if조건 해당 안됨
				visited[4] => True
				s.append(4) ========> 1 4
				backTracking()
					len(s) => 2. if문 들어감
						print -> “1 4”
						return
				s.pop() ======> 1
				visited[4] = False =====> [False, True, False, False, False]
		s.pop() ======> []
		visited[1] = False ========> [False, False, False, False, False]
	i = 2
		visited => False이므로 if조건 해당 안됨
		visited[2] = True
		s.append(2) ========> [2]
		backTracking()
			len(s) => 1. if문 넘어감
			i = 1
				visited[1] => False이므로 if조건 해당안됨
				visited[1] = True
				s.append(1) ========> [2, 1]
				backTracking()
					len(s) => 2. if문 들어감
						print -> “2 1”
						return
				s.pop() =====> 2
				visited[1] = False
			i = 2
				visited => True이므로 if조건 해당 됨
			i = 3
				.
                .
                .

​
​

결과