[Python][백준] 17472번 다리 만들기 2

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

공부 날짜 : 2023.02.10
정답 참조 여부 : X

여러개의 섬들이 있고 각 섬을 연결할 다리를 건설하고자 한다.
다리의 길이는 2 이상이여야 하며, 칸이 겹치더라도 별개의 다리로 간주된다.

이때 모든 섬들을 연결 하는 다리의 최소 길이를 구하는 문제다.

---

최소신장트리 알고리즘을 새로 배울 수 있었던 문제.

일단 가장먼저 1로만 표기된 섬들을 BFS 탐색으로 모두 구분시켜 주었다.
가장 편한 방법은 1,2,3,4로 구분하는 방법이지만 1로이미 표기 되어있어서 나는 'A','B','C' 로 구분했다.

그 다음으로 다리가 가로 혹은 세로로만 만들 수 있기 때문에, 가로로 탐색하고 세로로 탐색하며 각 섬들을 연결 할 수있는 다리를 구했는데, 이때 최소길이가 되는 다리만 구했다.

이 부분 구현에서 많이 해멨는데, a -> a를 연결하는 다리를 만들거나
다리가 안된다고 느끼면 다리길이를 초기화 해야하는데 초기화를 제대로 하지않아
만들수 없는 다리를 만드는 경우도 있어서 조건을 구현하는데 조금 애먹었다.

연결 가능한 다리와 길이가 구해졌다면 가중치(길이)있는 그래프가 완성되었다.

여기서 가중치를 최소화 하는 트리를 만드는게 목표인데 MST개념을 전혀 몰라서 결국 검색해봤다.
물론 정답을 참조 한건 아니고 최소가중치트리 라고 검색했더니 최소신장트리가 나와서 해당 개념을 공부 할 수 있었다. 이거 검색 안 하고 직접 알고리즘 만들어서 최소신장트리 구하면 논문한 편 쓸 수있었는데 ㄲㅂ

최소신장트리의 구현은 어렵지 않았지만 불가능 판단이 좀 어려웠다.
처음에는 간선의 개수만 세서 간선이 n-1이 되면 성공 그 전에 더 탐색가능한 지역이 없으면 불가능이라고 판단했다.
이 경우 못가는 섬이 있더라도 사이클을 만들면서 간선을 추가해서 오답이 나왔다.
사이클 방지를 위해 탐색 노드를 체크하는 딕셔너리를 만들었고, 이미 탐색한 노드면 더 탐색하지 않도록 설정했으며 간선의 개수가 n-1개, 탐색한 노드가 n개가 되면 성공으로 설정 했더니 정답으로 나왔다.

소스코드

import sys
from collections import deque
import heapq
input = sys.stdin.readline
################################################################
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

################################################################
n, m = map(int, input().split())

island = [list(map(int, input().split())) for _ in range(n)]

count_island = 0

# 각 섬들과 다른 섬들을 이어주는 경로를 저장하는 변수
load = {}

################################################################
island_char = ord("A")

# 모든 섬들을 구분하기 'A' ~ 'F'
for i in range(n):
    for j in range(m):
        if island[i][j] == 0:
            island[i][j] = '0'
            continue
        # 섬을 찾으면
        if island[i][j] == 1:
            # 섬의 개수 추가
            count_island += 1

            # 해당섬의 명칭 변경
            island[i][j] = chr(island_char)

            # 해당 섬 추가
            load[chr(island_char)] = {}

            # BFS로 같은 섬들 전부 같은 명칭으로 변경
            visit = deque()
            visit.append((i, j,))

            while visit:
                x, y = visit.pop()

                for dir in range(4):
                    nx = x + dx[dir]
                    ny = y + dy[dir]

                    if nx < 0 or nx >= n or ny < 0 or ny >= m or island[nx][ny] != 1:
                        continue

                    island[nx][ny] = chr(island_char)
                    visit.append((nx, ny,))

            # 다른 섬들은 다른 알파벳
            island_char += 1


# for i in island:
#     print(i)
#
# print("#############################")
################################################################
# 가로방향으로 놓을 수 있는 모든 다리 체크
for i in range(n):
    s = False
    len_load = 0
    for j in range(1, m):
        # 가로방향 체크시 섬이 바다와 맞닿으면 시작점은 해당 섬
        if str(island[i][j-1]).isalpha() and island[i][j] == '0':
            s = island[i][j-1]

        # 시작섬이 있고, 해당칸이 바다이면 다리길이 늘리기
        if s and island[i][j] == '0':
            len_load += 1

        # 시작섬이 있고, 다른 섬에 도착했을 때
        if s and str(island[i][j]).isalpha():
            # 다리의 길이가 2 이상이고,
            if len_load >= 2 and island[i][j] != s:
                # 해당 섬까지의 경로가 최단경로이면 갱신
                # 이전에 탐색되지 않은 경로면 그냥 추가
                if load[s].get(island[i][j], 11) > len_load:
                    load[s][island[i][j]] = len_load
                    load[island[i][j]][s] = len_load

                    # 그 다음 다시 다리길이 초기화, 시작섬 삭제
                    len_load = 0
                    s = False

            # 다리길이가 2이상이 안되면 시작섬 삭제, 다리길이 초기화
            else:
                len_load = 0
                s = False

            # 하나의 행에 2개의 다리가 놓일 수 있으므로 초기화
            len_load = 0
            s = False

# 세로방향 다리 체크
for j in range(m):
    s = False
    len_load = 0
    for i in range(1, n):
        # 세로방향 체크시 섬이 바다와 맞닿으면 시작점은 해당 섬
        if str(island[i - 1][j]).isalpha() and island[i][j] == '0':
            s = island[i-1][j]

        if s and island[i][j] == '0':
            len_load += 1

        # 시작섬이 있고, 다른 섬에 도착했을 때
        if s and str(island[i][j]).isalpha():
            #  다리 길이가 2 이상이고
            if len_load >= 2 and island[i][j] != s:
                # 이전에 탐색한 다리길이 보다 짧으면 거리 갱신
                # 경로와 열 추가 행, 열은 양수 음수로 구분
                if load[s].get(island[i][j], 11)> len_load:
                    load[s][island[i][j]] = len_load
                    load[island[i][j]][s] = len_load
                    len_load = 0
                    s = False

            # 다리길이가 1이면 길이 초기화, 시작섬 삭제
            else:
                len_load = 0
                s = False

            # 하나의 행에 2개의 다리가 놓일 수 있으므로 초기화
            len_load = 0
            s = False
#
# for i in load.items():
#     print(i)

################################################################
# 만들어진 그래프에서 최소신장 트리 찾기
cost = []
heapq.heappush(cost, (0, 'A',))
visited = {}

answer = 0
i = 0
while True:
    if i == count_island and len(visited) == count_island:
        print(answer)
        break

    if not cost:
        print(-1)
        break

    load_cost, node = heapq.heappop(cost)
    if visited.get(node, False):
        continue

    visited[node] = True
    answer += load_cost

    for key, values in load[node].items():
        if not visited.get(key, False):
            heapq.heappush(cost, (values, key,))

    i += 1