[백준] 1715, 1260 (파이썬)

오늘은 그리디 문제를 풀고 BFS,DFS에 관한 개념을 학습한뒤 관련 문제를 풀어보았다. 전반적인 내용의 이해는 어렵지 않았으나 이를 구현하는 것에 익숙하지 않아서 그런지 계속 막히는 느낌이었다. 그래서 여러문제를 풀어보기보다는 DFS,BFS의 기본적인 함수를 안보고 구현할 수 있을 때까지 필사하며 연습해보았다.

백준 1715번 카드 정렬하기

'''메모리초과
import sys
N = int(sys.stdin.readline())
num_lst = []
for _ in range(N):
    num_lst.append(int(sys.stdin.readline()))
num_lst.sort()
cnt = 0
for i in range(N-1):
    cnt += num_lst[i] + num_lst[i+1]
    num_lst[i+1] = cnt
print(cnt)
'''
import sys
import heapq
N = int(sys.stdin.readline())
num_lst = []
for _ in range(N):
    heapq.heappush(num_lst, int(sys.stdin.readline()))
cnt = 0
for i in range(N-1):
    temp1 = heapq.heappop(num_lst)
    temp2 = heapq.heappop(num_lst)
    cnt += temp1 + temp2
    heapq.heappush(num_lst, temp1 + temp2)
print(cnt)

백준 1260번 DFS와 BFS

# 알고리즘과 책을 참고했다.
# 계속 연습해봐야할 문제, 아무런 참고자료없이 구현할 수 있게 만들자.
import sys
from collections import deque

def dfs(n):
    print(n, end=' ')
    visited[n] = True
    for i in graph[n]:
        if not visited[i]:
            dfs(i)
def bfs(n):
    queue = deque([n])
    visited[n] = True
    while queue:
        v = queue.popleft()
        print(v, end= ' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

N,M,V = map(int,sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]
visited = [False] * (N + 1)
for _ in range(M):
    x,y = map(int,sys.stdin.readline().split())
    graph[x].append(y)
    graph[y].append(x)
for i in range(1, N+1):
    graph[i].sort()
dfs(V)
visited = [False] * (N + 1)
print()
bfs(V)