[알고리즘] 완전탐색과 백트래킹 - N과 M

완전탐색

- 모든 경우의 수를 계산하는 방법

 

백트래킹

- 주어진 문제에서 답을 구하기 위해 가능한 경우의 수를 탐색하는 방법

- 해를 찾는 도중에 찾는 해가 아닌 경우 되돌아가서 해를 찾는다.

 

백트래킹 문제 

1. N과 M(1) 15649번

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

15649번: N과 M (1)

 

n, m = 4, 2
#n, m = map(int, input().split())
s = [] # 수열을 저장하는 리스트

def dfs():
    if len(s) == m: # 리스트의 길이가 m개인 경우
        print(' '.join(map(str, s))) # 리스트의 모든 숫자들을 출력
        return 
    for i in range(1, n+1): # 1부터 n+1
        if i not in s: # 리스트 안에 i(1~4) 가 없으면 
            s.append(i) # 리스트에 i(1~4) 추가
            dfs() # 다음 레벨
            s.pop() # 마지막으로 넣었던 i 제거
dfs()



n, m = 4,2
stack = []

def dfs(start):
    if len(stack) == m:
        # print(stack)
        print(' '.join(map(str, stack)))
        return 
    for x in range(1, n+1):
        if x not in stack:
            stack.append(x)
            dfs(start+1)
            stack.pop()
dfs(1)

 

---

3. N과 M(3) 15650번

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

15650번: N과 M (2)

 

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

def dfs(start):
    if len(stack) == m:
        print(' '.join(map(str, stack)))
        return
    else:
        for x in range(start, n+1):
            if x not in stack:
                stack.append(x)
                #print(stack)
                dfs(x+1)
                stack.pop()
dfs(1)

 

---

3. N과 M(3) 15651번

 

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

15651번: N과 M (3)

 

# n, m = map(int, input().split())
n, m = 4,2 
stack = []

def dfs():
    if m == len(stack):
        print(' '.join(map(str, stack)))
        return
    for x in range(1, n+1):
        stack.append(x)
        dfs()
        stack.pop()
dfs()

 

---

4. N과 M(4) 15652번

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

15652번: N과 M (4)

 

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

def dfs(start):
    if len(s) == m: # 리스트의 길이가 m개인 경우
        print(' '.join(map(str, s))) # 리스트의 모든 숫자들을 출력
        return 
    for i in range(start, n+1): # start으로 1,1 2,2, 3,3
        s.append(i) # 리스트에 i(1~4) 추가
        dfs(i) # 다음 레벨
        s.pop() # 마지막으로 넣었던 i 제거
dfs(1)

 

---

5. N과 M(5) 15654번

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

15654번: N과 M (5)

 

n, m = map(int, input().split())
# n, m = 4, 2 # n개의 수를 입력받고, m개의 중복없는 수열을 구하기
# arr = [9,8,7,1]
arr = list(map(int, input().split()))
arr = sorted(arr) # 사전순 출력
stack = []

def dfs():
    if len(stack) == m:
        for idx in stack:
            print(arr[idx], end=' ')
        print()
        return
    for x in range(0, n):
        if x not in stack:
            stack.append(x)
            dfs()
            stack.pop()
dfs()

 

---

6. N과 M(6) 15655번

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

15655번: N과 M (6)

 

#n, m = map(int, input().split())
#arr = list(map(int, input().split()))
n, m = 4, 4
arr = [1231, 1232, 1233, 1234]
arr = sorted(arr)
stack = []

def dfs(start):
    if len(stack) == m:
        for idx in stack:
            print(arr[idx], end=' ')
        print()
        return
    for x in range(start, n):
        if x not in stack:
            stack.append(x)
            dfs(x+1)
            stack.pop()
dfs(0)

 

 

---

7. N과 M(7) 15656번

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

15656번: N과 M (7)

 

n, m = map(int, input().split())
arr = list(map(int, input().split()))
#n, m = 4, 2
#arr = [9,8,7,1]
arr = sorted(arr) # 사전순 출력
stack = []

def dfs(start):
    if len(stack) == m:
        for idx in stack:
            print(arr[idx], end=' ')
        print()
        return

    for x in range(0, n):
        # 중복 상관 X
        stack.append(x)
        dfs(start+1)
        stack.pop()

dfs(0)

 

---

8. N과 M(8) 15657번

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

15657번: N과 M (8)

 

#n, m = map(int, input().split())
#arr = list(map(int, input().split()))

