백트래킹

DFS

가능한 모든 경로를 탐색하는 알고리즘.

백트래킹이란?

백트래킹은 DFS(Depth First Search; 깊이 우선 탐색)의 방식을 기반으로 불필요한 경우를 배제해가면서 답에 도달할 때까지 계속 탐색하는 전략이다. 즉 가지치기라고 할 수 있다.

 

DFS를 기반으로 두기 때문에 스택을 이용해서 퇴각 하고 다음 탐색을 진행하기 때문에 백트래킹이라 불린다.

 

그래서 백준 15649의 풀이를 소개하며 정리하겠다.

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

 

이 문제는 순열 문제로 4 2 가 주어진다면 [1 2] [1 3] [1 4] [2 1] ... [4 3] 이런식으로 중복되지 않게 하나씩 뽑아야한다. 이 때 바로 백트래킹을 쓰는것이 아주 적합하다.

두 가지 코드를 준비했다.

1.

n,m = map(int, input().split())  visited = [False] * n solved = []  def bt(depth, n, m):     if depth == m:         print(' '.join(map(str, solved)))         return          for i in range(len(visited)):         if not visited[i] :             visited[i] = True             solved.append(i+1)             bt(depth+1, n, m)             visited[i] = False             solved.pop()   # pop : 맨 마지막 요소를 출력하고 solved에서 사라짐               bt(0, n, m)

이해를 쉽게 하기위해 n=4, m=2 를 예로 들면서 하겠다.

입출력은 그대로 받아오고

방문한 곳을 표시하기 위해 visited = [F F F F]를 만들었다.

 

그 다음 만일 depth(깊이)가 m과 일치하면 solved에 저장된 값을 공백만 넣어서 출력 하게 설정했다.

 

이제부터 본격적으로 들어가는데

i = 0

• visited(이제부터 V라고 하겠다) = [T F F F]

• solved = [1]

• bt(1,4,2)
  • i = 0
    • V[0] = True이므로 Pass
  • i = 1
    • V = [T T F F]
    • solved = [1 2]
    • bt(2,4,2)
    • (출력) 1 2
    • V = [T F F F]
    • pop는 맨 마지막를 없애준다. ⇒ solved = [1]
  • i = 2
    • V = [T F T F]
    • sovled = [1 3]
    • bt(2,4,2)
    • 1 3
    • V = [T F F F] / solved = [1]
  • i =3
    • 1 4
    • V = [T F F F] / sovled = [1]

• V = [F F F F] / solved = []

i = 1

• V = [F T F F]

• solved = [2]

• bt(1,4,2)
  • i = 0
    • V = [T T F F]
    • solved = [2 1]
    • ...... 이런식으로 반복

 

이렇게 소괄호 형식으로 쭉 진행 하면 원하는 답이 나온다.

이걸 처음 본다면 당연히 떠올리기가 쉽지 않고 이를 여러 블로그를 찾아봤으나 명확하게 이해하기 코드를작성하기는 쉽지않았다. 이렇게 직접 알고리즘이 돌아가는 과정을 통해서 공부하는 것도 일종의 백트래킹이 아닐까 생각하며 열심히 공부해야겠다.

 

2

n, m = map(int, input().split())  ans = []  def bt():     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)             bt()             ans.pop()              bt()

 

스택으로만 푼 풀이라고 한다.

이건 방문기록을 체크하지않고 ans에 길이로 판단한다.

이도 마찬가지로 위처럼 나열해서 써보면 쉽게 이해가 가능하다.

[1] 을 추가하고 길이 1 ≠ m(2) 이므로 [1 2] 가 들어가고 길이가 맞기 때문에 출력하는 똑같은 과정이다. 밑 풀이를 좀 더 잘 익혀야겟다.

 

Uploaded by Notion2Tistory v1.1.0