[백준 12963번] 달리기 (Python3)

import sys,collections
def input(): return map(int,sys.stdin.readline().split())

def BFS():
  dq = collections.deque([0])
  parent = [-1]*N
  while dq:
    now = dq.popleft()
    for next in adj[now]:
      if graph[now][next]-flow[now][next] and parent[next]<0:
        parent[next] = now
        dq.append(next)
        if next==N-1:
          return parent

def solve():
  while parent:=BFS():
    now = N-1; f = 3**M
    while now:
      last = parent[now]
      f = min(f,graph[last][now]-flow[last][now])
      now = last
    now = N-1
    while now:
      last = parent[now]
      flow[last][now] += f; flow[now][last] -= f
      now = last

N,M = input()
graph = [[0]*N for i in range(N)]; adj = [[] for i in range(N)]
for i in range(M):
  a,b = input()
  adj[a].append(b); adj[b].append(a)
  graph[a][b] = graph[b][a] = 3**i
flow = [[0]*N for i in range(N)]
solve()
print(sum(flow[i][-1] for i in range(N))%(10**9+7))

최대유량으로 해결하였다.

그냥 최대유량 알고리즘을 이용하면 쉽게 답을 구할 수 있다. M개의 양방향 간선에 대해 각 용량을 3^i로 두면 된다.

 

하지만 이 문제는 그리디한 방법으로 더 빠르게 해결할 수 있다고 하니 그 방법도 생각해봐야겠다.

예상컨대 3^i > 3^0+3^1+3^2+ ... + 3^(i-1)인 점을 이용하지 않을까 생각한다.

 

 

오늘의 교훈) 그리디한 방법으로도 문제를 해결해보자