해커를 꿈꾸는 개발자

파이썬 / 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)

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

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

문제

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

풀이

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

2. 재귀함수를 이용하고, 그 재귀함수에는 숫자의 개수를 전달하여, 그 개수가 m개 이면 리스트의 내용을 출력하도록 합니다.

3. 재귀함수에서 개수가 m개가 아니라면, n까지의 숫자들을 확인하고, 방문하였는지 체크하여, 방문하지 않은 숫자를 기준으로 가지치기(재귀함수 호출)를 합니다.

N = 4, M = 3인 경우, 위와 같이 깊이우선탐색의 순서대로 방문하여, 리스트를 출력하는 방식으로 합니다. 

위 그림에서 2, 3, 4가 루트인 경우에도 동일한 방식으로하여 구하면 됩니다. 

전체 코드

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

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

    for i in range(N):
        if not visited[i]:
            visited[i] = True
            lst.append(i+1)
            dfs(depth+1)
            visited[i] = False
            lst.pop()