네이버 코테 준비로 열심히 코테 문제들을 풀어보는데, 어렵다!
오늘은 힙을 잘 써서 효율적으로 풀이한 문제 몇개를 봐서 정리할 겸 올린다.
1. 지형 이동
아이디어
1.
그림처럼 먼저 bfs를 통해 visited에 넘버링으로 구간 (노랑색, 파랑색, 빨간색)을 나눈다.
# 1 bfs를 이용해서 구간 나누기 (넘버링)
visited = [[0]*Y for _ in range(X)]
def bfs(x,y,i):
Q = deque([[x,y]])
visited[x][y] = i
while Q:
x, y = Q.popleft()
for _ in range(4):
nx, ny = x+dx[_], y+dy[_]
if 0 <= nx < X and 0 <= ny < Y and not visited[nx][ny] and (abs(land[nx][ny] - land[x][y]) <= height):
Q.append([nx,ny])
visited[nx][ny] = i
i = 0
start = []
for x in range(X):
for y in range(Y):
if not visited[x][y]:
i += 1
bfs(x,y,i)
start.append([x,y,i])
2.
구간 표시가 끝났으니 다시 bfs로 임의의 x 구간에서 y 구간으로 갈 때 필요한 가중치를 저장한다.
# visited에 저장 되어있음
adj = {x+1 : set() for x in range(i)}
#2 그룹간의 이동 시 필요한 최소 가중치 간선 탐색
for x,y,i in start:
Q = deque([[x,y]])
while Q:
x,y = Q.popleft()
for _ in range(4):
nx, ny = x+dx[_], y+dy[_]
if 0 <= nx < X and 0 <= ny < Y:
if visited[nx][ny] == i:
Q.append([nx,ny])
visited[nx][ny] = -1
elif visited[nx][ny] != -1:
adj[i].add((abs(land[nx][ny] - land[x][y]),visited[nx][ny]))
adj[visited[nx][ny]].add((abs(land[nx][ny] - land[x][y]),i))
3.
이제 문제는 (예제에서는) 노드 3개와 간선들의 그래프에서 MST를 구하는 문제로 치환된다.
프림 알고리즘을 사용하여 해결하였다.
# 3 프림 알고리즘으로 최소 가중치 간선들 구하기
Tree_node = set([1])
cand_list = list(adj[1])
heapify(cand_list)
anw = 0
while cand_list:
w, node = heappop(cand_list)
if node not in Tree_node:
Tree_node.add(node)
anw += w
for e in adj[node]:
if e[1] not in Tree_node:
heappush(cand_list,e)
return anw
일단 패스는 받았는데 코드가 매우 길다. 구간을 나누고, 다시 한번 도는 것도 그렇고, 프림 알고리즘도 처음엔 인접 행렬로 접근하였더니 바로 시간초과가 뜨더라. 다행히 힙과 인접 배열을 쓴 프림 알고리즘으로 풀리긴 하였다. 문제를 보자마자 깊은 생각 없이 접근한 죄.
개선 방안
다른 사람의 풀이를 보니 풀이가 참 좋아서 가져온다. 우선순위 큐를 사용하여 그리디하게 가중치가 필요없는 순회를 먼저 마치고, 남은 순회 중 가중치가 최저인 것부터 순회해서 다시 접근 가능 지형을 업데이트하는 방식.
대충~ 코드를 짜보았다.
# v, x, y 를 저장
Q = [[0,0,0]]
visited = #대충 맵 모양 False
visit_count = 0
Max_count = #대충 맵 크기
V = 0
while visit_count < Max_count:
# 도착하는데 필요한 가중치가 적은것부터 빼기
v, x, y = heappop(Q)
# x,y 를 이미 만나봤으면 pass
if visited[x][y]:
continue
visit_count += 1
# 현재 사용된 가중치 합
V += v
for _ in range(4):
#대충 nx, ny 만들어서 visit 확인하고 Q에 넣는 bfs 형식인데!
# 만약 사다리가 필요하면 (v가 존재하면)
if abs(new_height - now_height) > height:
heappush(Q,(abs(new_height - now_height), nx, ny))
# 두 지형의 높이차가 프리하게 지나갈 수 있으면
else:
heappush(Q, (0,nx,ny))
return V
그냥 이렇게 굳이 구간을 나누지 않고 우선순위 큐를 사용하면 처음에 사다리가 필요 없는 구간을 다 돌고
알아서 가중치가 최저인 지형을 선택하게 되더라. 허허 bfs할 때 너무 deque만 썼더니 뇌가 녹아버렸나보다.
이러면 bfs를 전 맵에 1번하는 것에 que에 넣고 빼는 부분만 log(N*N) 이 곱해질테니 훨씬 빠를 듯 하다. 그리고 일단 구현이 쉬워진다 ㅜ. 배워갑니다.
2. 보석 도둑
냅색 문제인 줄 알았다가 자세히 보니 가방 1개에 보석이 1개만 들어간다.
아이디어
보석을 (V, M) 형태로 V를 오름차순으로 오도록 정렬하고 하나씩 꺼내서 주어진 가방들 중에서 가장 딱 맞는 가방을 이분탐색으로 찾아 넣어주고 visit 처리를 해서 해결하려 했으나 시간 초과. 첫 보석은 잘 넣지만, 이후 visit 처리된 보석이 많아지면, visit이 안된 보석을 찾기 위해 배열을 순회하면서 결국 보석을 단 하나 넣는데도 O(N)이 소모된다.
뭔가 보석과 가방을 한 배열에 넣고 처리해야겠다는 감은 왔으나 어떻게 할지 잘 생각이 안나서 결국 힌트를 보고 풀게 되었다.
보석의 무게와 가치 M, V와 가방의 허용 무게 C를 다음과 같이 한 배열에 정렬할 수 있다.
무게가 작은 보석은 허용 무게가 큰 가방에 들어갈 수 있지만, 반대는 안 된다는 점을 생각해서...
무게가 작은 보석부터 꺼내서 V를 기준으로 우선순위 큐에 넣다가 가방을 만나면 현재 큐에 있는 보석들은 다 가방에 넣을 수 있는 보석들이다. V가 제일 큰 녀석을 빼서 넣어주기만 하면 된다.
얘도 힙을 활용하면 쉽게 풀 수 있더라. ((N+K)log(N))으로 풀릴 것이다.
import sys; read = sys.stdin.readline
import heapq
N, K = map(int,read().split())
alls = []
for _ in range(N):
M, V = map(int,read().split())
alls.append([M,V])
for _ in range(K):
K = int(read().strip())
# -1 안댐, 제일 큰 값을 해야 무게가 같은 보석과 가방 중
# 가치를 기준으로 가방이 제일 뒤로 줄을 선다.
#alls.append([K,-1])
alls.append([K, 10**6+1])
# 무게를 기준으로 정렬하고 가방의 경우 가치를 구분하여 가방임을 표시
alls.sort()
anw = 0
buffer = []
print(alls)
# 무게가 낮은 거 부터 -> 가방을 만나면 무조건 넣을 수 있다.
for x in alls:
# 보석이라면
if x[1] != 10**6+1:
# 가치가 큰 것이 우선적으로 오게 힙 삽입 buffer는
# 넣을 수 있는 후보 보석들을 담음
heapq.heappush(buffer,-x[1])
#가방이라면
else:
# 후보 보석들 중 가장 가치가 큰 놈을 빼서 가방에 넣는다.
if buffer:
anw += -heapq.heappop(buffer)
print(anw)
가방을 배열에 저장할 때는 V를 보석의 최대 가치보다 더 큰 값으로 하여 alls 정렬시 같은 무게여도 가방이 무조건 뒤에 서있게 하는 아이디어가 참신하더라.
우선순위 큐를 쓰는 그리디한 문제를 좀 더 풀어봐야할 듯 하다.
