[BOJ 17472] 다리 만들기 2

문제

섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.

섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.

다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를 연결되었다고 한다. 다리의 양 끝은 섬과 인접한 바다 위에 있어야 하고, 한 다리의 방향이 중간에 바뀌면 안된다. 또, 다리의 길이는 2 이상이어야 한다.

다리의 방향이 중간에 바뀌면 안되기 때문에, 다리의 방향은 가로 또는 세로가 될 수 밖에 없다. 방향이 가로인 다리는 다리의 양 끝이 가로 방향으로 섬과 인접해야 하고, 방향이 세로인 다리는 다리의 양 끝이 세로 방향으로 섬과 인접해야 한다.

섬 A와 B를 연결하는 다리가 중간에 섬 C와 인접한 바다를 지나가는 경우에 섬 C는 A, B와 연결되어있는 것이 아니다.

다리의 총 길이: 13 → D는 2와 4를 연결하는 다리이고, 3과는 연결되어 있지 않다.	다리의 총 길이: 9 (최소)

다리가 교차하는 경우가 있을 수도 있다. 교차하는 다리의 길이를 계산할 때는 각 칸이 각 다리의 길이에 모두 포함되어야 한다.

C의 방향이 중간에 바뀌었다.	D의 길이가 1이다.	가로 다리인 A가 1과 가로로 연결되어 있지 않다.

나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.

출력

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

풀이

• 문제는 크게 세 가지 파트로 나누어 해결하였다.

  1. graph내의 섬(1)을 연결하고 고유 번호(k)를 부여한다.

     • dfs 함수로 탐색하였고 저장된 k는 실제 섬의 개수보다 +1개 많다.

  2. 각 섬의 원소를 출발지로 하여 동서남북으로 직선 탐색하였을 때, 다른 섬이 나오면 (다리 길이, 출발 번호, 도착 번호)로 간선 edge에 저장한다.

     • 모서리 범위를 벗어나지 않는지(in_range) 확인하고, 다리 길이 cnt를 조건에 맞게 늘려주거나 edge에 저장하거나 한다.

  3. 다리 길이가 짧은 순으로 정렬하여 크루스칼 알고리즘을 사용해 노드를 연결한다.

     • 이로써 최소 신장 트리(MST)가 만들어진다.

• 마지막으로 모든 섬이 연결되었음을 확인하는 check 함수에 통과시킨다.

  • 1번 노드의 parent[1]가 2번부터 전체 섬의 개수까지의 parent[i]와 같은지 확인하는 함수다.

  • 다른 사람의 풀이에서는 간선이 노드(k-1) - 1개임을 이용하여 num에 저장한 값으로 정답을 출력하였다.

    • answer if (answer > 0) and (num == k-2) else -1

소스 코드

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[0]*m for _ in range(n)]

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def in_range(a, b):
    return 0 <= a < n and 0 <= b < m

def dfs(x, y, cnt):
    graph[x][y] = cnt
    for l in range(4):
        nx, ny = x+dx[l], y+dy[l]
        if not in_range(nx, ny) or visited[nx][ny]:
            continue
        if graph[nx][ny] == 1:
            visited[nx][ny] = 1
            dfs(nx, ny, cnt)

    return

k = 1
for i in range(n):
    for j in range(m):
        if not visited[i][j] and graph[i][j] == 1:
            dfs(i, j, k)
            k += 1  # 5까지 기록됨

edge = set()

def distance(x, y, now):
    for l in range(4):
        cnt = 0  # 몇 칸 갔는지 체크
        nx, ny = x, y
        while in_range(nx+dx[l], ny+dy[l]):
            nx += dx[l]
            ny += dy[l]
            if graph[nx][ny] > 0 and graph[nx][ny] != now:
                if cnt >= 2:  # 다리 길이 최소 2칸 이상
                    edge.add((cnt, now, graph[nx][ny]))  # (cnt, now, next)
                break
            elif graph[nx][ny] == 0:
                cnt += 1
            else:  # ex. graph[nx][ny] == now
                break

for i in range(n):
    for j in range(m):
        if graph[i][j] > 0 :
            distance(i, j, graph[i][j])

parent = [i for i in range(k)]  # [0, 4+1]

def find_parent(x, parent):
    if parent[x] != x:
        parent[x] = find_parent(parent[x], parent)
    return parent[x]

def union_parent(a, b, parent):
    a = find_parent(a, parent)
    b = find_parent(b, parent)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

def check(parent):
    root = find_parent(1, parent)
    if all(find_parent(i, parent) == root for i in range(2, k)):
        return True
    return False

def main():
    # num = 0  ## 다른 사람의 풀이
    answer = 0  # min
    for (cnt, now, nxt) in sorted(edge):  # 정렬!
        if find_parent(now, parent) != find_parent(nxt, parent):
            union_parent(now, nxt, parent)
            answer += cnt
            # num += 1  ## 다른 사람의 풀이
    if check(parent):
        return answer
    else:
        return -1
    # return answer if (answer > 0) and (num == k-2) else -1  ## 다른 사람의 풀이

print(main())