[백준] 1202, 2644 (파이썬)

동일하게 그리디와 BFS,DFS 문제를 풀었다. 한 문제당 시간이 상당히 오래 걸리다보니 문제수가 많지는 않은 느낌이지만, 확실히 많이 배우고 있다는 느낌이 든다. 아직은 알고리즘을 봐야 느낌이 오는 상태이다. 아예 감도 못잡던 예전보다는 낫지만 더 익숙해져서 알고리즘 없이도 완벽하게 구현하도록 노력하자.

백준 1202번 보석 도둑

import sys
import heapq

N,K = map(int,sys.stdin.readline().split())
gem = []
for _ in range(N):
    M,V = map(int,sys.stdin.readline().split())
    heapq.heappush(gem, [M, V])
bag = []
for _ in range(K):
    C = int(sys.stdin.readline().strip())
    heapq.heappush(bag, C)
cnt = 0
que = []
for _ in range(K):
    # bag의 수용량
    min_bag = heapq.heappop(bag)
    # bag의 수용량보다 작은 보석
    while gem and min_bag >= gem[0][0]:
        # 조건에 맞는 보석의 가격만 넣어준다
        [M, V] = heapq.heappop(gem)
        heapq.heappush(que, -V) # 최대힙을 만드는 방식
    # 남은 보석이 있는 경우
    if que:
        # 조건에 맞는 가장 비싼 보석 추가
        cnt -= heapq.heappop(que)
    # 남은 보석 없는 경우 (없어도 되지만 쓸데없는 반복줄임)
    elif not gem:
        break
print(cnt)

백준 2644번 촌수계산

# 아직까지도 알고리즘을 봐야 흐름이 잡힌다.
# 익숙해질때까지 트라이
import sys
from collections import deque
# bfs
def bfs(n):
    queue = deque()
    queue.append(n)
    while queue:
        # queue에서 n빼냄
        n = queue.popleft()
        for i in graph[n]:
            # 다음 지역 방문 x일때
            if visited[i] == 0:
                # 숫자 1늘리고 queue에 넣어줌
                visited[i] = visited[n]+1
                queue.append(i)
# 모든 인원
all_num = int(sys.stdin.readline())
# 0 부터 모든 인원수까지 그래프
graph = [[] for _ in range(all_num+1)]
# 시작사람, 끝사람
hum1, hum2= map(int,sys.stdin.readline().split())
# 입력받을 관계수
chonsu_num = int(sys.stdin.readline())
# 관계입력받음
for _ in range(chonsu_num):
    x,y = map(int,sys.stdin.readline().split())
    # 그래프에 넣음
    graph[y].append(x)
    graph[x].append(y)
# 방문 여부
visited = [0]*(all_num+1)
bfs(hum1)
# 관계 없으면 -1
if visited[hum2] > 0:
    print(visited[hum2])
else:
    print(-1)