[파이썬, 자바] 백준 1506 : 경찰서 (플레5)

[파이썬, 자바] 백준 1506 : 경찰서 (플레5)

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

---

풀이

방향성 생각

• 간선 정보가 인접행렬로 나와있다.
• N이 작아서 인접 리스트를 구현하는 대신 그냥 인접행렬 사용하기
• 문제를 해석하면 SCC가 몇 개나 있는지 확인하는 문제이다.
• 각 SCC 내에서 가장 작은 건설 cost를 구해서 더해주면 되는 문제

 

---

파이썬

from collections import deque
import sys
input = lambda : sys.stdin.readline().strip()

N = int(input())
arr = list(map(int,input().split()))
G = [list(map(int,input())) for _ in range(N)]

# SCC 방문 / 카운팅 / 스택 관리
V = [-1]*N
P = [-1]*N
counter = [0]
stack = deque()
on_stack = [False]*N

# 타잔 알고리즘
SCC = []
def dfs(x):
    V[x] = counter[0]
    P[x] = counter[0]
    counter[0] += 1
    stack.append(x)
    on_stack[x] = True

    for nx in range(N):
        if G[x][nx]:
            if V[nx] == -1:
                dfs(nx)
                P[x] = min(P[x], P[nx])
            elif on_stack[nx]:
                P[x] = min(P[x], V[nx])

    if V[x] == P[x]:
        scc = []
        while True:
            w = stack.pop()
            on_stack[w] = False
            scc.append(w)
            if w == x:
                break
        SCC.append(scc)

# 탐색
for x in range(N):
    if V[x] == -1:
        dfs(x)

# 답
answer = 0    
for scc in SCC:
    answer += min(arr[x] for x in scc)
print(answer)

---

코멘트

• .