[알고리즘] 코테 유형 분석 7. 백트래킹

안녕하세요 오늘은 백트래킹 문제 유형에 대해 분석해보는 시간을 갖도록 하겠습니다.

첫 번째 유형은 탐색 중 특정 횟수만큼 특정 조건을 만족하는 경우를 포함하는 경우입니다. 주로 dfs 또는 bfs 탐색 유형과 유사하나 탐색 과정 중 추가 조건을 필요로 하는 문제입니다. 이 경우 탐색의 갈래가 조건의 개수만큼 증가하기 때문에 단순히 탐색을 이어가면 안되고 백트래킹으로 조건을 적용했을 때, 조건을 적용하지 않았을 때 두 가지를 모두 체크해주어야 합니다.

백준 14502(연구소) 문제의 경우 벽을 3개 세워서 바이러스가 퍼질 수 없는 안전 영역의 최댓값을 구하는 문제입니다. 벽을 놓을 수 있는 곳에 백트래킹으로 벽을 3개 세운 후 바이러스를 bfs로 이동시켜 이동이 끝났을 경우 남아 있는 공간의 최댓값을 출력하면 됩니다.

백준 1759(암호 만들기) 문제의 경우 최소 한 개의 모음과 최소 두 개의 자음으로 구성된 증가하는 순서의 암호를 모두 출력하는 문제입니다. 백트래킹으로 이전 원소보다 다음 순서의 원소들을 탐색하여 넘겨주면서 결과값의 모음이 1개 이상, 자음이 2개 이상일 경우 정답 리스트에 추가하는 방식으로 구할 수 있습니다.

백준 1987(알파벳) 문제의 경우 같은 알파벳을 두 번 지날 수 없을 때 최대 몇 칸 이동이 가능한지 구하는 문제입니다. 백트래킹으로 현재까지 방문한 알파벳을 체크하여 넘겨주고 해당 알파벳 탐색이 완료되면 알파벳 체크를 해제하여 다음 알파벳으로 이동하는 방식으로 진행하여 최종 이동값의 최댓값을 갱신합니다.

백준 15684(사다리 조작) 문제의 경우 사다리에 가로선을 최대 3개 추가해서 i번 세로선의 결과가 i가 나오게 할 수 있는 가로선의 최솟값을 구하는 문제입니다. 한 세로선을 기준으로 놓을 수 있는 위치에 모두 가로선을 놓아보고 해제하는 방식으로 백트래킹을 진행하고, 가로선을 전부 추가했을 경우 모든 세로선이 자기 자신으로 도착하는지를 체크하여 그 값의 최솟값을 갱신합니다.

두 번째 유형은 현재 상태를 결정하기 위한 여러 경우의 수가 존재할 경우입니다. 첫 번째 유형과 유사하며 탐색 중 여러 분기가 나뉘고 다시 돌아와서 새로운 분기의 탐색을 진행해야 할 경우 사용됩니다.

백준 1405(미친 로봇) 문제의 경우 로봇의 이동 경로가 단순한 확률을 구하는 문제입니다. 끝까지 갔을 때의 경로 별 확률을 구해야 하기 때문에 매 순간 이동한 확률을 곱하여 하나의 경로 확률을 계산한 후 여러 경로의 총합을 출력합니다. 이 때 매 위치 별 여러 경우의 수가 존재하므로 백트래킹으로 해당 위치로 이동 시 체크하고 이동이 완료되면 체크를 해제하는 식으로 진행합니다.

백준 9663(N-Queen) 문제의 경우 N x N 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 방법을 구하는 문제입니다. 퀸의 특성 상 한 줄에 한 개만 놓을 수 있기 때문에 f(퀸의 세로 위치값) = 퀸의 가로 위치값 형식으로 1차원 배열로 설정할 수 있습니다. 이후 줄 단위로 탐색하면서 이전 줄들의 같은 가로값에 퀸이 존재하거나 대각선상에 퀸이 존재한다면 퀸을 놓지 않고 넘기는 방식으로 백트래킹을 진행합니다.

백준 1799(비숍) 문제의 경우 서로가 서로를 잡을 수 없는 위치에 놓을 수 있는 비숍의 최대 개수를 구하는 문제입니다. 한 번에 처리할 경우 시간 초과가 발생하기 때문에 비숍의 특성 상 서로 다른 색의 칸끼리는 잡을 수 없기 때문에 검정색 이동과 흰색 이동을 나누어 고려합니다. 색깔 별 모든 칸을 탐색하면서 대각선 방향에 다른 비숍이 놓여있다면 놓지 않는 방식으로 백트래킹을 진행합니다.

