- 이번 문제는 입력된 9개의 정수 중 2개를 뽑고, 나머지 7개의 정수의 합을 구하면됩니다.
- 가능한 모든 2개의 정수를 뽑는데, 나머지 7개의 정수의 합이 100이 된다면, 7개의 정수를 정렬하여 출력하면 됩니다.
전체 코드
- combinations 함수를 이용해 7개 정수를 뽑는 모든 조합의 경우를 계산합니다.
- 그 모든 조합 가운데, 합이 100이면, 그 7개 정수를 정렬하여 출력하도록 합니다.
from itertools import combinations
num_list = [int(input()) for i in range(9)]
p = list(combinations(num_list,7))
for i in p:
#print(sorted(i), sep='\n')
if sum(i) == 100 :
print(*sorted(i), sep='\n')
break;
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 한 간선이 여러 번 주어질 수도 있는데, 간선이 하나만 있는 것으로 생각하면 된다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
예제 입력 및 출력
문제 풀이
너비우선탐색(BFS, Breadth First Search)와 깊이우선탐색(Depth First Search)의 전형적인 기초 문제입니다. 이 두 알고리즘은 그래프를 탐색하기 위한 알고리즘으로 모든 정점을 탐색하기 위해 사용됩니다.
DFS는 한 경로로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 경로로 탐색하는 방식이고,(스택의 방식을 이용함, 스택은 기본 동작이라 스택 자료 구조를 이용할 필요는 없음) BFS는 갈림길에 연결되어 있는 모든 경로를 한번씩 탐색한 뒤 다시 연결되어 있는 모든 경로를 넓게 탐색하는 방식입니다. (자료 구조 큐 또는 덱 구조를 이용해야 함)
예를 들어 아래와 같은 그래프에서 DFS 동작은 다음과 같습니다. 1) 정점 1에서부터 검색 시작 2) 1에 연결된 정점 2,3,4 중 가장 작은 수인 2(방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 된다고 기입 됨)를 방문 3) 2에 연결된 정점 4를 방문 4) 4에 연결된 정점 3을 방문 5) 더이상 방문할 정점이 없으므로 종료 - 결국 1->2->4->3 순으로 방문하게 됩니다
예를 들어 아래와 같은 그래프에서 BFS 동작은 다음과 같습니다. 1) 정점 1에서부터 검색 시작 2) 정점 1과 연결된 2를 검색(방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 된다고 기입 됨) 3) 정점 1과 연결된 3을 검색(방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 된다고 기입 됨) 4) 정점 1과 연결된 4를 검색 - 결국 1->2->3->4 순으로 방문하게 됩니다.
전체 코드
from collections import deque
def dfs(v):
print(v, end=' ')
visit[v] = 1
for i in range(1, n + 1):
if visit[i] == 0 and adj[v][i] == 1:
dfs(i)
def bfs(v):
queue = deque()
visit[v] = 1
queue.append(v)
while (queue):
v = queue.popleft()
print(v, end=' ')
for i in range(1, n + 1):
if visit[i] == 0 and adj[v][i] == 1:
queue.append(i)
visit[i] = 1
#입력 n : 정점의 개수, m : 간선의 개수, v : 탐색을 시작할 정점의 번호
n, m, v = map(int, input().split())
adj = [[0] * (n + 1) for i in range(n + 1)]
visit = [0 for i in range(n + 1)]
for i in range(m):
x, y = map(int, input().split())
adj[x][y] = 1
adj[y][x] = 1
#출력
dfs(v)
print()
visit = [0 for i in range(n + 1)]
bfs(v)
