백준 - 다리 만들기2(feat.python)

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

문제 요구사항

모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든 섬을 연결하는 것이 불가능하면 -1을 출력한다.

문제 풀이

이 문제를 푸는 로직은 크게 4가지로 나눌 수 있습니다.

• 1. 모든 섬에 번호 붙이기(dfs/bfs)
• 2. 모든 섬끼리의 거리 구하기(브루트포스)
• 3. MST(최소 신장트리) 만들기(kruskal)
• 4. 모든 섬이 연결되었나 확인하기

모든 섬에 번호 붙이는 로직은 다음 문제를 풀어보면 참 좋을 것 같습니다.
https://www.acmicpc.net/problem/2667

# 하나의 섬 번호 붙이기
def dfs(x,y,num) :

    if graph[x][y] != 0: return
    graph[x][y] = num
    for i in range(4):
        cx = x + dx[i]
        cy = y + dy[i]
        if 0 <= cx < n and 0 <= cy < m :
             dfs(cx, cy, num)

# 모든 섬에 번호붙이기
def numbering():
    no = 1
    for i,j in islands:
        if graph[i][j] == 0:
            dfs(i,j,no)
            no += 1
    return no-1

이제, 섬의 거리를 섬을 연결해야 하는데, 주의해야할 사항들이 있습니다.

• 한 방향으로만 다리를 만들어나가야한다.
• 다리의 길이가 2이상이여야한다.
• 다리가 교차하는 것을 허용

이렇게 호흡이 긴 문제를 풀 때는 특히나 더 문제의 조건을 꼼꼼히 읽어야합니다.
위의 조건을 만족하는 모든 섬과 섬의 거리를 distance 배열에 담아줍니다.

# 모든 섬과 섬 사이의 거리 찾기
def searchAllDistance():
    for i,j in islands:
        search(i,j)

# 주변 섬과 섬까지의 거리 찾기
def search(x,y):
    u = graph[x][y] # 현재 섬
    for i in range(4):
        cx = x + dx[i]
        cy = y + dy[i]
        v = 0 # 다른 섬
        dis = 0
        while(0 <= cx < n and 0 <= cy < m and graph[cx][cy] == -1): # 바다
            dis += 1
            cx += dx[i]
            cy += dy[i]
            # 바다가 아니라 섬을 만났다면?
            if 0 <= cx < n and 0 <= cy < m and graph[cx][cy] > 0 :
                v = graph[cx][cy] #
		
        # u섬과의 거리가 2이상, u가 조건을 만족하는 섬일 때
        if dis > 1 and v > 0 and v != u:
            distance.append((dis,u,v))

이제 distance배열을 거리를 기준으로 비내림차순으로 정렬을 해준 후, kruskal알고리즘을 적용해줍니다.

distance.sort()
ans = 0
for dis, u, v in distance:
    if union(u,v):
        ans += dis

마지막으로 모든 섬이 연결될 수 있는지 판별해준다.

print(ans) if isLinked() else print(-1)

전체 코드

import sys
input = lambda : sys.stdin.readline().rstrip()
# 하나의 섬 번호 붙이기
def dfs(x,y,num) :

    if graph[x][y] != 0: return
    graph[x][y] = num
    for i in range(4):
        cx = x + dx[i]
        cy = y + dy[i]
        if 0 <= cx < n and 0 <= cy < m :
             dfs(cx, cy, num)

# 모든 섬에 번호붙이기
def numbering():
    no = 1
    for i,j in islands:
        if graph[i][j] == 0:
            dfs(i,j,no)
            no += 1
    return no-1
# 모든 섬과 섬 사이의 거리 찾기
def searchAllDistance():
    for i,j in islands:
        search(i,j)

# 주변 섬과 섬까지의 거리 찾기
def search(x,y):
    u = graph[x][y] # 현재 섬
    for i in range(4):
        cx = x + dx[i]
        cy = y + dy[i]
        v = 0 # 다른 섬
        dis = 0
        while(0 <= cx < n and 0 <= cy < m and graph[cx][cy] == -1): # 바다
            dis += 1
            cx += dx[i]
            cy += dy[i]
            # 바다가 아니라 섬을 만났다면?
            if 0 <= cx < n and 0 <= cy < m and graph[cx][cy] > 0 :
                v = graph[cx][cy] #

        if dis > 1 and v > 0 and v != u:
            distance.append((dis,u,v))

def find(x):
    if parents[x] < 0 : return x
    parents[x] = find(parents[x])
    return parents[x]

def union(x, y):
    x = find(x)
    y = find(y)

    if x == y : return False

    if parents[x] < parents[y]:
        parents[x] += parents[y]
        parents[y] = x
    else:
        parents[y] += parents[x]
        parents[x] = y
    return True
# 모든 섬이 연결 됐니?
def isLinked():
    pivot = find(1)
    for i in range(2, no+1):
        if find(i) != pivot:
            return False
    return True
n,m = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(n)]
islands = []
dx = [1,0,-1,0]
dy = [0,1,0,-1]
# islands 초기화
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            islands.append((i,j))
        graph[i][j] -= 1

# 1. 섬 번호 붙이기(dfs)
no = numbering()
# for i in range(n):
#     print(' '.join(map(str,graph[i])))

# 2. 섬 사이의 모든 거리 구하기
distance = []
searchAllDistance()
# 3. MST 찾기(Kruskal)
parents = [-1 for i in range(no + 1)]
distance.sort()
ans = 0
for dis, u, v in distance:
    if union(u,v):
        ans += dis

# 4. 모든 섬이 연결될 수 있니?
print(ans) if isLinked() else print(-1)