백준 17472번 다리 만들기 2 (Python)

섬으로 이루어진 나라가 있고 모든 섬을 다리로 연결하려고 할 때, 모든 다리의 길이의 합이 최소가 되도록 해야합니다.

다리의 길이는 최소 2여야 하고, 다리는 직선 모양으로 중간에 방향이 바뀌면 안 됩니다.

방향이 가로인 다리는 무조건 두 섬이 가로 방향으로 섬과 인접해야지만 두 섬이 연결됩니다. 방향이 세로일 경우는 무조건 두 섬이 세로 방향으로 섬과 인접해야지만 두 섬이 연결됩니다.

다리는 교차가 가능하며 총 다리의 길이를 구할 때, 겹쳐진 부분은 각 다리의 길이에 모두 포함되어야 합니다.

 

이번 문제는 보자마자 조금 시간이 오래 걸릴 것으로 예상되었습니다. 하지만, 각 조건이 1 ≤ N, M ≤ 10, 3 ≤ N×M ≤ 100, 2 ≤ 섬의 개수 ≤ 6 적은 숫자들로 구성된 것을 확인했고, 구현만 한다면 맞출 수 있을 것이라고 생각했습니다.

 

 

 

구현 1. 각 섬에 포함된 좌표 구하기

우선 각 섬을 이루고 있는 좌표들을 모아줄 수 있도록 했습니다. islands 2중 배열을 선언했고 섬의 개수가 최대 6개이므로 행을 7개로 선언했습니다. (섬은 1번 섬부터 시작한다고 가정했기 때문)

islands = [[] for _ in range(7)]

모든 칸들을 탐색하면서 섬이 나올 경우 해당 좌표에서 DFS를 통해 해당 섬(num)안에 포함된 좌표를 모두 islands[num] 안에 넣어줄 수 있도록 했습니다.

def findEachIsland(i, j, num):
    global N, M
    for k in range(4):
        ni, nj = i+moves[k][0], j+moves[k][1]
        if not (0 <= ni < N and 0 <= nj < M) or visited[ni][nj] or board[ni][nj] == 0:
            continue

        visited[ni][nj] = num
        islands[num].append((ni, nj))
        findEachIsland(ni, nj, num)


...
num = 1
for i in range(N):
    for j in range(M):
        if board[i][j] == 1 and not visited[i][j]:
            visited[i][j] = num
            islands[num].append((i, j))
            findEachIsland(i, j, num)
            num += 1

num을 통해 각 섬마다 표시를 해줄 수 있도록 했습니다.

또한 N*M 크기의 배열 visited를 선언한 뒤, 각 좌표마다 자신의 섬 번호를 저장할 수 있도록 해주었습니다.

 

visited 배열과 같은 경우 다음과 같이 생성이 됩니다.

# 예시
0 0 0 0 0 0 1 1
1 1 0 0 0 0 1 1
1 1 0 0 0 0 0 0
1 1 0 0 0 1 1 0
0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1

# visited 내부
0 0 0 0 0 0 1 1
2 2 0 0 0 0 1 1
2 2 0 0 0 0 0 0
2 2 0 0 0 3 3 0
0 0 0 0 0 3 3 0
0 0 0 0 0 0 0 0
4 4 4 4 4 4 4 4

 

 

 

구현 2. 간선 구하기

각 섬의 위치를 알았으니 각 섬을 이을 수 있는 다리를 구해보도록 하겠습니다.

다리와 같은 경우 각 섬마다 이을 수 있는 다리가 있다면 최소 길이의 다리를 저장하도록 했습니다.

 

간선을 저장할 변수는 2중 배열로 각 섬마다 다른 섬간의 다리 길이 정보를 저장할 수 있도록 7행 7열로 선언했습니다.

또한, 모든 edge 정보를 저장하기 위해 allEdges를 선언해주었습니다.

edges = [[0 for __ in range(7)] for _ in range(7)]
allEdges = []

 

간선 구하기 함수의 인자는 현재 좌표와 다리의 방향, 다리를 시작하는 섬의 번호, 다리 길이로 이루어져 있습니다.

def findEachEdges(i, j, nextMoves, num, count):

 

만약 현재 좌표가 바다라면

다리의 방향으로 한 칸 움직이도록 했습니다.

if visited[i][j] == 0:
    ni, nj = i+nextMoves[0], j+nextMoves[1]
    if not (0 <= ni < N and 0 <= nj < M):
        return

    findEachEdges(ni, nj, nextMoves, num, count+1)

 

 

만약 바다가 아니라면

현재 좌표의 섬이 다리를 시작한 섬의 번호와 같거나 다리의 길이가 2보다 작다면 그냥 함수를 return 해주었습니다.

현재 좌표의 섬이 다리를 시작한 섬의 번호와 다르고 다리의 길이가 2보다 크거나 같다면 다리를 세울 조건을 만족하기 때문에 다리 정보를 저장할 수 있도록 했습니다.

 

만약 반대 섬에서 이미 다리를 시작한 섬과 이은 다리 정보를 가지고 있을 경우, 이미 두 섬의 최소 길이 다리를 알고 있다는 의미이므로 그냥 반대 섬의 다리 정보를 저장하도록 했습니다.

만약 반대 섬에 다리 정보가 없다면 아직 두 섬은 다리에 대한 정보가 없으므로 최소 길이의 다리를 찾을 수 있도록 했습니다.

