다리만들기2 Python(백준, BAEKJOON)

난이도 : Gold 3

문제번호 : 17472

문제 주소 및 출처입니다.

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

17472번: 다리 만들기 2

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다. 섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다. 다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를 연결되었다고 한다. 다리의 양 끝은 섬과 인접한 바다 위에 있어야 하고, 한 다리의 방향이 중간에 바뀌면 안된다. 또, 다리의 길이는 2 이상이어야 한다. 다리의 방향이 중간에 바뀌면 안되기 때문에, 다리의 방향은 가로 또는 세로가 될 수 밖에 없다. 방향이 가로인 다리는 다리의 양 끝이 가로 방향으로 섬과 인접해야 하고, 방향이 세로인 다리는 다리의 양 끝이 세로 방향으로 섬과 인접해야 한다. 섬 A와 B를 연결하는 다리가 중간에 섬 C와 인접한 바다를 지나가는 경우에 섬 C는 A, B와 연결되어있는 것이 아니다.  아래 그림은 섬을 모두 연결하는 올바른 2가지 방법이고, 다리는 회색으로 색칠되어 있다. 섬은 정수, 다리는 알파벳 대문자로 구분했다. 다음은 올바르지 않은 3가지 방법이다. 다리가 교차하는 경우가 있을 수도 있다. 교차하는 다리의 길이를 계산할 때는 각 칸이 각 다리의 길이에 모두 포함되어야 한다. 아래는 다리가 교차하는 경우와 기타 다른 경우에 대한 2가지 예시이다. 나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자.

 

입력

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

출력

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

제한

1 ≤ N, M ≤ 10 3 ≤ N×M ≤ 100 2 ≤ 섬의 개수 ≤ 6

 

---

2. 문제풀이

보자마자 모든섬을 연결해야 하는데 최소비용으로 연결해라. 라고 적혀있어서 MST를 떠올렸다. 그래서 구현하기 쉬운 크루스칼 알고리즘을 이용하여 문제를 풀었다. 모든섬은 1로 표현이 되어있다. 그렇지만 모든섬을 구분하기 위해 각섬마다 번호를 다르게 주었다.(노드번호) 이후 섬의 상하좌우를 돌면서 다른섬과 연결이 가능한 부분을 찾아 간선정보를 생성했다. 이후 사이클이 생기지 않게하며 제일작은 간선부터 연결하여 모든 섬을 연결하면 끝이다.

---

3. 소스코드

# Gold 3 17472 다리만들기2
 
#상 하 좌 우
move_list = [(-1, 0), (1, 0), (0, -1), (0, 1)]
 
#섬정보를 변경한다.
def change_number(y, x, idx):
    for dy, dx in move_list:
        d_y, d_x = y+dy, x+dx
        if d_y < 0 or d_x < 0 or d_y >= row or d_x >= col:
            continue
        if island_map[d_y][d_x] == 0:
            continue
        if island_map[d_y][d_x] == 1:
            island_map[d_y][d_x] = idx
            change_number(d_y, d_x, idx)
 
#간선의 정보를 가져온다.
def find_edge(y, x, idx):
    for dy, dx in move_list:
        d_y, d_x = y+dy, x+dx
        count = 0
        while True:
            #밖으로 벗어나면 취소
            if d_y < 0 or d_x < 0 or d_y >= row or d_x >= col:  break
            #자기자신과 만나면 취소
            if island_map[d_y][d_x] == idx: break
            #진행방향이 바다라면 한번더 진행하고 거리 count
            if island_map[d_y][d_x] == 0:
                d_y += dy
                d_x += dx
                count += 1
                continue
            #그외의 경우이다.
 
            #길이가 2 이하라면 취소
            if count < 2: break
            #그게 아니라면 거리 추가하기
            num = island_map[d_y][d_x]
            cost = distances[idx-2][num-2]
            if cost == 0:  distances[idx-2][num-2] = count
            else: distances[idx-2][num-2] = min(cost, count)
            break
 
#부모의 정보를 가져온다.
def getParent(idx):
    if parent[idx] == idx:
        return idx
    parent[idx] = getParent(parent[idx])
    return parent[idx]
 
#부모를 병합한다. 작은 부모에게 병합
def unionParent(a, b):
    a = getParent(a)
    b = getParent(b)
    if a < b: parent[b] = a
    else: parent[a] = b
 
#부모가 같은지 확인한다.
def find(a, b):
    a = getParent(a)
    b = getParent(b)
    return a == b
 
 
#가로세로 크기입력받기
row , col = map(int, input().split())
#부모노드 확인용
parent = [i for i in range(6)]
#각 이동 거리에 대한 배열
distances = [[0 for j in range(6)] for i in range(6)]
#노드 연결 비용
costs = []
#최단거리
answer = 0
 
#섬정보 저장
island_map = []
for i in range(row):
    island_map.append(list(map(int, input().split())))
 
number = 2
 
#섬정보 바꾸기
for i in range(row):
    for j in range(col):
        if island_map[i][j] == 1:
            island_map[i][j] = number
            change_number(i, j, number)
            number += 1
 
#섬과 연결되있는 부분 찾기
for i in range(row):
    for j in range(col):
        if island_map[i][j]:
            find_edge(i, j, island_map[i][j])
 
#관리하기 쉽도록 데이터 구조 편집
for i in range(6):
    for j in range(6):
        if distances[i][j] and [j, i, distances[i][j]] not in costs:
            costs.append([i, j, distances[i][j]])
 
#거리를 기준으로 정렬한다.
costs = sorted(costs, key = lambda x : x[2])
 
#거리계산하고 부모노드 병합하기
for cost in costs:
    if not find(cost[0], cost[1]):
        answer += cost[2]
        unionParent(cost[0], cost[1])
 
#모든섬이 연결되었나 확인한다.
for i in range(number-2):
    #하나라도 연결이 되어있지 않다면 -1로 바꾼다
    if getParent(i) != 0:
        answer = -1
        break
 
print(answer)