17472 다리만들기2

문제

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

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

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

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

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

아래 그림은 섬을 모두 연결하는 올바른 2가지 방법이고, 다리는 회색으로 색칠되어 있다. 섬은 정수, 다리는 알파벳 대문자로 구분했다.

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

다음은 올바르지 않은 3가지 방법이다

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

다리가 교차하는 경우가 있을 수도 있다. 교차하는 다리의 길이를 계산할 때는 각 칸이 각 다리의 길이에 모두 포함되어야 한다. 아래는 다리가 교차하는 경우와 기타 다른 경우에 대한 2가지 예시이다.

A의 길이는 4이고, B의 길이도 4이다. 총 다리의 총 길이: 4 + 4 + 2 = 10	다리 A: 2와 3을 연결 (길이 2) 다리 B: 3과 4를 연결 (길이 3) 다리 C: 2와 5를 연결 (길이 5) 다리 D: 1과 2를 연결 (길이 2) 총 길이: 12

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

입력

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

출력

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

 

 

 

그림이 짤리지만 문제를 읽으면 모두 이해갈 것이다.

 

처음에는 접근 방법을 몰라서 고민하다가 풀이를 잠깐 보았다.

 

핵심은 다음과 같다.

섬을 찾고 -> 라벨링을하고 -> 각 좌표에서 상,하,좌,우로 쭉 뻗어서 다리를 만들고 -> 크루스칼 알고리즘을 돌린다.

 

1. 섬을 찾는다.

bfs를 이용해서 찾는다.

 

2. 라벨링

섬의 좌표들에 같은 섬끼리 번호를 붙여준다.

 

3. 다리는 1개의 방향이므로 각 섬의 좌표에서 상,하,좌,우로 쭉 뻗는다.

이때 다른섬이면 다리를 추가하고 (길이는 2이상)

맵밖으로 나가면 종료하고

아니면 다리를 연장한다. (이때 자신의 섬을 가로질러갈 수 있으므로 자신의 섬일때는 길이를 0으로 초기화해줘야 한다)

 

4. 크루스칼 알고리즘을 돌린다.

이때, 모든 스패닝트리가 연결되었는지 확인하기 위해서, 모든 섬의 루트노드를 확인하는 과정이 꼭 필요하다.

 

자잘한 구현상의 실수 떄문에 반례를 찾아가면서 힘겹게 풀었다.

그래도 힌트를 조금씩 얻어가면서 스스로 문제를 해결해나가는 이러한 기분이 좋은것 같다.

 

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().rstrip().split(" "))

board = []
for _ in range(n):
    board.append(list(map(int, input().rstrip().split(" "))))

# 상,하,좌,우
direction_x = [-1, 1, 0, 0]
direction_y = [0, 0, -1, 1]

# 순회하면서 섬의 영역을 찾고 좌표를 저장한다.


def find_islands():
    global board, direction_x, direction_y
    visited = [[0]*(m) for _ in range(n)]

    q = deque()

    islands = []

    for row in range(n):
        for col in range(m):
            # 순회하다가 섬의 시작점으로 추정되는 곳에서 시작
            if(board[row][col] == 1 and visited[row][col] == 0):
                islands.append([])  # 새로운 섬 넣기
                q.append((row, col))
                visited[row][col] = 1

                while(len(q) != 0):
                    x, y = q.popleft()

                    islands[-1].append((x, y))  # 섬 좌표 1개씩 넣기
                    for i in range(4):
                        new_x = x+direction_x[i]
                        new_y = y+direction_y[i]

                        if(new_x >= 0 and new_x <= n-1 and new_y >= 0 and new_y <= m-1):
                            # 바다거나 방문한곳이면 패쓰
                            if(visited[new_x][new_y] == 0
                               and board[new_x][new_y]):
                                q.append((new_x, new_y))
                                visited[new_x][new_y] = 1

    return islands


# board의 섬좌표에 각각의 섬의 이름을 대입한다.
def naming_islands(islands):
    for idx, points in enumerate(islands):
        for point in points:
            x, y = point
            board[x][y] = idx+1  # 1부터 섬이름 붙임

# 섬의 각 좌표에서 상,하,좌,우로 직선을 그어 섬에 도달하는 다리를 만들고 저장한다.


def make_bridge(islands):
    global board, direction_x, direction_y
    graph = []

    for points in islands:
        for point in points:
            # 상,하,좌,우 로 직진

            for i in range(4):
                new_x, new_y = point
                curr_x, curr_y = point
                dist = 0
                while(1):
                    new_x = new_x+direction_x[i]
                    new_y = new_y+direction_y[i]

                    # 맵 벗어나면 종료
                    if(
                        new_x < 0 or new_x > n-1 or new_y < 0 or new_y > m-1
                    ):
                        break
                    # 다른 섬에 도착하면 종료
                    elif(
                        board[new_x][new_y] != 0 and  # 육지면서
                        (new_x, new_y) not in points  # 현재 섬에 포함되지 않는 => 다른섬
                    ):
                        # 다리의 최소길이는 2이상이어야함
                        if(dist >= 2):
                            graph.append(
                                (board[curr_x][curr_y],
                                 board[new_x][new_y], dist)
                            )
                        break
                    else:
                        # 바다면 다리길이 추가
                        if(board[new_x][new_y] == 0):
                            dist += 1

                        elif(board[new_x][new_y] >= 1):
                            # '''
                            # 아래처럼 0을 2번지나가는 경우까지 고려
                            # 1 1 1
                            # 1 0 1
                            # 0 1 1
                            # 0 0 0
                            # 0 1 0
                            # '''
                            dist = 0

    return graph


# 루트노드를 찾는 함수(재귀)


def find_root_nodes(x):
    global parents
    if(parents[x] != x):
        parents[x] = find_root_nodes(parents[x])
    return parents[x]


# union


def union(a, b):
    global parents
    a = find_root_nodes(a)
    b = find_root_nodes(b)
    if(a < b):
        parents[b] = a
    else:
        parents[a] = b


islands = find_islands()
naming_islands(islands)
graph = make_bridge(islands)
graph = sorted(graph, key=lambda x: x[2])

# 크루스칼 용 parent
parents = [0]*(1 + len(islands))
# 자기자신을 부모로
for i in range(1+len(islands)):
    parents[i] = i

answer = 0

for edge in graph:
    start, end, d = edge
    if(find_root_nodes(start) != find_root_nodes(end)):
        union(start, end)
        answer += d

# 모든 섬의 루트노드가 같은지 체크
allConnected = True
temp = find_root_nodes(1)
for i in range(1, len(islands)+1):
    if(temp != find_root_nodes(i)):  # 부모가 다른 노드가 있다면 스패닝트리로 합쳐지지 않은 것
        allConnected = False

if(allConnected == False or answer == 0):
    print(-1)
else:
    print(answer)

# for i in board:
#     print(" ".join(map(str, i)))
# print(graph)

# print(parents)
# print(answer)