17472. 다리 만들기 2
업데이트 시간 : 2023-04-06 07:08:28 +0000[Gold I] 다리 만들기 2 - 17472
성능 요약
메모리: 116368 KB, 시간: 152 ms
분류
구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색, 최소 스패닝 트리
문제 설명
섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 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을 출력한다.
💡 Solutions
📄 다리 만들기 2.py
N,M = map(int,input().split())
from collections import deque
matrix = [list(map(int,input().split())) for _ in range(N)]
is_travel = [[False for _ in range(M)] for _ in range(N)]
dx = (0,0,-1,1)
dy = (1,-1,0,0)
def bfs(start):
global group, groups
que = deque()
que.append(start)
groups[group] = [(start[0],start[1])]
while que:
x, y = que.popleft()
for d in (0,1,2,3):
nx = x + dx[d]
ny = y + dy[d]
if nx < 0 or ny <0 or nx >= N or ny >= M: continue
if is_travel[nx][ny] : continue
if matrix[nx][ny] == 0 : continue
is_travel[nx][ny] = True
matrix[nx][ny] = group
groups[group] += [(nx,ny)]
que.append((nx,ny))
return
edges = []
def find_route(X,Y,K):
que2 = deque()
for d in (0,1,2,3):
que2.append((X,Y))
# is_visited = [[False for _ in range(M)] for _ in range(N)]
# is_visited[X][Y] = True
bridge = [[0 for _ in range(M)] for _ in range(N)]
while que2:
x, y = que2.popleft()
nx = x + dx[d]
ny = y + dy[d]
if nx < 0 or ny <0 or nx >= N or ny >= M: continue
# if is_visited[nx][ny] : continue
if matrix[nx][ny] == 0:
bridge[nx][ny] = bridge[x][y] + 1
que2.append((nx,ny))
elif matrix[nx][ny] != K and bridge[x][y] >= 2:
edges.append((bridge[x][y], K, matrix[nx][ny])) # weight start end
group = 0
groups = dict()
for i in range(N):
for j in range(M):
if not is_travel[i][j] and matrix[i][j] == 1:
group += 1
is_travel[i][j] = True
matrix[i][j] = group
bfs((i,j))
# print(groups)
for k, island in groups.items():
for x, y in island:
find_route(x,y,k)
# print("내꺼",edges)
edges.sort()
parent = [i for i in range(group+1)]
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
answer= 0
cnt = 0
for w, s, e in edges:
sRoot = find(s)
eRoot = find(e)
if sRoot != eRoot:
if sRoot > eRoot:
parent[sRoot] = eRoot
else:
parent[eRoot] = sRoot
cnt += 1
answer += w
if cnt == group-1 : break
if cnt == group-1 : print(answer)
else : print(-1)