글 읽기 - 파이썬 틀렸습니다 질문드립니다.

pepper_mis 3년 전 0

BFS로 섬을 찾고,

오른쪽방향, 아래방향으로 for문을 돌면서 섬 사이 거리를 찾았습니다.

(1이 입력할때 받은 값이라서 2, 3, 4.. 로 바꿔주면서 찾았습니다. 그래서 첫번째 섬번호가 2에요!)

찾은섬에서 시작해서 다음 섬까지 바다칸을 세서 거리를 쟀어요.

그리고 거리를 edge에 저장해서 크루스칼로 모든섬을 연결하는 최소거리를 찾았습니다.

마지막에 크루스칼에 사용했던 유니온 파인드 돌면서 연결되지 않은 섬이 있는지 확인했고요.

15%부근에서 틀렸습니다가 나옵니다.

예제랑 게시판 반례들 다 잘 돌아갔는데 계속 틀렸습니다가 나오네요..

혹시 잘못된 부분이나 반례가 있을까요?

import sys
#input = sys.stdin.readline
#sys.setrecursionlimit(100000)

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

#정점 찾기
from collections import deque
number = 2
def BFS(i, j):
    global number
    queue = deque()
    queue.append([i, j])
    while queue:
        i, j = queue.popleft()
        maps[i][j] = number
        if i > 0 and maps[i-1][j] == 1:#위
            queue.append([i-1, j])
        if i+1 < N and maps[i+1][j] == 1:#아래
            queue.append([i+1, j])
        if j > 0 and maps[i][j-1] == 1:#왼쪽
            queue.append([i, j-1])
        if j+1 < M and maps[i][j+1] == 1:#오른쪽
            queue.append([i, j+1])
    number += 1
    
for i in range(N):
    for j in range(M):
        if maps[i][j] == 1:
            BFS(i, j)
number -= 1
            
#간선 찾기
edge = [[100]*(number+1) for i in range(number+1)]
start = 0
count = 0
for i in range(N):
    for j in range(M):
        if maps[i][j] != 0 and (start == 0 or start == maps[i][j]): #출발지점
            start = maps[i][j]
            count = 0
        elif maps[i][j] == 0 and start != 0:
            count += 1
        elif maps[i][j] != 0 and maps[i][j] != start and start != 0: #도착지점
            if count != 1:
                if start < maps[i][j]:
                    edge[start][maps[i][j]] = min(edge[start][maps[i][j]], count)
                else:
                    edge[maps[i][j]][start] = min(edge[start][maps[i][j]], count)
            start = maps[i][j]
            count = 0
    start = 0
    count = 0
    
for i in range(M):
    for j in range(N):
        if maps[j][i] != 0 and (start == 0 or start == maps[j][i]): #출발지점
            start = maps[j][i]
            count = 0
        elif maps[j][i] == 0 and start != 0:
            count += 1
        elif maps[j][i] != 0 and maps[j][i] != start and start != 0: #도착지점
            if count != 1:
                if start < maps[j][i]:
                    edge[start][maps[j][i]] = min(edge[start][maps[j][i]], count)
                else:
                    edge[maps[j][i]][start] = min(edge[start][maps[j][i]], count)
            start = maps[j][i]
            count = 0
    start = 0
    count = 0

#다리 연결하기
import heapq
heap = []
for i in range(number+1):
    for j in range(number+1):
        if 100 > edge[i][j]:
            heapq.heappush(heap, [edge[i][j], i, j])
            
#유니온 파인드
root = [i for i in range(number+1)] 
def find_root(target):
    if root[target] == target:
        return target
    root[target] = find_root(root[target])
    return root[target]
def union(i, j):
    i = find_root(i)
    j = find_root(j)
    if i == j:
        return False
    if i < j:
        root[j] = i
    else:
        root[i] = j
    return True

count = 0
distance = 0
while heap and count != number-2 :
    d, i, j = heapq.heappop(heap)
    if union(i, j):
        distance += d
        count += 1
        
check = 0
for i in range(2, number-1):
    if find_root(i) != find_root(i+1):
        check = 1

if not heap and check == 1:
    print(-1)
else:
    print(distance)

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

문제

문제

출처

ICPC

파이썬 틀렸습니다 질문드립니다.

pepper_mis 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말