[코테/Python] 세금 징수

목차 (OPEN)

• 📑 문제
• 💡 아이디어
• 👩🏻‍💻 전체 코드
• 📚 결론

 

 

 

 

📑 문제

• 방향 그래프가 있고, 각 간선에는 통행료 d 와 폐쇄 비용 c 가 붙어 있다.
• 시작점 s 에서 도착점 e 로 가는 총 통행료가 x 이하인 모든 경로에 포함되는 간선을 전부 폐쇄하려 한다.
• 여러 질의 x 에 대해서 폐쇄해야 할 간선들의 폐쇄 비용 합을 구해야 한다.

 

 

---

💡 아이디어

핵심은 간선 단위로 그 간선을 지나는 s -> e 경로의 최소 통행려를 한 번에 계산해두는 것이다.

이 값을 미리 알면 질의 x마다 임계갑 이하인 간선만 합산하면 되기 때문에 효율적이다.

 

1. 간선마다 최소 비용 계산하기
   만약 어떤 도로 u -> v 가 있다고 해보자.
   이 도로가 실제로 s - > e 경로에 포함되려면, 아래의 3가지 요소를 모두 더해줘야 한다.
   1) s에서 u까지 가는 최단 요금
   2) u -> v 도로의 요금
   3) v에서 e까지 가는 최단 요금
   👉🏻 즉, 위의 세 가지를 더해주면, 해당 도로(u -> v)를 거쳐 s - > e로 가는 데 드는 최소 요금을 알 수 있는 것이다.
        (쉽게 말해 도로 하나마다 이 도로를 거치는 최저 경로 요금을 미리 적어두는 거라고 생각하면 된다.)
2. 임계값 x와 비교하기
   위에서 계산한 값을 key(간선)이라 하고, 질의 x가 들어온다고 하자.
   1) 만약 key <= x 이면 👉🏻 이 도로는 어떤 경로에서든 총 요금이 x 이하일 가능성이 있으니, 폐쇄 후보가 됨
   2) 만약 key > x 이면 👉🏻 애초에 이 도로를 지나는 순간 비용이 폐쇄 임계값 보다 커지는 것이므로, 폐쇄될 일이 없음
3. 여러 질의를 빠르게 처리하기
   여러 개의 x 값이 들어올 수 있으니까, 매번 모든 도로를 다 확인해주면 너무 느리다.
   그래서 우리는 미리 아래의 준비들을 해주어야 한다.
   1) 모든 도로의 (key, 폐쇄 비용)을 적어놓고, key를 기준으로 정렬한다.
   2) 폐쇄 비용들을 위에서부터 차례대로 더해서 누적합을 만들어준다.
       (ex. 앞에서부터 3개의 도로를 합치면 비용이 얼마고, 5개의 도로를 합치면 비용이 얼마고 .. 이런 느낌)
   3) 이제 질의 x가 들어오면, key <= x 인 도로가 몇 개인지만 이분 탐색로 찾고, 그 개수까지의 누적합을 답으로 바로 꺼내면 된다.

 

 

더 쉽게 이해하기 위해서 아예 다른 상황을 생각해보자.

 

만약 내가 지금 마트에 가서 쇼핑을 하고 있는데,

각 상품마다 '이거는 최소 key원 이상 사야 구매 가능함, 하나 당 가격은 cost원 임' 이라고 써있다고 해보자.

 

나는 오늘 쇼핑을 나오면서 x원만 들고 왔다고 하면,

key < = x 이하인 상품들 중에서만 쇼핑을 할 수 있을 것이다.

(최소 x원 이상 사야 구매가 가능한 상품을 골라야 내가 돈을 낼 수 있으니까 ..)

 

구체적으로는, 내가 오늘 만원을 들고 쇼핑을 하려고 나왔는데,

라면은 한 봉지당 5천원(cost)인데, 만원(key) 이상 사야 결제가 가능하다고 하고,

떡볶이는 한 봉지당 8000(cost) 원인데, 만 오천원(key) 이상 사야 결제가 가능하다고 해보자.

그러면 내가 가진 돈은 만원 뿐인데,

떡볶이를 사려면 최소 만 오천원이 필요한 거니까 애초에 난 떡볶이를 사는게 불가능해진다.

 

 

그래서 내가 key를 기준으로 정렬을 해준 것이고,

구매 가능한 최소 요금 5천원, 최소 요금 8천원, 최소 요금 만원, 최소 요금 3만원 , ... 이런 느낌으로 정렬이 되었다고 치면,

다른 손님이 와서 '저는 오늘 x원 까지만 쓸래요~' 했을 때, 바로 구매 가능한 상품들을 대답할 수 있게 되는 것이다.

 

