백준 2146 [다리 만들기] 파이썬

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

 

생각보다 할만했다. 근데 시간관리가 어려웠다.

#백준 2146 다리 만들기
import sys
from collections import deque
import copy
dr=[1,-1,0,0]
dc=[0,0,1,-1]
ans=[]
land_cnt=-1 # 섬을 구분할 숫자
N=int(sys.stdin.readline()) # 맵의길이
field=[]# 맵
visited=[[0 for _ in range(N)] for _ in range(N)] # 방문여부확인 리스트
lands=[] # 각 섬의 좌표를 저장할 리스트

for _ in range(N):
    field.append(list(map(int,sys.stdin.readline().split()))) # 맵 정보 받음

for i in range(N):
    for j in range(N):
        if field[i][j]==1 and visited[i][j]==0: # 방문하지 않은 섬이라면 (BFS 시작)
            temp_land=deque() # N번째 섬의 좌표를 저장할 리스트
            q=deque()
            q.append((i,j))
            temp_land.append((i,j)) # N번째 섬의 좌표 저장
            visited[i][j]=1 # 방문여부 갱신
            field[i][j]=land_cnt # 섬 구분자로 값 갱신 ( 각 섬마다 --> -1,-2,-3...)
            while q:
                r,c=q.popleft()
                is_near_sea=False
                for k in range(4):
                    R=r+dr[k]
                    C=c+dc[k]
                    if 0<=R<N and 0<=C<N:
                        if visited[R][C]==0 and field[R][C]!=0: #방문하지 않았고, 연결되있는부분(R,C)가 육지라면
                            q.append((R,C))
                            visited[R][C]=1
                            field[R][C]=land_cnt
                        elif field[R][C]==0: # 현재(r,c)가 바다에 접해있다면
                            is_near_sea=True
                if is_near_sea: # 현재(r,c)가 바다에 접해있다면
                    temp_land.append((r,c))
            lands.append(temp_land)
            land_cnt-=1


for i in range(len(lands)): # 각 섬에 대하여
    temp_field=copy.deepcopy(field) # 맵을 갱신하기 위해 복사
    criteria=(i*-1)-1 # 각 섬의 구분자
    find_flg=False # 최단거리를 찾았는지 확인 하는 FLAG
    while lands[i]: #이을 수 있는 다리의 좌표가 있다면
        if find_flg==True: # 최단거리 찾은경우 탈출
            break
        r,c=lands[i].popleft()
        for k in range(4):
            R=r+dr[k]
            C=c+dc[k]
            if 0<=R<N and 0<=C<N:
                if temp_field[R][C]==0: 
                    if temp_field[r][c]==criteria: # 섬에서 방금 막 시작한 경우
                        temp_field[R][C]=1
                        lands[i].append((R,C))
                    else:
                        temp_field[R][C]=temp_field[r][c]+1 # 다리를 계속 잇고 있는 경우
                        lands[i].append((R,C))
                elif temp_field[R][C]!=criteria and temp_field[R][C]<0: # 다른 섬과 만난 경우우
                    ans.append(temp_field[r][c])
                    find_flg=True
                    break
print(min(ans))

위 코드는 python3로 풀면 시간초과가 발생하고, pypy3로 풀면 정답으로 처리가된다.

흐음...

 

시간초과가 발생하지 않은 다른분의 풀이를 첨부한다.

https://hstory0208.tistory.com/entry/Python%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%B0%B1%EC%A4%80-2146-%EB%8B%A4%EB%A6%AC-%EB%A7%8C%EB%93%A4%EA%B8%B0

[Python/파이썬] 백준 2146 - 다리 만들기

 

from collections import deque
import sys
input = sys.stdin.readline
 
n = int(input())
maps = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
 
# 섬의 개수를 구하고 섬마다 번호를 표시하는 bfs
def bfs(x, y):
    q = deque()
    q.append((x, y))
    visited[x][y] = True
    maps[x][y] = mark
 
    while q:
        x, y = q.popleft()
 
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
 
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                if maps[nx][ny] == 1:
                    q.append((nx, ny))
                    maps[nx][ny] = mark
                    visited[nx][ny] = True
 
# 섬 사이 최단거리를 구하는 bfs
def bfs2(island):
    q = deque()
    dist = [[-1] * n for _ in range(n)]
 
    for i in range(n):
        for j in range(n):
            if maps[i][j] == island:
                q.append((i, j))
                dist[i][j] = 0
    
    while q:
        x, y = q.popleft()
 
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0 <= nx < n and 0 <= ny < n:
                if maps[nx][ny] != island and maps[nx][ny] != 0: # 다른 섬과 만났을 경우
                    return dist[x][y]
                if maps[nx][ny] == 0 and dist[nx][ny] == -1: # 물이고 아직 건너지 않은 곳일 경우
                    dist[nx][ny] = dist[x][y] + 1
                    q.append((nx, ny))
 
mark = 1 # 섬마다 번호를 체크하기 위한 값
for x in range(n):
    for y in range(n):
        if maps[x][y] == 1 and not visited[x][y]:
            island_cnt = bfs(x, y)
            mark += 1
 
result = sys.maxsize # 최솟값을 구하기 위해 가장 큰 값으로 세팅
for island in range(1, mark):
    result = min(result, bfs2(island))
 
print(result)

나의 시간초과 추정원인은 deepcopy 때문인거같다.