문제 링크
https://www.acmicpc.net/problem/13907
미해결
- 풀이시간 : x
- 풀이 : dijkstra로 경로를 추적해본 적이 있기 때문에 처음에는 경로를 추적해서 그 경로의 수를 구해서 세금을 인상시키는 방법을 써야하나 생각도 해보았지만 경로를 빼는 것과 완전히 추적하는 것은 다른 문제였다. 그래서 한참을 경로의 수를 구할 방법을 찾았지만 생각나는 방법이 없어서 게시판을 보았다. 다른 사람들이 다들 이차원 배열로 distance를 갱신하길래 어떻게 하면 2차원 배열로 이것을 통제할 수 있을까 생각하다가 한 노드에서 출발하면 그 노드와 연결된 모든 노드가 갱신되므로 다시 한번 갱신된다면 방문한 간선의 갯수가 된다고 생각했다. 즉 특정 노드를 들렸다가 갱신이 되므로 +1이 되는것으로 간주되는 것이다. 여기까지 생각했으니 다 풀었다고 생각하고 Java로 끄적여보다가 안풀리길래 python으로 건드려보았으나 역시나 안풀렸다. 문제는 최적화 방법 중 간선을 탐색하기 전에 최적화하는 곳에 있었다. 모든 노드를 기준으로 탐색해보고 하나라도 최적화가 이미되어있다면 끝내야한다는 것이다. 여기까지도 사실 생각은 했었으나 풀이시간이 하도 길어져서 넘어간 부분이었다. 이 부분만 다음번에 비슷한 유형이 나온다면 유의하면 될거 같다.
- 왜 이차원 배열을 사용한다는 점을 생각하지 못했는가? : 경로의 갯수를 파악하는 데 있어서 다익스트라의 갱신 원리를 깊게 생각하지 못했던 거 같다. 즉 갱신의 원리, 한 노드가 갱신될때 연결된 모든 노드를 갱신하므로 다시 갱신하면 전 노드까지의 갯수를 구할 수 있다는 것을 생각하지 못했다. 왜 이 부분을 생각 못했냐 한다면 원리를 알고 있어도 이 부분을 2차원 배열로 갱신할 생각은 못한거 같다. 아직 DP에서 전 단계가 이전단계를 갱신시키는 부분의 다익스트라의 기본이 되는 원리를 이용하는데 능력이 부족한거 같다.
🕒 Python 풀이시간: x
import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)
N, M, K = map(int, input().split())
S, D = map(int, input().split())
graph = [[] for _ in range(N + 1)]
for _ in range(M):
a, b, c = map(int, input().split())
graph[a].append((b, c))
graph[b].append((a, c))
tax = [0]
for _ in range(K):
tax.append(int(input())+tax[-1])
def dijkstra(start):
distance = [[INF] * N for _ in range(N + 1)]
q = [(0, 0, start)]
distance[start][0] = 0
while q:
dist, edgeCnt, now = heapq.heappop(q)
flag = False
for i in range(edgeCnt):
if distance[now][i] < dist:
flag = True
break
if edgeCnt == N - 1 or flag:
continue
for i in graph[now]:
cost = dist + i[1]
if distance[i[0]][edgeCnt + 1] > cost:
distance[i[0]][edgeCnt + 1] = cost
heapq.heappush(q, (cost, edgeCnt + 1, i[0]))
return distance
distance = dijkstra(S)[D]
answer=[]
for k in tax:
min_cost=INF
for i in range(len(distance)):
if distance[i]<INF:
min_cost=min(min_cost,distance[i]+i*k)
answer.append(min_cost)
print(*answer, sep='\n')
이렇게 Python으로 백준의 "세금" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