else: # visited[i][j] != 0 일 경우
    if visited[i][j] != num and count >= 2:
        newIsland = visited[i][j]
        if edges[newIsland][num] == 0:
            newCount = count if edges[num][newIsland] == 0 else min(
                edges[num][newIsland], count)
            edges[num][newIsland] = newCount
            allEdges.append((newCount, num, newIsland))
        else:
            edges[num][newIsland] = edges[newIsland][num]
    else:
        return

섬 번호가 num인 섬과 newIsland 섬간의 다리 길이를 측정해 최소 다리 길이를 edges[num][newIsland] 에 저장해줍니다.

allEdges에는 (다리길이, 시작 섬, 끝 섬) 정보가 저장되도록 했습니다.

 

전체 코드

def findEachEdges(i, j, nextMoves, num, count):
    if visited[i][j] == 0:
        ni, nj = i+nextMoves[0], j+nextMoves[1]
        if not (0 <= ni < N and 0 <= nj < M):
            return

        findEachEdges(ni, nj, nextMoves, num, count+1)
    else:
        if visited[i][j] != num and count >= 2:
            newIsland = visited[i][j]
            if edges[newIsland][num] == 0:
                newCount = count if edges[num][newIsland] == 0 else min(
                    edges[num][newIsland], count)
                edges[num][newIsland] = newCount
                allEdges.append((newCount, num, newIsland))
            else:
                edges[num][newIsland] = edges[newIsland][num]
        else:
            return

...
for i in range(1, num):
    for x, y in islands[i]:
        for j in range(4):
            nx, ny = x+moves[j][0], y+moves[j][1]

            if not (0 <= nx < N and 0 <= ny < M) or visited[nx][ny] == i:
                continue

            findEachEdges(nx, ny, moves[j], i, 0)

 

 

 

구현 3. 모든 다리 길이의 최소 합 구하기

우선 allEdges 배열을 다리 길이를 기준으로 오름차순으로 정렬하고 Union-Find를 통해 연결 가능한 섬끼리 묶고 하나의 섬으로 묶을 수 있는지 확인해주었습니다.

 

union, find 함수를 통해 연결된 두 노드를 하나로 묶어줄 수 있도록 했습니다.

또한, 두 노드의 부모가 원래 달랐다면 True를 부모가 원래 같았다면 False를 반환해주도록 했습니다. 두 노드의 부모가 원래 달랐다면 두 노드는 아직 연결된 적이 없었다는 것이므로 해당 간선의 길이를 정답에 더해줍니다. 두 노드의 부모가 같았다면 두 노드는 이미 연결되어 있으므로 해당 간선은 포함되지 않습니다.

def find(node):
    if parent[node] == node:
        return node
    parent[node] = find(parent[node])
    return parent[node]


def union(a, b):
    pa = find(a)
    pb = find(b)

    if pa != pb:
        parent[pa] = pb
    return pa != pb

...
allEdges.sort()
for count, n1, n2 in allEdges:
    answer += count if union(n1, n2) else 0

 

이 후, 모든 노드가 하나의 부모를 가리키고 있다면 모든 노드가 연결된 것으로 구한 정답을 반환하고 다른 부모를 가리키는 노드가 있다면 연결이 불가능한 상태이므로 -1을 반환합니다.

for i in range(1, num-1):
    if find(i) != find(i+1):
        answer = -1
        break
print(answer)

 

 

 

전체 코드

def findEachIsland(i, j, num):
    global N, M
    for k in range(4):
        ni, nj = i+moves[k][0], j+moves[k][1]
        if not (0 <= ni < N and 0 <= nj < M) or visited[ni][nj] or board[ni][nj] == 0:
            continue

        visited[ni][nj] = num
        islands[num].append((ni, nj))
        findEachIsland(ni, nj, num)


def findEachEdges(i, j, nextMoves, num, count):
    if visited[i][j] == 0:
        ni, nj = i+nextMoves[0], j+nextMoves[1]
        if not (0 <= ni < N and 0 <= nj < M):
            return

        findEachEdges(ni, nj, nextMoves, num, count+1)
    else:
        if visited[i][j] != num and count >= 2:
            newIsland = visited[i][j]
            if edges[newIsland][num] == 0:
                newCount = count if edges[num][newIsland] == 0 else min(
                    edges[num][newIsland], count)
                edges[num][newIsland] = newCount
                allEdges.append((newCount, num, newIsland))
            else:
                edges[num][newIsland] = edges[newIsland][num]
        else:
            return


def find(node):
    if parent[node] == node:
        return node
    parent[node] = find(parent[node])
    return parent[node]


def union(a, b):
    pa = find(a)
    pb = find(b)

    if pa != pb:
        parent[pa] = pb
    return pa != pb


N, M = list(map(int, input().split()))
board = [list(map(int, input().split())) for _ in range(N)]
visited = [[0 for _ in range(M)] for __ in range(N)]
islands = [[] for _ in range(7)]
edges = [[0 for __ in range(7)] for _ in range(7)]
allEdges = []
moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]
parent = [i for i in range(7)]
answer = 0

num = 1
for i in range(N):
    for j in range(M):
        if board[i][j] == 1 and not visited[i][j]:
            visited[i][j] = num
            islands[num].append((i, j))
            findEachIsland(i, j, num)
            num += 1

for i in range(1, num):
    for x, y in islands[i]:
        for j in range(4):
            nx, ny = x+moves[j][0], y+moves[j][1]

            if not (0 <= nx < N and 0 <= ny < M) or visited[nx][ny] == i:
                continue

            findEachEdges(nx, ny, moves[j], i, 0)

allEdges.sort()
for count, n1, n2 in allEdges:
    answer += count if union(n1, n2) else 0

for i in range(1, num-1):
    if find(i) != find(i+1):
        answer = -1
        break
print(answer)