[백준] 17472번 다리 만들기 2
문제 링크
문제 설명
- 모든 섬을 다리로 연결
- 다리는 가로, 세로로 직선만 가능
- 다리 길이 2 이상
- 다리 길이 합의 최솟값 출력
- 연결이 불가능하면 -1 출력
풀이
- 섬에 번호를 매김
- BFS
- 다리 리스트를 구함
- 바다와 인접한 부분에서 다른 섬을 만날 때까지 직선 이동
- 다리 리스트에서 n-1개 선택
- 크루스칼, Union-find
코드
import sys
from collections import deque
def init():
ipt = sys.stdin.readline
h, w = map(int, ipt().split())
board = [list(map(int, ipt().split())) for _ in range(h)]
dy, dx = [1,-1,0,0], [0,0,1,-1]
return h, w, board, dy, dx, []
def set_board():
num = 1
visited = [[False] * w for _ in range(h)]
for y in range(h):
for x in range(w):
if not visited[y][x] and board[y][x]:
bfs(visited, (y, x), num)
num += 1
return num - 1
def bfs(visited, start, num):
sy, sx = start
visited[sy][sx] = True
q = deque([start])
while q:
cy, cx = q.popleft()
board[cy][cx] = num
for d in range(4):
ny = cy + dy[d]
nx = cx + dx[d]
if 0 <= ny < h and 0 <= nx < w:
if not visited[ny][nx] and board[ny][nx]:
visited[ny][nx] = True
q.append((ny, nx))
def set_edge_list():
for y in range(h):
for x in range(w):
if board[y][x]:
for d in range(4):
bridge = get_bridge((y, x), d)
if bridge:
edge_list.append(bridge)
def get_bridge(start, d):
y, x = start
n = board[y][x]
length = 0
while True:
y = y + dy[d]
x = x + dx[d]
length += 1
if 0 <= y < h and 0 <= x < w:
if board[y][x]:
if board[y][x] != n:
if length-1 >= 2:
return (n, board[y][x], length-1)
else:
return
else:
return
else:
continue
else:
return
def get_min_length():
count = 0
sum_cost = 0
edge_list.sort(key=lambda x: x[2])
parent = list(range(n+1))
for a, b, cost in edge_list:
ra = find_set(parent, a)
rb = find_set(parent, b)
if ra != rb:
union(parent, ra, rb)
sum_cost += cost
count += 1
if count == n-1:
return sum_cost
else:
return -1
def find_set(parent, x):
if parent[x] != x:
parent[x] = find_set(parent, parent[x])
return parent[x]
def union(parent, ra, rb):
parent[ra] = rb
h, w, board, dy, dx, edge_list = init()
n = set_board()
set_edge_list()
print(get_min_length())
Author And Source
이 문제에 관하여([백준] 17472번 다리 만들기 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-17472번-다리-만들기-2
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
- 모든 섬을 다리로 연결
- 다리는 가로, 세로로 직선만 가능
- 다리 길이 2 이상
- 다리 길이 합의 최솟값 출력
- 연결이 불가능하면 -1 출력
풀이
- 섬에 번호를 매김
- BFS
- 다리 리스트를 구함
- 바다와 인접한 부분에서 다른 섬을 만날 때까지 직선 이동
- 다리 리스트에서 n-1개 선택
- 크루스칼, Union-find
코드
import sys
from collections import deque
def init():
ipt = sys.stdin.readline
h, w = map(int, ipt().split())
board = [list(map(int, ipt().split())) for _ in range(h)]
dy, dx = [1,-1,0,0], [0,0,1,-1]
return h, w, board, dy, dx, []
def set_board():
num = 1
visited = [[False] * w for _ in range(h)]
for y in range(h):
for x in range(w):
if not visited[y][x] and board[y][x]:
bfs(visited, (y, x), num)
num += 1
return num - 1
def bfs(visited, start, num):
sy, sx = start
visited[sy][sx] = True
q = deque([start])
while q:
cy, cx = q.popleft()
board[cy][cx] = num
for d in range(4):
ny = cy + dy[d]
nx = cx + dx[d]
if 0 <= ny < h and 0 <= nx < w:
if not visited[ny][nx] and board[ny][nx]:
visited[ny][nx] = True
q.append((ny, nx))
def set_edge_list():
for y in range(h):
for x in range(w):
if board[y][x]:
for d in range(4):
bridge = get_bridge((y, x), d)
if bridge:
edge_list.append(bridge)
def get_bridge(start, d):
y, x = start
n = board[y][x]
length = 0
while True:
y = y + dy[d]
x = x + dx[d]
length += 1
if 0 <= y < h and 0 <= x < w:
if board[y][x]:
if board[y][x] != n:
if length-1 >= 2:
return (n, board[y][x], length-1)
else:
return
else:
return
else:
continue
else:
return
def get_min_length():
count = 0
sum_cost = 0
edge_list.sort(key=lambda x: x[2])
parent = list(range(n+1))
for a, b, cost in edge_list:
ra = find_set(parent, a)
rb = find_set(parent, b)
if ra != rb:
union(parent, ra, rb)
sum_cost += cost
count += 1
if count == n-1:
return sum_cost
else:
return -1
def find_set(parent, x):
if parent[x] != x:
parent[x] = find_set(parent, parent[x])
return parent[x]
def union(parent, ra, rb):
parent[ra] = rb
h, w, board, dy, dx, edge_list = init()
n = set_board()
set_edge_list()
print(get_min_length())
Author And Source
이 문제에 관하여([백준] 17472번 다리 만들기 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-17472번-다리-만들기-2
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
- BFS
- 바다와 인접한 부분에서 다른 섬을 만날 때까지 직선 이동
- 크루스칼, Union-find
import sys
from collections import deque
def init():
ipt = sys.stdin.readline
h, w = map(int, ipt().split())
board = [list(map(int, ipt().split())) for _ in range(h)]
dy, dx = [1,-1,0,0], [0,0,1,-1]
return h, w, board, dy, dx, []
def set_board():
num = 1
visited = [[False] * w for _ in range(h)]
for y in range(h):
for x in range(w):
if not visited[y][x] and board[y][x]:
bfs(visited, (y, x), num)
num += 1
return num - 1
def bfs(visited, start, num):
sy, sx = start
visited[sy][sx] = True
q = deque([start])
while q:
cy, cx = q.popleft()
board[cy][cx] = num
for d in range(4):
ny = cy + dy[d]
nx = cx + dx[d]
if 0 <= ny < h and 0 <= nx < w:
if not visited[ny][nx] and board[ny][nx]:
visited[ny][nx] = True
q.append((ny, nx))
def set_edge_list():
for y in range(h):
for x in range(w):
if board[y][x]:
for d in range(4):
bridge = get_bridge((y, x), d)
if bridge:
edge_list.append(bridge)
def get_bridge(start, d):
y, x = start
n = board[y][x]
length = 0
while True:
y = y + dy[d]
x = x + dx[d]
length += 1
if 0 <= y < h and 0 <= x < w:
if board[y][x]:
if board[y][x] != n:
if length-1 >= 2:
return (n, board[y][x], length-1)
else:
return
else:
return
else:
continue
else:
return
def get_min_length():
count = 0
sum_cost = 0
edge_list.sort(key=lambda x: x[2])
parent = list(range(n+1))
for a, b, cost in edge_list:
ra = find_set(parent, a)
rb = find_set(parent, b)
if ra != rb:
union(parent, ra, rb)
sum_cost += cost
count += 1
if count == n-1:
return sum_cost
else:
return -1
def find_set(parent, x):
if parent[x] != x:
parent[x] = find_set(parent, parent[x])
return parent[x]
def union(parent, ra, rb):
parent[ra] = rb
h, w, board, dy, dx, edge_list = init()
n = set_board()
set_edge_list()
print(get_min_length())
Author And Source
이 문제에 관하여([백준] 17472번 다리 만들기 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehj8896/백준-17472번-다리-만들기-2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)