2146번 다리 만들기 백준 파이썬

문제:www.acmicpc.net/problem/2146

2146번: 다리 만들기

이 문제를 접근했을 때 단지 번호 붙이기가 생각이 났다. 그래서 각 섬 별로 단지를 붙혀서 -1,-2,-3 이런식으로 붙힌 다음 각 바다점마다의 거리를 계산하여 최소 거리를 계산 했다. 하지만 아니나 다를 까 시간초과가 났다.

 

 

import sys
from collections import deque
# sys.setrecursionlimit(int(10e5))
def func(y,x):
    if x>=0 and x<N and y>=0 and y<N:
        return True
    else:
        return False

def bfs(y,x,form):
    q = deque()
    q.append([y,x])
    graph[y][x]=form
    visited[y][x]=True
    while q:
        dot=q.popleft()
        for i in range(4):
            gy=dot[0]+dy[i]
            gx=dot[1]+dx[i]
            if func(gy,gx) and not visited[gy][gx] and graph[gy][gx]:
                q.append([gy,gx])
                visited[gy][gx]=True
                graph[gy][gx]=form

def bfs2(y,x):
    q = deque()
    q.append([y,x])
    travel[y][x]=True
    total=0
    val=0
    while q:
        dot=q.popleft()
        for i in range(4):
            gy=dot[0]+dy[i]
            gx=dot[1]+dx[i]
            if total==2:
                return val-1
            if func(gy,gx) and graph[gy][gx]<0 and not tileChart[abs(graph[gy][gx])]:
                tileChart[abs(graph[gy][gx])]=True
                total+=1
                val+=abs(gy-y)+abs(gx-x)
            elif func(gy,gx) and not travel[gy][gx] and graph[gy][gx]==0 and not tileChart[abs(graph[gy][gx])]:
                q.append([gy,gx])
                travel[gy][gx]=True
    return 10e9

N = int(sys.stdin.readline().rstrip())
graph=[]
for i in range(N):
    graph.append(list(map(int,sys.stdin.readline().split())))
tile=-1
tileChart=[False]*10000
visited=[[False]*N for _ in range(N)]
dy=[1,0,-1,0]
dx=[0,1,0,-1]

for i in range(N):
    for j in range(N):
        if not visited[i][j] and graph[i][j]:
            bfs(i,j,tile)
            tile-=1
travel=[[False]*N for _ in range(N)]
ans=10e9

for i in range(N):
    for j in range(N):
        if travel!=visited:
            travel=[[False]*N for _ in range(N)]
        if graph[i][j]==0 and not travel[i][j]:
            ans=min(ans,bfs2(i,j))
            tileChart=[False]*10000
        
print(ans)

방문 기록을 바다점을 바꿀때마다 갱신하는 것에서 아무래도 시간초과의 큰 원인이 아니였을까 싶다.

그래서 하는 수 없이 다른 분의 코드를 참고했다.

 

 

import sys 
from collections import deque 
def grouping(i, j): # 섬마다 번호 붙이기 
    q = deque([(i, j)]) 
    world[i][j] = gid 
    while q: 
        qi, qj = q.popleft() 
        for t in range(4): 
            x, y = qi + dx[t], qj + dy[t] 
            if 0 <= x < n and 0 <= y < n: 
                if world[x][y] == 1: 
                    world[x][y] = gid 
                    q.append((x, y)) 
                elif world[x][y] == 0 and not (qi, qj) in ocean: 
                    ocean.append((qi, qj))
            
def get_distance(): # 모든 섬에서 동시에 확장 
    loop = 0 
    ans = sys.maxsize 
    while ocean: 
        loop += 1 
        length = len(ocean) 
        for _ in range(length): 
            oi, oj = ocean.popleft() 
            for t in range(4): 
                x, y = oi + dx[t], oj + dy[t] 
                if 0 <= x < n and 0 <= y < n: 
                    if world[x][y] == 0: 
                        world[x][y] = world[oi][oj] 
                        ocean.append((x, y)) 
                    elif world[x][y] < world[oi][oj]: 
                        ans = min(ans, (loop - 1) * 2) 
                    elif world[x][y] > world[oi][oj]: 
                        ans = min(ans, loop * 2 - 1) 
    return ans 
dx, dy = (0, 0, 1, -1), (1, -1, 0, 0) 
n = int(sys.stdin.readline()) 
world = [list(map(int, sys.stdin.readline().split())) for _ in range(n)] 
ocean = deque() 
gid = -1 
for i in range(n): 
    for j in range(n): 
        if world[i][j] > 0: 
            grouping(i, j) 
            gid -= 1
    
sys.stdout.write(str(get_distance()))

참고:https://suri78.tistory.com/133

[백준알고리즘] 2146번: 다리 만들기 -Python

이 분과 나의 차이점은 섬을 기준으로 최소거리를 계산하느냐 각 바다의 점 기준으로 최소거리를 계산하느냐의 차이인 것 같다. 

 

위의 코드도 마찬가지로 각각의 섬에 번호를 부여한다. 그리고 바다와 맞닿는 섬의 좌표들을 ocean이라는 큐에 저장해놓는다. 그리고 다음 아래와 같이 풀면 된다.