[백준]1506 경찰서

1.풀이

(1) 플로이드와샬을 이용하여 연결되어있는지를 확인한다.

(2) bfs를 통해 연결되어있는 컴포넌트에서 경찰서 건설비용이 가장 작은곳에 경찰서를 짓는다.

​

위의 방법으로 어거지로 풀었지만 아래와 같이 최적화하여 푸는 방법을 찾아본다.

*최적화 풀이

(1) dfs(강연결요소)를 통한 풀이

(2) 유니온-파인드를 이용.

​

2. 소스코드 (플로이드와샬, bfs)

INF=9876543210

N=int(input())
cost=list(map(int,input().split()))
L=[]
for i in range(N):
    L.append(list(map(int,list(input()))))


def floid():
    #초기값 설정
    for i in range(N):
        for j in range(N):
            if L[i][j]==1:
                dist[i][j]=1

    #플로이드와샬
    for k in range(N):
        for i in range(N):
            for j in range(N):
                temp=dist[i][k]+dist[k][j]
                if temp<dist[i][j]:
                    dist[i][j]=temp

def connect():
    for i in range(N):
        for j in range(i+1,N):
            if dist[i][j]!=INF and dist[j][i]!=INF:
                graph[i].append(j)
                graph[j].append(i)

def BFS():
    global ans
    visited=[-1 for i in range(N)]
    for i in range(N):
        if visited[i]==-1:
            visited[i]=1
            temp=[i]+graph[i]
            for conNode in graph[i]:
                visited[conNode]=1
            minNum=INF
            for i in temp:
                if cost[i]<minNum:
                    minNum=cost[i]
            ans+=minNum


dist = [[INF for j in range(N)] for i in range(N)]
floid()
graph={}
for i in range(N):
    graph[i]=[]
connect()
ans=0
BFS()
print(ans)