백준 2580(스도쿠) 문제의 경우 스도쿠 판의 빈칸을 채우는 문제입니다. 백트래킹으로 1부터 9까지 수를 추가해보면서 가로,세로,사각형에 존재한다면 추가하지 않고 존재하지 않는다면 추가 후 다음 위치로 넘어가는 방식으로 백트래킹을 진행합니다.

백준 15683(감시) 문제의 경우 CCTV의 방향을 정해서 사각지대의 최소 크기를 구하는 문제입니다. CCTV의 방향을 백트래킹으로 결정해서 사각지대의 개수를 구하는 방식으로 풀 수 있으며, 백트래킹 로직보다는 CCTV의 감시 범위를 구현하는 것이 조금 더 복잡한 문제입니다.

백준 12100(2048(Easy)) 문제의 경우 2048 보드를 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력하는 문제입니다. 백트래킹으로 보드를 5번 이동시켜 결과값의 최댓값을 출력하며, 이동하는 방향대로 가장 앞쪽에 있는 블록 순서대로 큐에 추가하여 큐에서 값을 꺼내면서 현재 보드의 값이 비어 있는 경우 꺼낸 값을 보드에 추가, 꺼낸 값이 보드의 값과 같을 경우 보드의 값을 X2, 값이 다를 경우 다음 인덱스에 큐에서 꺼낸 값을 추가하는 방식으로 구현할 수 있습니다.

백준 17136(색종이 붙이기) 문제의 경우 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구하는 문제입니다. 현재 위치 기준 최대 어느 범위까지 보유 중인 색종이를 붙일 수 있는지 체크하여 큰 순서대로 색종이를 덮고 해제하는 방식으로 백트래킹을 진행합니다.

백준 10819(차이를 최대로) 문제의 경우 배열에 들어있는 정수 순서를 바꿔 식의 최댓값을 구하는 문제입니다. 이전값을 기준으로 다음 값과의 차를 더해준 다음 총 카운트가 N-1일 경우 최댓값을 비교하여 출력하는 방식으로 백트래킹을 진행합니다.

백준 10597(순열 장난) 문제의 경우 1부터 N까지의 수로 이루어진 순열의 공백을 추가하여 수열을 복구하는 문제입니다. 백트래킹으로 문자열을 각각 한 글자와 두글자씩 나누어 최종적으로 모든 문자열을 나누었을 때 체크 배열의 1부터 지금까지의 최댓값이 모두 체크되어있다면 정답을 출력합니다.

세 번째 유형은 부분 집합 또는 집합 내의 원소들을 뽑는 경우의 수를 구하는 문제입니다. 이 경우는 next_permutation을 이용하거나 조합 알고리즘을 사용하여 풀 수 있는 경우도 있으며, 기본적으로 백트래킹을 사용하여 선택 가능한 원소들을 선택하고 해제하는 방식으로 풀이를 진행합니다.

백준 1182(부분수열의 합) 문제의 경우 크기가 양수인 부분 수열 중 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 문제입니다. 백트래킹으로 모든 경우를 체크하여 진행하고, 현재 인덱스를 같이 넘겨주어 인덱스 이후의 값만을 조회하여 중복 처리를 방지합니다.

백준 6603(로또) 문제의 경우 49개의 수 중 k개의 수를 골라 집합 S를 만든 후 그 수만 가지고 번호를 선택하는 모든 경우의 수를 구하는 문제입니다. 부분수열의 합 문제와 유사하게 백트래킹으로 모든 경우를 체크하고 현재 인덱스를 같이 넘겨주는 방식으로 풀 수 있습니다. 또한 조합 알고리즘을 사용하여 49개의 수 중 k개를 순서 상관없이 뽑는 경우의 수를 구하는 방식으로 풀 수 있습니다.

백준 10974(모든 순열) 문제의 경우 1부터 N까지 이루어진 순열을 사전순으로 출력하는 문제입니다. 백트래킹으로 현재 방문한 곳을 체크한 후 탐색이 완료되면 체크를 해제하여 다시 탐색하는 방식으로 문제를 풀 수 있습니다.