글 읽기 - 백준17472 다리만들기 2 (파이썬) 질문있습니다!

djagmlrhks3 3년 전 0

문제가 쉽게 풀릴 줄 알았는데... 그루핑하는 부분에서 시간을 너무 오래잡아먹고 해결이 안됩니다 ㅠ

크루스칼 알고리즘을 그루핑하는 부분에 사용하니 바로 풀렸는데 이전에 작성했던 코드는 어떤 반례의 경우 통과되지 않은지 궁금합니다.

질문게시판 및 블로그에 올라와 있는 반례 모두 통과됩니다. 😥

import sys
from collections import deque

N, M = map(int, input().split())
country = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
answer = 0
cnt = 1
used = []
edge = []
queue = deque([])

direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# 섬을 번호로 매기는 부분(BFS)
for i in range(N):
    for j in range(M):
        if country[i][j] and (i, j) not in used:
            queue.append((i, j))
            used.append((i, j))
            while queue:
                r, c = queue.popleft()
                country[r][c] = cnt
                for idx in range(4):
                    nr = r + direction[idx][0]
                    nc = c + direction[idx][1]
                    if 0 <= nr < N and 0 <= nc < M:
                        if country[nr][nc] and (nr, nc) not in used:
                            queue.append((nr, nc))
                            used.append((nr, nc))
            cnt += 1

# 행 또는 열을 인자로 넣었을 때 생성할 수 있는 다리가 있는지 확인하는 함수
def check(li):
    start, cnt = 0, 0
    flag = False
    for idx in range(len(li)):
        if li[idx] and not flag:
            flag = True
            start = li[idx]
        elif not li[idx] and flag:
            cnt += 1
        elif li[idx] and flag and start != li[idx]:
            if start and cnt >= 2:
                if (start, li[idx], cnt) not in edge:
                    edge.append((start, li[idx], cnt))
            cnt = 0
            start = li[idx]
        elif start == li[idx]:
            cnt = 0

# 행 탐색
for row in country:
    if sum(row):
        check(row)

# 열 탐색
for col in list(zip(*country)):
    if sum(col):
        check(col)

# 아래코드 부터는 그루핑 시키는 부분입니다.(크루스칼 알고리즘 사용시 통과됩니다!)
def group(connected, yet):
    global answer
    for _ in range(len(yet)):
        test = yet.popleft()
        if test[0] in connected or test[1] in connected:
            if test[0] in connected and test[1] in connected:
                yet.append(test)
                continue
            if test[0] not in connected:
                connected.append(test[0])
            else:
                connected.append(test[1])
            answer += test[2]

edge = sorted(edge, key=lambda x:[x[2]])
yet = deque([])
if len(edge):
    connected = [edge[0][0], edge[0][1]]
    answer = edge[0][2]
    for idx in range(1, len(edge)):
        if edge[idx][0] in connected or edge[idx][1] in connected:
            if edge[idx][0] in connected and edge[idx][1] in connected:
                continue
            if edge[idx][0] not in connected:
                connected.append(edge[idx][0])
            else:
                connected.append(edge[idx][1])
            answer += edge[idx][2]
            if len(yet):
                group(connected, yet)
        else:
            yet.append(edge[idx])
    answer = answer if len(connected) == cnt-1 else -1
    print(answer)
else:
    print(-1)

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

문제

문제

출처

ICPC

백준17472 다리만들기 2 (파이썬) 질문있습니다!

djagmlrhks3 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말