백트래킹(BackTracking) - 되추적
정답을 찾는 도중 절대로 정답이 될 수 없다고 판단되면, 되돌아가서 정답을 다시 찾아가는 방법
Back(뒤로 가서) +Tracking(찾는다)
가능성이 없는 곳을 알아보고 되돌아가는 것
- 문제마다 효율이 달라지므로 시간 복잡도를 특정해서 정의하기 어려움
- 정답이 될 가능성이 없는 대상을 배제할 수 있어 완전 탐색보다는 효율이 좋음
재귀적으로 문제를 해결함 → 현재 재귀를 통해 확인 중인 상태가 제한 조건에 위배 되는지 판단하고, 위배가 되면 해당 상태를 제외하고 다음 단계로 넘어감- 조건에 부합하지 않으면 이전 수행으로 돌아가야 하는 부분에서
DFS와 유사함 → 그래서 보통DFS를 통해 구현함 -BFS보다 편함 가지치기: 더 이상 탐색할 필요가 없는 상태를 제외하는 것
유망하지 않은 것들은 쳐다보지도 않는 방식이다..
유망주가 아니면 탈락이라니 너무하다
이제 문제를 풀어보자
백준 15686번 - 치킨 배달
문제
크기가 N x N 도시
빈 칸,치킨집,집중 하나로 이루어져 있음
- (r, c) 형태
- r은 행, c는 열
0: 빈 칸,1: 집,2: 치킨집
치킨거리: 집과 가장 가까운 치킨집 사이의 거리 → 각각의 집은치킨거리를 가지고 있음
- |r1 - r2| + |c1 - c2|
M: 가장 수익을 많이 낼 수 있는 치킨집의 개수
도시에 있는 치킨집 중에서 최대
M개를 고르고, 나머지 치킨집은 모두 폐업
도시의치킨거리가 가장 작은 경우를 구하기
입력
첫째 줄 : N과 M이 주어짐
둘째 줄 ~ N개의 줄 : 도시의 정보가 주어짐
도시의 정보는 0,1,2로 이루어져 있고, 0은 빈칸, 1은 집, 2는 치킨집을 의미
집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재
치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다
출력
첫째 줄에 폐업시키지 않을 치킨집을 최대 M개 골랐을 때, 도시의 치킨 거리의 최솟값 출력
풀이
이번에도 역시 어렵다. 조만간 알고리즘 폐관 수련에 들어가야할 것 같다
또 다른 블로그 참고함 흑흑
우선 집과 치킨집이 아닌 빈칸은 쓸모가 없어서 입력을 받을때 house, chicken 배열을 만들어 집과 치킨집인 경우의 좌표를 각각의 배열에 저장해준다.
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
int temp = Integer.parseInt(st.nextToken());
if (temp == 1) {
house.add(new int[] {i, j}); // 집 좌표 집어넣기
}
if (temp == 2) {
chicken.add(new int[] {i, j}); // 치킨집 좌표 집어넣기
}
}
}그리고 이제 백트래킹 방식이다
이해하는데 한참 걸렸다.
static void back(int depth, int start) {
if (depth == m) { // 선택한 치킨집이 m개
int sum = 0;
for (int[] h : house) {
int min = Integer.MAX_VALUE;
for (int[] c : choice)
int d = Math.abs(h[0] - c[0]) + Math.abs(h[1] - c[1]); // 치킨거리
min = Math.min(d, min); // 최솟값 찾기
}
sum += min;
}
result = Math.min(result, sum);
return;
}
for (int i = start; i < chicken.size(); i++) {
choice.add(chicken.get(i)); // 현재까지 선택한 치킨집 목록
back(depth + 1, i + 1);
choice.remove(choice.size() - 1); // 마지막으로 추가한 치킨집 제거
}
}이렇게만 보면 이해가 잘 안되니까 한번 예시를 들어보자
치킨집 [A, B, C, D] 가 있고 m = 2 라고 가정
back(0,0)
choice = []
A -> back(1,1)
choice = [A]
start = 1
B -> back(2,2)
choice = [A, B]
depth == m (2) 이므로 치킨거리 계산함
계산하고 B remove → choice = [A]
C -> back(2,3) - 다시 depth = 1로 돌아옴
choice = [A, C]
depth == m 치킨거리 계산
계산하고 C remove → choice = [A]
D -> back(2,4)
choice = [A, D]
depth == m 치킨거리 계산
계산하고 D remove → choice = [A]
A도 remove → choice = [B]
이제 다음 치킨인 B 부터 시작
반복
이렇게 반복을 하면서 치킨 거리를 계속해서 result에 저장을 해주게 된다!
이해가 되려나 모르겠다.
사실 나도 아직 완전히 이해는 못한것 같음
이번주 알고리즘 끗
