[백준/python] 백트래킹 전체 풀이(15단계)

숏코딩보다는 백트래킹, BackTracking 을 이용하여 문제가 원하는 목적에 맞게 풀이해보았다.

목차

 

N과 M (1)(#15649)

• Problem

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

 

• Hint

일반적인 백트래킹 방법을 이용하였다.

 

• Solution

백트래킹을 이용한 풀이

n, m = map(int, input().split())
res = []

def BackT(depth):
    if depth == m:
        for i in res:
            print(i, end=' ')
        print()
        return
    for i in range(1, n + 1):
        if i not in res:
            res.append(i)
            BackT(depth + 1)
            res.pop()

BackT(0)

---

 

 

N과 M (2)(#15650)

• Problem

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다.

 

• Hint

중복이 되는걸 출력하지 않는 방법을 생각해보자.

 

• Solution

nod 변수를 이용한 풀이

n, m = map(int, input().split())
res = []


def BackT(depth, nod):
    if depth == m:
        for i in res:
            print(i, end=' ')
        print()
        return
    for i in range(nod, n + 1):
        if i not in res:
            res.append(i)
            BackT(depth + 1, nod)
            res.pop()
        nod += 1


BackT(0, 1)

nod 변수를 추가하여 nod 번째 수 이후로만 반복이 되도록 하였다.

---

 

 

N과 M (3)(#15651)

• Problem

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다.

 

• Hint

기존 백트래킹에서는 if ~not in 으로 중복됨을 막아서 append 하였다.

 

• Solution

백트래킹을 이용한 풀이

n, m = map(int, input().split())
res = []


def BackT(depth):
    if depth == m:
        for i in res:
            print(i, end=' ')
        print()
        return
    for i in range(1, n + 1):
        res.append(i)
        BackT(depth + 1)
        res.pop()


BackT(0)

기존 백트래킹에서 인자 추가시에 리스트 조건문을 없애주었다.

---

 

 

N과 M (4)(#15652)

• Problem

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

 

• Hint

N과M (2) 풀이를 참고해보자

 

• Solution

nod 변수를 이용한 풀이

n, m = map(int, input().split())
res = []


def BackT(depth, nod):
    if depth == m:
        for i in res:
            print(i, end=' ')
        print()
        return
    for i in range(nod, n + 1):
        res.append(i)
        BackT(depth + 1, nod)
        res.pop()
        nod += 1


BackT(0, 1)

조건문을 없애주고 nod 인자를 넣어주었다.

---

 

 

N-Queen(#9663)

• Problem

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

 

• Hint

dfs 로 n번째 줄까지 depth+1를 하면서 반복을 해주어 전체를 탐사하면서 무엇을 해줘야할지 생각해본다.

 

• Solution

백트래킹을 이용한 풀이

n = int(input())
addlist = [0]*n
res = 0


def checkvalid(i):
    j = 0
    while (j < i):
        if (addlist[j] == addlist[i] or abs(addlist[j]-addlist[i]) == i-j):
            return False
        j += 1
    return True


def nqueen(x):
    global res
    if x == n:
        res += 1
        return
    for i in range(n):
        addlist[x] = i
        if checkvalid(x):
            nqueen(x+1)


nqueen(0)
print(res)

dfs 로 n번째 줄까지 depth+1를 하면서 반복을 해주고 다음 dfs를 넘어갈 조건으로 1부터 n까지의 가로로의 좌표를 탐색하면서 따로 만든 유효성 검사 함수를 통하여 같은 열에 중복이 되는지 또한 대각선에도 중복이 되는지를 확인하여 중복이 되지않는 경우에 n 번째 줄에 i를 추가하고 끝낸다.

---

 

 

 

스도쿠(#2580)

• Problem

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다. 또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다. 이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다. 게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

 

• Hint

스도쿠의 특징을 잘 생각해보면 같은 열, 같은 행, 같은 사각형 내를 유효성검사를 해야한다는 사실을 이용해보자

 

• Solution

백트래킹을 이용한 풀이

getlist = []
hole = []

for i in range(9):
    getlist.append(list(map(int, input().split())))

for y in range(9):
    for x in range(9):
        if getlist[y][x] == 0:
            hole.append([y, x])


def sudoku(depth):
    if depth == len(hole):
        for i in range(9):
            print(*getlist[i])
        exit(0)
    for n in range(1, 10):
        hx = hole[depth][1]
        hy = hole[depth][0]

        if rowcheck(hy, n) and columncheck(hx, n) and squarecheck(hx, hy, n):
            getlist[hy][hx] = n
            sudoku(depth+1)
            getlist[hy][hx] = 0


def rowcheck(hy, n):
    for i in range(9):
        if getlist[hy][i] == n:
            return False
    return True


def columncheck(hx, n):
    for i in range(9):
        if getlist[i][hx] == n:
            return False
    return True


def squarecheck(hx, hy, n):
    cx = hx//3
    cy = hy//3
    for i in range(3):
        for j in range(3):
            if getlist[cy*3+j][cx*3+i] == n:
                return False
    return True


sudoku(0)

pypy3로 밖에 문제 해결이 안된다. python3으로 해결을 하려면 더욱 경우를 쪼개어서 불필요한 반복을 줄여야되더라..

 

 

hole 함수를 이용하는것이 반복을 줄이는 방법이었다 (남의 코드를,, 보고야 말았다. 골드 이상의 문제는 아무래도 풀릴때까지 잡고 있는것보다 보고 배우는 것이 좋아보인다.)

 

나머지는 열과 행 그리고 사각형내의 유효성을 검사하여 추가하는 것을 dfs 를 통해서 구현해보자.

---

 

 

연산자 끼워넣기(#14888)

• Problem

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개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

 

• Hint

수를 그대로 두고 사칙연산자를 배치해보자.

 

• Solution

백트래킹을 이용한 풀이

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
oper = list(map(int, input().split()))

val = a[0]
valMax = -int(1e9)
valMin = int(1e9)


def dfs(depth):
    global val, valMax, valMin

    if depth == n:
        if val > valMax:
            valMax = val
        if val < valMin:
            valMin = val
        return

    for i in range(4):
        temp = val
        if oper[i] > 0:
            if i == 0:
                val += a[depth]
            elif i == 1:
                val -= a[depth]
            elif i == 2:
                val *= a[depth]
            else:
                if val >= 0:
                    val //= a[depth]
                else:
                    val = (-val//a[depth])*-1

            oper[i] -= 1
            dfs(depth+1)
            val = temp
            oper[i] += 1


dfs(1)
print(valMax)
print(valMin)

 

 

dfs를 이용하여 다음 조합으로 이동하게 하였고 oper 리스트에 차례대로 저장한 각 연산자의 개수를 확인한 후 이를 중복조합 형태로 반복시켰다. (각 자리수를 선택하면 그 자리수에 할당된 수치가 1 줄어드는 방식) 또한 선택된 연산자로 조건문 안에서 최종 값 val 에 계산도 함께 해주어 최종적으로는 저장되어있던 최대값과 최소값과 비교하여 더 크거나 작은 값인 경우에 할당되어있던 최대값 최소값을 재할당 해주었다.

---

 

 

스타트와 링크(#14889)

• Problem

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다. N=4이고, S가 아래와 같은 경우를 살펴보자. i\j 1 2 3 4 1 1 2 3 2 4 5 6 3 7 1 2 4 3 4 5 예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다. 스타트 팀: S12 + S21 = 1 + 4 = 5 링크 팀: S34 + S43 = 2 + 5 = 7 1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다. 스타트 팀: S13 + S31 = 2 + 7 = 9 링크 팀: S24 + S42 = 6 + 4 = 10 축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

 

• Hint

dfs로 어떤 것을 구해야하는지 잘 생각해보자. 또한 저장된 리스트의 값들을 최대한 반복을 적게하면서 더하는 방법을 생각해보자.

 

• Solution

백트래킹을 이용한 풀이

import sys
input = sys.stdin.readline
stat = []
start = []
link = []
n = int(input())
for i in range(n):
    stat.append(list(map(int, input().split())))

valMin = float('Inf')


def dfs(index):
    global valMin
    if index == n // 2:
        startSum = 0
        linkSum = 0
        for i in range(0, n):
            if i not in start:
                link.append(i)
        for i in range(0, n // 2 - 1):
            for j in range(i+1, n // 2):
                startSum += stat[start[i]][start[j]] + stat[start[j]][start[i]]
                linkSum += stat[link[i]][link[j]] + stat[link[j]][link[i]]
        diff = abs(linkSum-startSum)
        if valMin > diff:
            valMin = diff
        link.clear()
        return
    for i in range(n):
        if i in start:
            continue
        if len(start) > 0 and start[len(start)-1] > i:
            continue
        start.append(i)
        dfs(index + 1)
        start.pop()


dfs(0)
print(valMin)

중복이 없는 조합을 통해서 n 중에서 n/2 개를 고르는 것을 dfs 를 돌린후에

 

저장된 전체 arr에서 각각의 start 와 link로 구별하여 더해주어야하는데 조합을 구하는 알고리즘 처럼 1,2 를 들렸다면 2,1 을 들르지 않도록 처음 숫자가 뒷쪽의 숫자보다 크면 안된다 라는 조건을 추가하여 알고리즘의 시간초과를 막는다.