[알고리즘] 백트래킹 2 (Backtracking)

개인 공부 후 자료를 남겨놓기 위한 목적이므로,
생략되거나 오류가 있을 수 있음을 알립니다.

해당 필기는

1. 기존 백트래킹 변형

앞선 포스팅에서 우리는 3가지 형태의 템플릿을 보았다.

이번엔 이를 다른 형태로 변환해 사용해보도록 하자.

이전의 백트래킹(1, 2, 3 템플릿)은 cur가 채운 개수 기준이었다.

새로운 백트래킹 형식은 다음과 같다.

여기서의 cur는 여태까지 본 원소의 개수, cnt는 고른 원소의 개수가 된다.

이를 실제 문제풀이 형식에 맞추어 변형해보면 다음과 같이 바뀐다.

만약 위 코드를 응용해, 3개 이하의 부분수열만을 출력하고 싶다면 다음과 같이 할수도 있다.

이제는 문제를 보면서 위 백트래킹 형식을 활용해보도록 하자.

2961번: 도영이가 만든 맛있는 음식

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

2961번: 도영이가 만든 맛있는 음식

첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은

www.acmicpc.net

for문을 이용한 백트래킹보다 훨씬 깔끔하게 코드가 나오는 것을 확인할 수 있다.

2차원 배열에서의 백트래킹은 어떻게 해야할까?

다음의 문제를 보며 알아보자.

16925번 : 매직 스퀘어로 변경하기

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

16945번: 매직 스퀘어로 변경하기

1부터 N2까지의 수가 하나씩 채워져 있는 크기가 N×N인 배열이 있고, 이 배열의 모든 행, 열, 길이가 N인 대각선의 합이 모두 같을 때, 매직 스퀘어라고 한다. 크기가 3×3인 배열 A가 주어졌을 때,

www.acmicpc.net

2차원 백트래킹의 핵심은 한 행이 끝나면 행을 0으로 바꾸고 열을 +1 하는 것이다.