글 읽기 - 파이썬 시작하자마자 틀림.[반례 모두 시도]

wndlswo12 3년 전 0

제출하자마자 바로 틀리네요. 질문에 있던 모든 반례 돌렸을 때 정상적으로 나옵니다.

제가 작성한 알고리즘의 핵심은 다음과 같습니다.

1. 지역 연결여부는 한 지점을 dfs로 방문하고 나서도 방문지점이 없을 때 연결되었다고 판단했습니다.

2. A선거구 기준으로 1번 지역,2번,..n번지역에 있을 때 A가 가지는 지역이 달라지므로 1~n번에서 스타트할 때 경우에 대해 BFS탐색을 실시하였습니다.

3.각 출발 지역에서 탐색했던 지점을 누적하여 기록하기 위한 visited, A선거구가 선택했던 그래프인지 확인하는 globalVisigted를 따로 두어 확인하였습니다.

무엇이 문제일까요?

from collections import deque

def isConnected(area):
    csdArea = area.copy()
    stack = [csdArea.pop()]

    while stack:
        u = stack.pop()
        for v in graph[u]:
            if v in csdArea:
                stack.append(v)
                csdArea.discard(v)

    if csdArea:
        return False
    else:
        return True

def getDifferencePopulation(aArea,bArea,population):
    aAreaNums = 0
    bAreaNums = 0
    for au in aArea:
        aAreaNums += population[au]

    for bu in bArea:
        bAreaNums += population[bu]

    return abs(aAreaNums-bAreaNums)

n = int(input())
population = [0]+list(map(int,input().split()))
graph = [[] for _ in range(n+1)]

for u in range(1,n+1):
    vInform = list(map(int,input().split()))
    for v in vInform[1:]:
        graph[u].append(v)

minValue = 1001

#aArea가지는 수가 방문했던 경우인지 기록.
globalVisited = set()

#A지역 선거구 기준으로 확인. 시작 지점에 값이 달라질 수 있으므로 1~n+1방문.
for u in range(1,n+1):
    queue = deque()
    #queue의 원소는 (aArea의 지역, u에서 시작했을 때 visited, 다음 방문위치)
    queue.append([{u},1<<u,u])
    globalVisited.add(1<<u)
    while queue:
        aArea,visited,curU = queue.popleft()
        bArea = set(range(1,n+1))-aArea
        
        #지역구 1개라도 가져야 한다는 조건에 위배되므로 다음 queue확인
        if not bArea:
            continue
        
        if isConnected(bArea):
            differencePopulation = getDifferencePopulation(aArea,bArea,population)
            minValue = min(minValue,differencePopulation)
        
        #다음 지정 방문.
        for nextV in graph[curU]:
            #이미 가졌던 aArea라면 다음으로.
            if visited|1<<nextV in globalVisited:
                continue
            globalVisited.add(visited|1<<nextV)
            queue.append((aArea|{nextV},visited|1<<nextV, nextV))

if minValue == 1001:
    minValue = -1

print(minValue)

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

문제

문제

출처

ICPC

파이썬 시작하자마자 틀림.[반례 모두 시도]

wndlswo12 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말