---

👩🏻‍💻 전체 코드

from heapq import heappush, heappop

INF = 10**9

# 다익스트라 알고리즘
# start는 시작 정점
# graph는 인접 리스트 (graph[u] = (v, w))
# n은 정점의 개수
def dijkstra(start, graph, n):
	dist = [INF] * n   # 최단 거리 배열
	dist[start] = 0
	pq = [(0, start)]  # (거리, 정점) 우선순위 큐

	while pq:
		du, u = heappop(pq)
        
        # 이미 더 짧은 최단 거리가 갱신된 경우는 건너뛰기
		if du != dist[u]:
			continue
            
        # u에서 나갈 수 있는 모든 간선 검사하기
		for v, w in graph[u]:
			nd = du + w
			if nd < dist[v]:
				dist[v] = nd
				heappush(pq, (nd, v))
	return dist



def main():

	# n은 정점 수, m은 간선 수, s는 시작 정점, e는 도착 정점
	n, m, s, e = map(int, input().split())
	s -= 1
	e -= 1

	# 정방향 그래프와 역방향 그래프 준비해두기
	not_reverse = [[] for _ in range(n)] # s -> ... 탐색용
	reverse = [[] for _ in range(n)]     # ... -> e 탐색용

	edge = [] # 원본 간선 (u, v, d, c) 저장용

	# 간선 입력 받기
	for _ in range(m):
		u, v, d, c = map(int, input().split())
		u -= 1
		v -= 1
		
        # 정방향 u -> v (비용 d)
		not_reverse[u].append((v, d))
        # 역방향 v -> u (비용 d)
		reverse[v].append((u, d))
        # 우너본 간선 저장
		edge.append((u, v, d, c))

	# 질의 입력
	q = int(input())
	qs = [int(input()) for _ in range(q)]

	
	distS = dijkstra(s, not_reverse, n) # s에서 각 정점까지의 최단 거리
	distE = dijkstra(e, reverse, n)     # 각 정점에서 e까지의 최단 거리

	# 각 간선 별로 "s->u + d + v->e" 최소 비용(key) 계산
	keys = []  # 간선의 최소 경로 비용
	costs = [] # 간선 폐쇄 비용

	for u, v, d, c in edge:
    	# s에서 u까지, v에서 e까지 도달 불가능하면 건너뛰기
		if distS[u] == INF or distE[v] == INF:
			continue

		key = distS[u] + d + distE[v] # 해당 간선을 지나는 최소 경로 비용
		keys.append(key)
		costs.append(c)

	# (key, cost) 쌍 정렬 준비
	pairs = []
	i = 0
	while i < len(keys):
		pairs.append((keys[i], costs[i]))
		i += 1

	# key 기준 정렬
	pairs.sort()

	# key와 비용만 따로 분리
	sorted_keys = []
	i = 0
	while i < len(pairs):
		sorted_keys.append(pairs[i][0])
		i += 1

	# 누적 비용 합 배열
	sums = [0]
	accumulate = 0
		
	i = 0
	while i < len(pairs):
		accumulate += pairs[i][1]
		sums.append(accumulate)
		i += 1

	# upper bound: x 이하의 key 개수 찾기
	def upper(arr, x):
		l = 0
		h = len(arr)

		while l < h:
			mid = (l + h) // 2
			if arr[mid] <= x:
				l = mid + 1
			else:
				h = mid
		return l

	# 각 질의 처리
	ans = []
	i = 0
	while i < len(qs):
		x = qs[i]
        # key <= x 인 간선 개수 구하기
		k = upper(sorted_keys, x)
        # 누적합에서 해당 구간까지 비용 합 출력
		ans.append(str(sums[k]))
		i += 1

	print("\n".join(ans))



if __name__ == "__main__":
	main()

 

 

---

📚 결론

보통 앞서 올렸던 3번 dp 문제(도형 만들기)를 더 어려워하던데,

난 오랜만에 코테를 봐서 그런가 이 문제가 더 오래 고민됐다 ..

(별건 아니지만 어떻게 접근했는지가 가물가물해서 ..ㅜㅜ)

 

그래도 오랜만에 문제를 간선 단위로 쪼개서, 전처리로 구조화한 뒤,

효율적으로 질의를 처리하는 사고법을 떠올려보니 뿌듯하긴 했지만 머리가 너무 아팠다 .. ^^ ..

 

잠깐이라도 소홀히 하면 머리가 급격하게 굳어버린다는 것을 깨달았으니

앞으로는 코테도 꾸준히 풀어서 포스팅해야겠다. (꼭 !!!! 👊🏻👊🏻👊🏻👊🏻)