[Python] Talking about DFS , backtracking algorithm

 

백트래킹(backtracking)이란? :

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다.

 

😀 DFS와 백트래킹

 

깊이 우선 탐색(DFS)

 

DFS는 가능한 모든 경로(후보)를 탐색한다. 따라서, 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄이지 못한다. 따라서 N! 가지의 경우의 수를 가진 문제는 DFS로 처리가 불가능하다.

 

 

백트래킹(Backtracking)

 

해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아간다. 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적이다.

이것을 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다.

일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 하므로 처리가 불가능 할 수도 있습니다. 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 됩니다.

 

백트래킹은 모두 가능한 경우의 수 중에서 특정 조건만 만족하는 경우만 살펴보는 것

 

 

문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현한다.

 

15649번: N과 M (1)

 

문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 예제 입력 1 복사 3 1 예제 출력 1 복사 1 2 3 예제 입력 2 복사 4 2 예제 ...

가지치기 방식의 코드 풀이

 

 

 

기본적으로 재귀를 사용한다.

n과 m에 두 정수를 입력받고 그 후 s라는 리스트를 선언한 후 dfs() 함수를 정의한다.

dfs() 함수 안에서 리스트 s 요소의 개수가 m 개면 list s를 출력하고 빠져나온다.

그렇지 않으면 반복문을 실행시켜 리스트 s에 i를 추가하고 다시 dfs 함수를 재귀 호출한다.

 

코드가 진행되는 순서는 n과 m을 입력받고 리스트 s를 호출한 후 dfs() 함수를 호출한다.

맨 아래 줄 dfs()를 실행하였을 때 n이 4 m이 2면

 

s가 빈 리스트이므로 if 문은 지나치고

for i in range(1,5):를 실행

s에 1을 추가한 상태로 dfs() 함수를 다시 실행

 

s가 [1]이므로 if 문은 지나치고

for i in range(1,5):를 실행

i가 1이면 if 조건문에 걸려서 지나치고

i가 2일 때 s에 2를 추가한 상태로 dfs() 다시 실행

 

s가 [1,2]이므로 if 문을 만족한다. 그러므로 출력하고 함수를 빠져나와 @ 부분으로 돌아가 s.pop()을 실행하고

i가 3일 때 s에 3을 추가한 상태로 dfs()를 다시 실행을 반복한다.

재귀의재귀의재귀의재귀

 

15650번: N과 M (2)

15650번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 검색 N과 M (2) 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 512 MB 41278 30883 22471 74.346% 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 ...

 

15649번과 똑같지만 오름차순으로 출력해야 한다는 조건만 하나 붙었다.

 

전 문제에서 오름차순 조건만 부여되었다. start라는 변수를 새로 만들었고

재귀 함수를 실행할 때 다음 수를 실행시키도록 dfs(i+1)를 사용하였다.

출력이 되는 s 리스트 안에 [두 숫자] 두 숫자가 있을 때

첫 번째 수 보다 두 번째 수가 무조건 커야 한다.

반복 문의 시작점을 계속 늘려가면서 같은 수를 반복하여 출력할 수 없게 한다.

 

15651번: N과 M (3)

문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 예제 입력 1 복사 3 1 예제 출력 1 복사 1 2 3 예제 입력...

 

같은 수를 여러 번 고를 수 있는 수열이다. 하지만 수열은 사전 순으로 증가하는 순서로

출력해야한다. 위의 두 문제를 적절히 조합하면 풀 수있다.

단지 15649번 문제에서 if 조건문만 없애주면 같은 수를 여러번 고르면서

사전 순으로 증가하는 순서로 두 수를 출력한다.

 

15652번: N과 M (4)

문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A 1 ≤ A 2 ≤ ... ≤ A K-1 ≤ A K 를 만족하면, 비내림차순이라고 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공...

 

첫번째 , 두번쨰, 세번쨰 문제가 다 합쳐진 문제다.

같은수를 여러번 골라도 되지만 고른 수열은 비내림 차순이여야만 한다.

 

 

dfs(1) 을 실행하면 #n=4 m=2라고 가정

for i in range(1,5): 가 실행된다. 같은 수를 여러번 골라도 되지만 비내림 차순이여야 하므로

dfs(i) 를 실행시키면서 재귀 루프를 돌린다.

 

 

 

위에서 말했듯이 백트래킹은 모두 가능한 경우의 수 중에서 특정조건만 만족하는 경우만 살펴보는 것이다. 문제를 보고 내가 원하는 값을 얻기 위해 조건을 잘 거는것이 중요해보인다.