알고리즘/백준
[BOJ/백준] 17472 다리 만들기 2 파이썬
개발싫어
2021. 12. 3. 23:32
728x90
문제 링크 : https://www.acmicpc.net/problem/17472
17472번: 다리 만들기 2
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.
www.acmicpc.net
예전에 풀었던 걸 MST로 다시 풀어봤다.
예전에는 BFS,DFS로 완탐으로 해결했었다.
이번에는 BFS, MST로 해결했다.
BFS로 각 섬에 번호 매기면서 섬의 가장자리를 구한다.
이때 해당 점에서 이동하려는 점이 격자판 안에 있고 물인 경우 가장자리로 판별해서 저장했다.
(x,y,방향) 이때 방향은 해당 칸으로 온 방향이다.
구한 가장자리에서 다리를 만들면서 유효한 다리 정보를 생성한다.
이때는 구한 가장자리의 정보를 가지고 다리를 생성한다.
저장한 방향정보 가지고 범위를 벗어나거나 다른 섬을 만날때까지 진행한다.
다른 섬을 만났다면 다리 정보를 생성하자.
(출발 다리 번호, 도착 다리 번호, 길이)
다음 다리 정보를 길이순으로 오름차순해서 정렬한 후 MST에 사용하자
마지막 MST는 크루스칼을 이용했다.
from sys import stdin
from collections import deque
input = stdin.readline
dx = [-1,1,0,0]
dy = [0,0,-1,1]
n,m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
edges = []
def solv():
global parent
max_num = set_area_num()
parent = [i for i in range(max_num)]
candidate_bridge = set_candidate_bridge()
print(kruskal(candidate_bridge,max_num))
def kruskal(candidate_bridge, max_num):
bridge_count = 0
length = 0
for a,b,c in candidate_bridge:
if not is_same_parent(a,b):
union(a,b)
bridge_count += 1
length += c
if bridge_count == max_num-3:
return length
return -1
def find(target):
global parent
if parent[target] == target:
return target
parent[target] = find(parent[target])
return parent[target]
def union(a,b):
global parent
a = find(a)
b = find(b)
if a != b:
if a > b:
parent[a] = b
else:
parent[b] = a
def is_same_parent(a,b):
return find(a) == find(b)
def set_candidate_bridge():
candidate_bridge = set()
for x,y,d in edges:
start = board[x][y]
length = 0
while True:
x += dx[d]
y += dy[d]
if boundaray_validator(x,y):
end = board[x][y]
if end != 0:
if start != end and length >= 2:
candidate_bridge.add((start,end,length))
break
length += 1
else:
break
candidate_bridge = sorted(candidate_bridge, key=lambda x:x[2])
return candidate_bridge
def set_area_num():
num = 2
for x in range(n):
for y in range(m):
if board[x][y] == 1:
bfs(x,y,num)
num += 1
return num
def bfs(sx,sy,num):
global board,edges
q = deque([(sx,sy)])
board[sx][sy] = num
while q:
x,y = q.pop()
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
if boundaray_validator(nx,ny):
if board[nx][ny] == 1:
board[nx][ny] = num
q.appendleft((nx,ny))
elif board[nx][ny] == 0:
edges.append((x,y,d))
def boundaray_validator(x,y):
if x < 0 or y < 0 or x >= n or y >= m:
return False
return True
solv()