해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 / 14888  연산자 끼워넣기 - 백트래킹

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

문제

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.
우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.
예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.
1+2+3-4×5÷6
1÷2+3+4-5×6
1+2÷3×4-5+6
1÷2×3-4+5+6
식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.
1+2+3-4×5÷6 = 1
1÷2+3+4-5×6 = 12
1+2÷3×4-5+6 = 5
1÷2×3-4+5+6 = 7
N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

풀이

1. 백트래킹을 이용하여 풀 수 있는 문제입니다.

2. 최대, 최소의 값을 위한 수식을 찾기 위해, 가지치기 없이 끝까지 탐색을 마쳐야 합니다.

3. idx == N이 되면, 현재값이 최소, 최대인지 검사하고, 재귀를 종료합니다.

전체 코드

import sys

N = int(input())
nums = list(map(int, input().split()))

a, b, c, d = map(int, input().split())
max_ans, min_ans = -sys.maxsize - 1, sys.maxsize

def solution(sum, idx, add, sub, mul, div):
    global max_ans, min_ans
    if idx == N:
        max_ans = max(max_ans, sum)
        min_ans = min(min_ans, sum)
        return

    if add > 0:
        solution(sum + nums[idx], idx + 1, add - 1, sub, mul, div)
    if sub > 0:
        solution(sum - nums[idx], idx + 1, add, sub - 1, mul, div)
    if mul > 0:
        solution(sum * nums[idx], idx + 1, add, sub, mul - 1, div)
    if div > 0:
        solution(int(sum / nums[idx]), idx + 1, add, sub, mul, div - 1)


solution(nums[0], 1, a, b, c, d)
print(max_ans)
print(min_ans)

파이썬 / BOJ 백준 / 2580 스도쿠 - 백트래킹

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

문제

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

풀이

1. 백트래킹을 이용하여 풀 수 있는 문제입니다.

2. 우선 0인 부분만 찾고, 그 부분을 하나씩 들어갈 숫자를 찾는데, 재귀함수를 이용해 진행합니다.

3. 숫자를 찾을 때에는 행, 열, 3x3 박스 안에서 검사하여 찾습니다.

4. 검사하여 들어갈 숫자를 찾으면, 그 다음 0인 부분도 동일하게 찾습니다.

5. 들어갈 숫자가 하나도 없다면, 그 이전에 넣었던 숫자를 다른 숫자로 변경합니다.

전체 코드

board = [list(map(int, input().split())) for _ in range(9)]
zeros = [(i, j) for i in range(9) for j in range(9) if board[i][j] == 0]


def is_promising(i, j):
    promising = [1, 2, 3, 4, 5, 6, 7, 8, 9]

    # 행열 검사
    for k in range(9):
        if board[i][k] in promising:
            promising.remove(board[i][k])
        if board[k][j] in promising:
            promising.remove(board[k][j])
    i //= 3
    j //= 3
    for p in range(i * 3, (i + 1) * 3):
        for q in range(j * 3, (j + 1) * 3):
            if board[p][q] in promising:
                promising.remove(board[p][q])

    return promising


flag = False

def dfs(x):
    global flag

    if flag:  # 이미 답이 출력된 경우
        return

    if x == len(zeros):
        for row in board:
            print(*row)
        flag = True
        return

    else:
        (i, j) = zeros[x]
        promising = is_promising(i, j)
        for num in promising:
            board[i][j] = num
            dfs(x + 1)
            board[i][j] = 0
dfs(0)

파이썬 / BOJ 백준 / 9663 N-Queen - 백트래킹

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

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

풀이

1. 백트래킹을 이용하여 풀 수 있는 문제입니다. 백트래킹의 가장 기초적인 문제라 할 수 있습니다.

2. 한 줄에 두 개 들어가는 게 불가능하기 때문에, 행과 열 중에 하나를 정해서 기준점 잡고 백트래킹에 들어갑니다.

3. 열을 기준점으로 잡은 경우에 col[x]에 행의 번호를 넣습니다. 이때, col[x]에 행의 번호를 넣었을 때, 다른 퀸이 공격할 수 있는지 check합니다. 퀸이 공격할 수 없는 위치라면, dfs(x+1)함수를 호출하여, 그 다음 열에 대해서 같은 작업을 반복합니다.

4. 재귀함수에서 전달인자의 크기가 N이면 결과값으로 카운팅 합니다.

전체 코드

def check(x):
    for i in range(x):
        if col[x] == col[i] or abs(col[i]-col[x]) == x-i:
            return False
    return True

def dfs(x):
    global res
    if x == n:
        res += 1
        return
    for i in range(n):
        col[x] = i
        if check(x):
            #print(x, " ", i)
            dfs(x+1)

n = int(input())
res = 0
col=[0]*15

dfs(0)
print(res)

파이썬 / BOJ 백준 / 15652번 N과 M(4) - 백트래킹

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

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 M개를 고른 수열
- 같은 수를 여러 번 골라도 된다.
- 고른 수열은 비내림차순이어야 한다.
길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

풀이

1. 백트래킹을 이용하여 풀 수 있는 문제입니다. 백트래킹의 가장 기초적인 문제라 할 수 있습니다. 15651의 문제에서 약간 변형된 문제입니다.

https://zidarn87.tistory.com/329

2. 중복이 가능하기 때문에, 재귀 시 i를 넘겨주어 같은 수도 고를 수 있게 합니다.

3. 비내림차순이기 때문에 index 적용합니다. for 문은 index부터 시작하여, 비내림차순으로 출력하도록 합니다.

전체 코드

N, M = map(int, input().split())
lst = []

def dfs(cnt, index):
    if cnt - 1 == M:  # 탈출 조건
        print(' '.join(map(str, lst)))
        return

    for i in range(index, N+1):
        lst.append(i)
        dfs(cnt+1, i)
        lst.pop()
dfs(1, 1)