[알고리즘] 백준 2146 다리만들기 파이썬
백준 2146 다리 만들기
'''
Problem Solving Baekjoon 2146_3
Author: Injun Son
Date: Dec 21, 2020
'''
import sys
sys.setrecursionlimit(10 ** 6)
from collections import deque
N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
check = [[False] * N for _ in range(N)]
dx = [-1, 0, 0, 1]
dy = [0, 1, -1, 0]
ans = sys.maxsize
count = 1
def print_board(board):
for i in range(N):
for j in range(N):
print(board[i][j], end=" ")
print("")
# 각 섬에 번호를 붙여줘서 그룹핑하는 함수
def dfs(y, x):
global count
check[y][x] = True
graph[y][x] = count
for i in range(4):
ny, nx = y + dy[i], x + dx[i]
if ny < 0 or ny >= N or nx < 0 or nx >= N:
continue
if check[ny][nx] == False and graph[ny][nx]:
dfs(ny, nx)
def bfs(z):
global ans
dist = [[-1] * N for _ in range(N)]
q = deque()
for i in range(N): # 섬들의 위치 모두 큐에 저장
for j in range(N):
if graph[i][j] == z:
q.append([i, j])
dist[i][j] = 0
while q:
y, x = q.popleft()
for i in range(4):
ny, nx = y + dy[i], x + dx[i]
if ny < 0 or ny >= N or nx < 0 or nx >= N:
continue
# 다른 섬에 도착한 경우
if graph[ny][nx] > 0 and graph[ny][nx] != z:
ans = min(ans, dist[y][x])
return
# 만약 바다이고, 간척 사업도 안된 곳이라면 새로 거리를 더해준다
if graph[ny][nx] == 0 and dist[ny][nx] == -1:
dist[ny][nx] = dist[y][x] + 1
q.append([ny, nx])
for i in range(N):
for j in range(N):
if check[i][j] == False and graph[i][j] == 1:
dfs(i, j)
count += 1
# 각각의 섬에 대하여 bfs로 간척을 하여 다른 섬에 도달한다
for i in range(1, count):
bfs(i)
print(ans)
알고리즘 문제를 안푼지 한 달 이상 됐다. 마지막 프로젝트를 했을 때 안드로이드 앱을 만드느라고 코틀린을 썼고, 우테코 프리코스 공부를 하느라 자바를 배웠다. 내일 부스트캠프 ai 1차 코테가 있어 일단 급하게 다시 조금이라도 감을 잡으려고 예전에 풀었던 문제의 코드를 다시 따라쳤다.
-
dfs를 돌려서 각 섬에 라벨링을 해준다.
-
각 섬에 대하여 bfs를 하는데, 섬의 각 칸에서 다른 섬으로 도착할 때까지 bfs를 하고, 매번 도착할 때마다 ans 글로벌 변수와 비교해서 갱신한다.
Author And Source
이 문제에 관하여([알고리즘] 백준 2146 다리만들기 파이썬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@injoon2019/알고리즘-백준-2146-다리만들기-파이썬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)