[강한 연결 요소/파이썬] 백준 1506번 : 경찰서 / 플래 5

https://www.acmicpc.net/problem/1506

1506번: 경찰서

n = int(input())
cost = list(map(int, input().split()))

graph = []
for _ in range(n):
    graph.append([int(x) for x in input()])

node_id = 0
stack = []
on_stack = [False for _ in range(n)]
parent = [-1 for _ in range(n)]

def dfs(node):
    global answer

    # 고유 아이디 부여
    global node_id
    cur_id = node_id
    node_id += 1

    # 본인 id를 부모로 우선 배정. 스택에 자기 자신을 넣음
    parent[node] = cur_id
    stack.append(node)
    on_stack[node] = True

    for i in range(n):
        if graph[node][i] == 1:  # 갈 수 있는 노드

            if parent[i] == -1:  # 방문 이력이 없는 노드
                dfs(i)
                parent[node] = min(parent[node], parent[i])

            elif on_stack[i]:  # 방문 이력이 있지만 해결 x인 노드
                parent[node] = min(parent[node], parent[i])

    ## find scc
    if parent[node] == cur_id:
        scc = []
        while True:
            elem = stack.pop()
            on_stack[elem] = False
            scc.append(elem)
            if elem == node:
                break

        min_cost = 9876543210
        for node in scc:
            min_cost = min(min_cost, cost[node])
        answer += min_cost


answer = 0
for i in range(n):
    if parent[i] == -1:
        dfs(i)
print(answer)

결국 문제는 강한 연결 요소를 찾고, 그 scc 별로 가장 싼 비용을 내는 것이다.