[boj]2146 다리만들기 - 파이썬, pypy3

www.acmicpc.net/problem/2146

2146번: 다리 만들기

[해설]

1. BFS를 통해 각 섬의 영역 상태를 구한다.

2. 각 섬에 대해서 BFS를 하며, 영역을 확장시키며 다른 섬과 만날 때까지의 거리를 구한다.

 

from collections import defaultdict,deque
def land(cur,island,count,N,total_land,gmap):#land의 상태를 구함
    q=deque([])
    q.append(cur)
    visit=[cur]
    X=[0,0,-1,1]
    Y=[-1,1,0,0]
    while q:
        c_x,c_y=q.popleft()
        for i in range(4):
            n_x=c_x+X[i]
            n_y=c_y+Y[i]
            if n_x>=0 and n_x<N and n_y>=0 and n_y<N:
                if gmap[n_x][n_y]==1:
                    if (n_x,n_y) not in visit:
                        visit.append((n_x,n_y))
                        island.remove((n_x,n_y))
                        q.append((n_x,n_y))
    total_land[count]=visit
    return island
def distance(N,gmap,cur,key,total_land):#각 섬에서 영역을 넓히며 다른 섬까지의 count (w값으로 카운트)
    q=deque([])
    q.append((cur[0],cur[1],0))
    visit=[[10000000]*N for i in range(N)]
    visit[cur[0]][cur[1]]=1
    cur_li=total_land[key]
    count=[]

    X=[0,0,-1,1]
    Y=[-1,1,0,0]
    while q:
        c_x,c_y,w=q.popleft()#w=-1 현재 1
        for i in range(4):
            n_x=c_x+X[i]
            n_y=c_y+Y[i]
            if n_x>=0 and n_x<N and n_y>=0 and n_y<N:
                if gmap[n_x][n_y]==1:
                    if visit[n_x][n_y]==10000000:
                        if w==0:#현재 같은섬에서 있음
                            visit[n_x][n_y]=0
                            q.append((n_x,n_y,0))
                        else:#다른섬일때
                            if (n_x,n_y) not in cur_li:
                                count.append(w)
                else:#0일때 계속 카운트
                    if w+1<visit[n_x][n_y]:
                        q.append((n_x,n_y,w+1))
                        visit[n_x][n_y]=w+1
    return min(count)

def solution(gmap,island):
    total_land=defaultdict(list)
    count=0
    while island:
        cur=island.pop(0)
        island=land(cur,island,count,N,total_land,gmap)
        count+=1
    min_val=100000
    for i in total_land.keys():
        min_val=min(min_val,distance(N,gmap,total_land[i][0],i,total_land))


    return min_val

f=open('./input.txt','r')
N=int(f.readline().strip())
gmap=[]#map
island=[]#값 1인 좌표

for i in range(N):
    temp=list(map(int,list(f.readline().strip().split(' '))))
    gmap.append(temp)
    for idx,j in enumerate(temp):
        if j==1:
            island.append((i,idx))
print(solution(gmap,island))

Pypy3로 했을때는 맞았으나,

python으로 했을 때는 시간초과가 뜬다.

 

몇가지 생각나는 게 있는데,

1. BFS를 2번 돌려야하는가? (처음에 섬을 결정하면서 동시에 영역을 확장시키면..?)

2. 섬간 거리 비교를할때 중복해서 계속 카운트가 된다. (n^2과 1/2*n^2 의 복잡도 차이긴 하겠으나..) 

 

뭘까..

곧 더 업데이트하기로!