우주의 IT 소행성

• 정보·통신 생성 시스템에서, 문제의 해답을 구하기 위한 추론 제어 방식의 하나. 규칙을 적용하여 얻은 결과가 틀리면 그 규칙을 적용한 다음부터 현재까지의 결과를 무시하고 처음으로 돌아가서 다른 규칙을 선택하여 다시 시도한다.

-표준 국어 대사전에서 발췌-

일반적으로 재귀함수에서 더 이상의 호출이 의미 없을 때, 중간에 재귀함수를 중단시키는 알고리즘을 의미한다.

백준 14889번, 15661번 스타트 링크 문제를 통해 백트래킹에 대해 알아보자.

1 ~ N까지의 번호 중 2개의 팀을 각 N/2명으로 나누어야 한다.

2. 이때 S[I][J] = i번 사람과 j번 사람이 같은 팀일 때 팀에 더해지는 능력치이다.

3. 팀의 능력치 : 팀에 속한 모든 s[i][j]쌍의 합이다.

4. 문제 요구 사항 : 두 팀의 능력치를 구하고 차이의 최소를 구하라

해당 문제를 요구 사항에 맞게 코딩하면

def go(index, first, second):
    if index == n:
        if len(first) != n // 2:
            return -1
        if len(second) != n // 2:
            return -1
        t1 = 0
        t2 = 0
        for i in range(n // 2):
            for j in range(n // 2):
                if i == j:
                    continue
                t1 += s[first[i]][first[j]]
                t2 += s[second[i]][second[j]]
        diff = abs(t1 - t2)
        return diff
    ans = -1

    t1 = go(index + 1, first + [index], second)
    if ans == -1 or (t1 != -1 and ans > t1):
        ans = t1
    t2 = go(index + 1, first, second + [index])
    if ans == -1 or (t2 != -1 and ans > t2):
        ans = t2
    return ans


n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]
print(go(0, [], []))

이런 코드가 나오게 된다.

index : 사람을 어떤 팀에 넣을지 (스타트 팀, 링크 팀)

first : 1번 팀, second : 2번 팀

index == n 일 경우 함수 종료

first나 second의 팀 수가 n//2를 넘어가게 되면(딱 절반이어야 하는데 넘어갈 때)  -1 반환

하지만 index == n 일때 

first나 second가 n//2가 아님을 검사하게 되면

결국 index는 n 만큼의 재귀를 실행하게 된다. 

만약 first나 second가 (n이 8일 때) 5를 넘었을 때 바로 종료한다면 더 시간을 단축할수 있을 것이다.

이때를 위해 백트래킹 방법이 사용된다.

재귀 중간에, 특정 상황(의미 없는 재귀가 반복된다고 판단)에서 재귀를 종료시키는 구문을 넣어준다.

def go(index, first, second):
    if index == n:
        if len(first) != n // 2:
            return -1
        if len(second) != n // 2:
            return -1
        t1 = 0
        t2 = 0
        for i in range(n // 2):
            for j in range(n // 2):
                if i == j:
                    continue
                t1 += s[first[i]][first[j]]
                t2 += s[second[i]][second[j]]
        diff = abs(t1 - t2)
        return diff
    ans = -1
    if len(first) > n // 2:
        return -1
    if len(second) > n // 2:
        return -1

    t1 = go(index + 1, first + [index], second)
    if ans == -1 or (t1 != -1 and ans > t1):
        ans = t1
    t2 = go(index + 1, first, second + [index])
    if ans == -1 or (t2 != -1 and ans > t2):
        ans = t2
    return ans


n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]
print(go(0, [], []))

따라서 중간에

if len(first) > n // 2:
    return -1
if len(second) > n // 2:
    return -1

를 넘어줌으로써, 시간을 절약시킬 수 있다.

MAX = 1000000
check = [0] * (MAX + 1)
check[0] = check[1] = True
prime = []

for i in range(2, MAX + 1):
    if not check[i]:
        prime.append(i)
        j = i + i
        while j <= MAX:
            check[j] = True
            j += i
prime = prime[1:]

while True:
    n = int(input())
    if n == 0:
        break
    for p in prime:
        if (n - p) < 0:
            print("Goldbach's conjecture is wrong.")
            break
        elif not check[n - p]:
            print(f'{n} = {p} + {n - p}')
            break

에라토스테네스의 체을 이용해 MAX인 1000000 까지의 소수의 배수들을 모두 걸러주고 PRIME 리스트를 만들어준다.

A + B = N ( A, B, C 는 모두 소수) 라는 골드바흐의 추측 공식을 기억해보자.

A가 P라고 할때 P + B = N 이고

B = N - P가 된다.

따라서 prime을 하나씩 꺼내주면서 n-p를 찾아주면 된다.

n - p가 음수일 경우 goldbach's conjecture is wrong을 출력해준다.

from collections import deque
import sys
input = sys.stdin.readline

# 좌, 우, 상, 하, 좌상대각, 우상대각, 좌하대각, 우하대각
move_x = [0, 0, -1, 1, -1, -1, 1, 1]
move_y = [-1, 1, 0, 0, -1, 1, -1, 1]


def bfs(i, j):
    graph[i][j] = 0
    queue = deque()
    queue.append((i, j))

    while queue:
        x, y = queue.popleft()
        for i in range(8):
            nx = move_x[i] + x
            ny = move_y[i] + y
            if 0 <= nx < h and 0 <= ny < w and graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))

while True:
    count = 0
    w, h = map(int, input().split())
    if w == h == 0:
        break
    graph = [list(map(int, input().split())) for _ in range(h)]

    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1:
                bfs(i, j)
                count += 1
    print(count)

1. 맵의 모든 부분을 돌면서 육지일 때 너비 우선 탐색을 실행 ( 카운트 + 1 )

2. 너비 우선 탐색시 인접한 모든 섬을 방문하여 0 으로 만듦

3. 섬이 이어지지 않을 경우 다시 1로 돌아감

4. 다시 섬을 구해서 그 섬과 이어진 부분을 전부 0 으로 만듦 ( 카운트 + 1 )

... 위를 반복해서 이어진 섬을 찾는 것

KEY POINT > 이미 탐색된 섬 전체를 0으로 만들어 메인에서 bfs 하지 않게 만들어야 함

from collections import deque

def bfs(s, t):
    queue = deque()
    queue.append((s, t, 0))
    visited = [-1] * (200)

    while queue:
        s, t, count = queue.popleft()
        if s <= t and visited[s] == -1:
            queue.append((s * 2, t + 3, count + 1))
            queue.append((s + 1, t, count + 1))
            if s == t:
                return count


c = int(input())
for i in range(c):
    s, t = map(int, input().split())
    print(bfs(s, t))

bfs를 통해 풀 수 있는 문제.
매 분기마다 A의 발차기를 할지, B의 발차기를 할지
모든 분기를 저장하여 가장 빠른 s == t에 도달한 count를 출력하면 끝.