[백준 4013번] ATM (Python3)

import sys,collections
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def BFS():
  result = 0; pre = [0]*C
  while dq:
    now = dq.popleft()
    if sccrest[now]:
      result = max(result,pre[now]+scc[now])
    for next in sccgraph[now]:
      indegree[next] -= 1
      pre[next] = max(pre[next],pre[now]+scc[now])
      if not indegree[next]:
        dq.append(next)
  return result

def DFS(now):
  global id,start
  visited[now] = nowid = id
  stack.append(now)
  for next in graph[now]:
    if not visited[next]:
      id += 1
      DFS(next)
    visited[now] = min(visited[now],visited[next])
  if visited[now] == nowid:
    n = len(scc); scc.append(0)
    while 1:
      x = stack.pop()
      scc[-1] += money[x]
      sccnum[x] = n; visited[x] = 1e7
      if x==now:
        break

N,M = map(int,input().split())

graph = [[] for i in range(N+1)]; indegree = [0]*(N+1)
for _ in range(M):
  a,b = map(int,input().split())
  graph[a].append(b)
  indegree[b] += 1
money = [0]+[int(input()) for i in range(N)]

S,P = map(int,input().split())
rest = [*map(int,input().split())]

stack = []; scc = []; visited = [0]*(N+1); sccnum = [0]*(N+1)
for i in range(1,N+1):
  if not visited[i]:
    id = 1
    DFS(i)

C = len(scc)
sccgraph = [[] for i in range(C+1)]
indegree = [0]*C; sccrest = [0]*(C+1); scc.append(0)
for i in range(1,N+1):
  for j in graph[i]:
    if sccnum[i]==sccnum[j]:
      continue
    sccgraph[sccnum[i]].append(sccnum[j])
    indegree[sccnum[j]] += 1
for r in rest:
  sccrest[sccnum[r]] = 1
sccgraph[-1].append(sccnum[S]); indegree[sccnum[S]] += 1

dq = collections.deque()
for i in range(C):
  if not indegree[i]:
    dq.append(i)
BFS()
dq.append(-1)
print(BFS())

SCC + 위상정렬 문제이다.

코드길이가 상당히 길고 구현량이 많다. 하지만 아이디어 자체는 쉬운 편이고 실수할 여지도 적은 편이어서 풀기 어렵지는 않다.

 

이 문제를 풀기 전에 위상정렬 최장거리 [백준 1005번] ACM Craft (Python3) (tistory.com) , SCC 알고리즘 [백준 2150번] Strongly Connected Component (Python3) (tistory.com) , SCC+indegree [백준 4196번] 도미노 (Python3) (tistory.com) 를 풀어본 경험이 도움이 되었다.

 

풀이를 설명하면,

1. 타잔 알고리즘으로 SCC를 구하고, 각 SCC의 돈의 합을 저장한다.

2. 모든 간선에 대해서 같은 SCC 내부의 간선을 제외한 나머지 간선에 대해 SCC간 그래프를 작성하고, SCC의 indegree를 구한다.

3. 시작지점 S를 포함한 SCC의 indegree를 +1 해준다.

4. SCC의 indegree가 0인 점에 대해서 BFS로 탐색한다. (이 SCC들은 쓸모없는 데이터이다. 시작지점에서 도달할 수 없기 때문)

5. 초기화 후, 이번엔 시작지점에서 BFS로 탐색하여 위상정렬+DP의 최장거리 구하는 방식으로 최대 돈을 구한다.

 

 

오늘의 교훈) 다양한 알고리즘을 적재적소에 활용하자