2146.다리 만들기 - python

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

2146번: 다리 만들기

dfs/bfs를 응용하는 문제

기본적으로 섬의 개수나 크기는 한 번에 간단하게 끝나지만 이건 그 두 가지를 조합해서 풀어야 한다

섬의 거리를 구하는 방법은 각각 섬의 가장자리에서 시작해 가장 가까운 섬까지의 거리를 측정해야 한다.

섬의 가장자리를 구하는 방법은 일반적인 섬의 크기 구하는 방식처럼 한 칸씩 움직이다가  바다가 나오면 멈춤 그곳이 가장자리다.

그리고 다음 섬까지의 거리는 가장자리에서 시작해서 최단 경로 구하는 방식처럼 움직여 또 다른 섬이 나올 때까지 움직인다 현재 섬과 구별하기 위해 처음 섬은 2번 다음은 3번으로 1씩 증가시키면서 각각 섬을 구별해 준다

 

import sys
sys.setrecursionlimit(10**5)
a=int(input())
t=[]
for i in range(a):
    t.append(list(map(int,input().split())))    
r=len(t)
l=len(t[0])
n=2
mai=100000
def f(i,j):
    t[i][j]=n
    global g
    for x,y in [[1,0],[-1,0],[0,1],[0,-1]] :
        if 0<=i+x<r and 0<=j+y<l:
            if t[i+x][j+y]==1:
                f(i+x,j+y)
            elif t[i+x][j+y]==0:
                if [i,j] not in g:
                    g.append([i,j])
                    
def ff(g):
    n1=0
    t1=[list(i) for i in t]
    while g:
        g1=[]
        for i,j in g:
            t1[i][j]=n
            for x,y in [[1,0],[-1,0],[0,1],[0,-1]] :
                if 0<=i+x<r and 0<=j+y<l:
                    if t1[i+x][j+y]==0:
                        if [i+x,j+y] not in g1:
                            g1.append([i+x,j+y])
                
                    elif t1[i+x][j+y]!=n:
                        return n1
        g=g1 
        n1+=1

for i in range(r):
    for j in range(l):
        if t[i][j]==1:
            g=[]
            f(i,j)
            mi=ff(g)
            if mi<mai:
                mai=mi
            n+=1
print(mai)