글 읽기 - 크루스칼 부분

kkk950928 1년 전 0

find union 형식으로 크루스칼 만들면 맞았다고 뜹니다.

그러나 지금과 같은 방식으로 하면 4%정도에서 시간초과가 뜨네요.

지금과 같은 방식은 효율성이 매우 안좋은 것일까요?

import collections
import sys

dx=[0,0,1,-1]
dy=[1,-1,0,0]
def island(x,y):
    queue=collections.deque()
    queue.append((x,y))
    visit[x][y]=1
    board[x][y]=island_num+1
    while queue:
        x,y=queue.popleft()
        for dir in range(4):
            nx=x+dx[dir]
            ny=y+dy[dir]
            if 0<=nx<N and 0<=ny<M and board[nx][ny] and not visit[nx][ny]:
                visit[nx][ny]=1
                board[nx][ny]=island_num+1
                queue.append((nx,ny))

def edge_func(x,y):
    for dir in range(4):
        nx=x;ny=y;
        dist=0
        while 1:
            nx+=dx[dir]
            ny+=dy[dir]
            if 0<=nx<N and 0<=ny<M:
                if not board[nx][ny]:
                    dist+=1
                elif board[x][y]!=board[nx][ny]:#다른섬 만난 경우
                    if dist>=2:
                        e=[board[x][y],board[nx][ny]]
                        e.sort()
                        edges.add((e[0],e[1],dist))
                    break
                else:
                    break
            else:#섬을 못만나고 범위 초과한 경우
                break



N,M=map(int,input().split())
board=[list(map(int,input().split())) for i in range(N)]

#섬 구분하기
island_num=0
visit=[[0]*M for i in range(N)]
for x in range(N):
    for y in range(M):
        if board[x][y] and not visit[x][y]:
            visit[x][y]=1
            island(x,y)
            island_num+=1

#가능한 edge구하기
edges=set()
visit=[[0]*M for i in range(N)]
for x in range(N):
    for y in range(M):
        if board[x][y] and not visit[x][y]:
            visit[x][y]=1
            edge_func(x,y)

# #크루스칼
edges=list(edges)
edges.sort(key=lambda x:(x[2]))
il_visit=[0]*(island_num+1)
answer=0
if not edges:
    print(-1)
    sys.exit()

il_visit=set([edges[0][0]])
while len(il_visit)!=island_num:
    if not edges:
        answer=-1
        break
    for edge in edges[:]:
        x,y,d=edge
        if x in il_visit and y in il_visit:
            continue
        if x in il_visit or y in il_visit:
            il_visit.update([x,y])
            answer+=d
            edges.remove(edge)
            break


print(answer)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

크루스칼 부분

kkk950928 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말