[백준 1506번] 경찰서 (Python3)

import sys
input = sys.stdin.readline

def DFS(now):
  global id,result
  visited[now] = nowid = id
  stack.append(now)
  for next in range(N):
    if graph[now][next]:
      if not visited[next]:
        id += 1
        DFS(next)
      visited[now] = min(visited[now],visited[next])
  if visited[now] == nowid:
    c = 1e9
    while 1:
      x = stack.pop()
      c = min(c,cost[x]); visited[x] = 1e9
      if x==now:
        result += c
        return

N = int(input())
cost = [*map(int,input().split())]
graph = [[*map(int,input().strip())] for i in range(N)]
stack = []; visited = [0]*N; result = 0
for i in range(N):
  if not visited[i]:
    id = 1
    DFS(i)
print(result)

SCC 기본문제.

타잔 알고리즘으로 해결하였다.

 

SCC를 구하고, 각 SCC의 요소 중 최소비용을 가진 도시에 경찰서를 세우면 된다.

 

 

오늘의 교훈) SCC 알고리즘은 매우 유용하다.