- 6.1. Recursive program for binary number (DFS)
- 6.2. Subset (DFS)
- 6.3. Subset sum problem (DFS)
- 6.4. Getting on truck (DFS)
- 6.5. Duplicated permutation (DFS)
- 6.6. Give change (DFS)
- 6.7. Get permutation (DFS)
- 6.8. Pascal’s triangle (DFS)
- 6.9. Get combination (DFS)
- 6.10. Guess combination (DFS)
- 6.11. Adjacent matrix (DFS)
- 6.12. Breadth First Search (BFS)
Python Algorithm Practice dfs/bfs
6.1. Recursive program for binary number (DFS)
10진수 N이 입력되면 2진수로 변환하여 출력하는 프로그램을 작성하세요. 단 재귀함수를 이용해서 출력해야 합니다.
num = int(input())
def to_binary(num):
if num == 0:
return
else:
to_binary(num//2)
print(num%2, end='')
to_binary(num)
6.2. Subset (DFS)
자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요.
def tree(root):
if root == n+1:
for i in range(1,n+1):
if a[i] == 1:
print(i, end='')
print()
else:
a[root] = 1
tree(root+1)
a[root] = 0
tree(root+1)
n = int(input())
a = [0]*(n+1)
tree(1)
6.3. Subset sum problem (DFS)
N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES”를 출력하고, 그렇지 않으면 “NO”를 출력하는 프로그램을 작성하세요.
둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다.
예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.
def tree(L, sum):
if sum > total//2:
return
if L == n:
if sum == (total-sum):
print("YES")
sys.exit(0)
else:
tree(L+1, sum+a[L])
tree(L+1, sum)
if __name__=="__main__":
n = int(input())
a = list(map(int, input().split()))
total = sum(a)
tree(0, 0)
print("NO")
6.4. Getting on truck (DFS)
트럭은 C(kg) 넘게 태울수가 없다. C(kg)을 넘지 않으면서 사람을 가장 무겁게 태우고 싶다.
N명의 사람 수와 각 사람 수의 무게 W가 주어지면, 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요.
def tree(L, sum):
global result
if sum > c:
return
if L == n:
if sum > result:
result = sum
else:
tree(L+1, sum+a[L])
tree(L+1, sum)
if __name__=="__main__":
c, n = map(int, input().split())
a = [0]*n
result = -1
for i in range(n):
a[i] = int(input())
tree(0,0)
print(result)
6.5. Duplicated permutation (DFS)
1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력합니다.
def tree(L):
global cnt
if L == m:
print(res)
cnt += 1
return
else:
for i in range(1, n+1):
res[L] = i
tree(L+1)
if __name__=="__main__":
n, m = map(int, input().split())
res = [0]*m
cnt = 0
tree(0)
print(cnt)
6.6. Give change (DFS)
다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.
def tree(L, sum): # L동전개수
global res
if L > res: # 최소 동전개수 이상이면 return
return
if sum > m:
return
if sum == m:
if L < res:
res = L
else:
for i in range(n):
tree(L+1, sum+a[i])
if __name__ == "__main__":
n = int(input())
a = list(map(int, input().split()))
m = int(input())
res = 2**1000
a.sort(reverse=True)
tree(0,0)
print(res)
6.7. Get permutation (DFS)
1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다.
def tree(L):
global cnt
if L == m:
for i in range(m):
print(res[i], end=' ')
print()
cnt += 1
else:
for i in range(1,n+1):
if ch[i] == 0:
ch[i] = 1
res[L] = i
tree(L+1)
ch[i] = 0
if __name__=="__main__":
n, m = map(int, input().split())
res = [0]*m
ch = [0]*(n+1)
cnt = 0
tree(0)
print(cnt)
6.8. Pascal’s triangle (DFS)
가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.
3 1 2 4
4 3 6
7 9
16
def tree(L, sum):
if L == 4 and sum == f:
for i in p:
print(i, end=' ')
sys.exit(0)
else:
for i in range(1, n+1):
if ch[i] == 0:
ch[i] = 1
p[L] = i
tree(L+1, sum+(p(L)*b[L]))
ch[i] = 0
if __name__ == "__main__":
n, f = map(int, input().split())
p = [0]*n
b = [1]*n
ch = [0]*(n+1)
for i in range(1, n):
b[i] = b[i-1] * (n-i)//i
print(b[i])
tree(0, 0)
# package 사용
n, f = map(int, input().split())
b = [1]*n
cnt = 0
for i in range(1, n):
b[i] = b[i-1]*(n-i)//i
a = list(range(1, n+1))
for tmp in it.permutations(a):
sum = 0
for L, x in enumerate(tmp):
sum += (x*b[L])
if sum == f:
for x in tmp:
print(x, end=' ')
break
6.9. Get combination (DFS)
1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성하세요.
def tree(L, s):
global cnt
if L == m:
for i in range(m):
print(res[i], end=' ')
print()
cnt += 1
else:
for i in range(s, n+1):
res[L] = tree(L+1, i+1)
n, m = map(int, input().split())
res = [0]*(n+1)
cnt = 0
tree(0, 1)
print(cnt)
6.10. Guess combination (DFS)
N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수는 몇 개가 있는지 출력하는 프로그램을 작성하세요.
예를 들면 5개의 숫자 2 4 5 8 12가 주어지고, 3개를 뽑은 조합의 합이 6의 배수인 조합을 찾으면 4+8+12 2+4+12로 2가지가 있습니다.
def tree(L, s, sum):
global cnt
if L == k:
if sum%m == 0:
cnt += 1
else:
for i in range(s, n):
tree(L+1, i+1, sum+a[i])
if __name__=="__main__":
n, k = map(int, input().split())
a = list(map(int, input().split()))
m = int(input())
cnt = 0
tree(0, 0, 0)
print(cnt)
# package 사용
n, k = map(int, input().split())
a = list(map(int, input().split()))
m = int(input())
cnt = 0
for x in it.combinations(a, k):
if sum(x)%m == 0:
cnt += 1
print(cnt)
6.11. Adjacent matrix (DFS)
아래 그림과 같은 그래프 정보를 인접행렬로 표현해보세요.
n = int(input())
m = int(input())
g = [[0]*(n+1) for _ in range(n+1)]
for i in range(m):
a, b = map(int, input().split())
g[a][b]=1
g[b][a]=1
for i in range(1, n+1):
for j in range(1, n+1):
print(g[i][j], end=' ')
print()
6.12. Breadth First Search (BFS)
방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요.
방문한 노드는 중복해서 방문하지 않습니다.
위 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 총 6가지입니다.
1 2 3 4 5
1 2 5
1 3 4 2 5
1 3 4 5
1 4 2 5
1 4 5
def tree(vt):
global cnt
if vt == n:
cnt += 1
# for x in path:
# print(x, end=' ')
else:
for i in range(1, n+1):
if g[vt][i]==1 and ch[i]==0:
ch[i] = 1
# path.append(i)
tree(i)
# path.pop()
ch[i] = 0
if __name__=="__main__":
n, m = map(int, input().split())
g = [[0]*(n+1) for _ in range((n+1))]
ch = [0]*(n+1) # dup check
for i in range(m):
a, b = map(int, input().split())
g[a][b] = 1
cnt = 0
# path = []
# path.append(1)
ch[1] = 1
tree(1)
print(cnt)