n, m = 4, 2
arr = [9,8,7,1]
arr = sorted(arr)
stack = []

def dfs(start):
    if len(stack) == m:
        for idx in stack:
            print(arr[idx], end=' ')
        print()
        return
    
    for x in range(start, n):
        stack.append(x)
        dfs(x)
        stack.pop()
dfs(0)

 

---

9. N과 M(9) 

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

15663번: N과 M (9)

 

#n, m = map(int, input().split())
#arr = list(map(int, input().split()))

n, m = 4, 2
arr = [9,7,9,1]
arr = sorted(arr)
visited = [False]*n # 사용한 원소 체크
stack = []
answer = []

def dfs(v):
    if len(stack) == m:
        answer.append(tuple(stack))
        return
    
    for x in range(0, n):
        if visited[x]:
            continue
        stack.append(arr[x])
        visited[x] = True # 사용
        dfs(v+1)
        visited[x] = False # 사용끝
        stack.pop() 
dfs(0)

# 오름차순, set 중복제거
for x in sorted(list(set(answer))):
    print(*x) # 튜플 출력

 

---

10. N과 M(10) 15664번

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

15664번: N과 M (10)

 

n, m = map(int, input().split())
arr = list(map(int, input().split()))
#n, m = 4,2
#arr = [999,1,23,5]
#arr = [9,7,9,1]
arr = sorted(arr) # 오름차순
stack = []

def dfs(v):
    if len(stack) == m:
        print(stack)
        return

    prev = 0
    for x in range(v, n):
        if prev != arr[x]:
            stack.append(arr[x])
            prev = arr[x]
            dfs(x+1)
            stack.pop()
dfs(0)

 

---

11. N과 M(11) 15665번

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

15665번: N과 M (11)

 

n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr = sorted(arr)
stack = []

def dfs():
    if len(stack) == m:
        print(*stack)
        return
    prev = 0
    for x in range(0, n):
        if prev != arr[x]:
            stack.append(arr[x])
            prev = arr[x]
            dfs()
            stack.pop()
dfs()

---

12. N과 M(12) 15666번

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

15666번: N과 M (12)

 

#n, m = map(int, input().split())
#arr = list(map(int, input().split()))
n, m = 4, 2
arr = [9,7,9,1]
arr = sorted(arr)
stack =[]

def dfs(v):
    if len(stack) == m:
        print(*stack)
        return
    prev = 0
    for x in range(v, n):
        if prev != arr[x]:
            stack.append(arr[x])
            prev = arr[x]
            dfs(x)
            stack.pop()
dfs(0)

 

6603번 로또

def dfs(stack, numbers, start, k):
    if len(stack) == 6:
        print(' '.join(map(str, stack)))
        return
    for x in range(start, len(numbers)):
        dfs(stack + [numbers[x]], numbers, x + 1, k)


while True:
    num = list(map(int, input().split()))
    if num[0] == 0:
        break

    k = num[0]  # 번호 개수
    numbers = sorted(num[1:])  # 번호 리스트

    visited = [False] * len(numbers)
    dfs([], numbers, 0, k)
    print()

 

1182번 부분수열의합

n, s = map(int, input().split())  # 정수의 개수, 정수 S
numbers = list(map(int, input().split()))

# n, s = 5, 0
# numbers = [-7, -3, -2, 5, 8]
cnt = 0


# 크기가 양수인 부분 수열 중에서 다 더한 값이 S인 경우의 수 구하기

def dfs(idx, cost):
    global cnt
    if idx >= n:  # 인덱스가 정수 개수보다 크면 종료
        return
    cost += numbers[idx]  # 더한값 += 현재 값
    if cost == s:  # 더한 값이 s면 경우의수 + 1
        cnt += 1
    dfs(idx + 1, cost)  # 현재 원소를 포함하는 경우
    dfs(idx + 1, cost - numbers[idx])  # 현재 원소를 포함하지 않는 경우


dfs(0, 0)
print(cnt)

 

9663번 N-Queen

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


def dfs(x):
    global result

    if x == n:
        result += 1
        return
    for i in range(n):
        if visite[i]:
            continue
        row[x] = i
        if adjacent(x):
            visite[i] = True
            dfs(x + 1)
            visite[i] = False

import sys

# n = int(sys.stdin.readline())
n = 8  # n x n 크기의 체스판
row = [0] * n
visite = [False] * n
result = 0
dfs(0)
print(result)