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





요 문제인데요. 어떻게 푸는지 고민하다가 스마트한 방법은 영 안 떠올라서 좀 무식하게 풀기로 했습니다.

주어진 관계 안에서 친한친구 쌍을 안 겹치는 한도 내에서 최대한 많이 뽑아내고 답을 친구쌍수*2에 경우에 따라서

1을 더해주거나 안 더해주거나 해서 출력하는 걸로 전략을 잡았고요


친구쌍을 뽑아내는 전략으로...아직 쌍으로 빠지지 않은 친구의 수가 최대한 적은 애와 그 애의 친구를 뽑아내고

그 둘을 전체 rel을 돌면서 삭제해주고...반복 뭐 이런 식으로 짰거든요. 이게 말로 설명하자니 이해하시기 좀 어려울 거 같은데


http://boj.kr/d8368276c3464393826ad781e4318bcf


import sys
sys.setrecursionlimit(10**5)
from collections import defaultdict, deque
read = sys.stdin.readline
write = sys.stdout.write
from heapq import *
from pprint import pprint
from math import *
n, m = map(int,read().split())
rel = defaultdict(list)
for _ in range(m):
u, v = map(int,read().split())
rel[u].append(v)
rel[v].append(u)
pprint(rel)
min_rel = inf
for num in rel.values():
if len(num) < min_rel:
min_rel = len(num)
complete = set()
dap = 0
while rel:
for stu,fri in rel.items():
if len(fri) == min_rel:
u = stu
v = fri[0]
break
# if u != None:
rel.pop(u)
# if v != None:
rel.pop(v)
dap += 1
q = None
for stu2,fri2 in rel.items():
if u in fri2:
fri2.remove(u)
if len(fri2) == 0:
q = stu2
if v in fri2:
fri2.remove(v)
if len(fri2) == 0:
q = stu2
if len(fri2) != 0:
min_rel = min(min_rel,len(fri2))
if q != None:
rel.pop(q)
u = None
v = None
print(rel)
if dap*2 == n:
print(dap*2)
else:
print(dap*2+1)



이렇게 구현했습니다.


문제는...이렇게 해서 제출을 하면 keyerror가 뜬다는 점인데요. 이해하기가 어렵습니다.

처음에 rel 생성할 때 부터 u,v 대칭적으로 만들어줬고

한번 친구쌍을 찾을 때 마다 rel에서 u와 v를 같이 삭제해줬고 루프문은 rel이 있을 때만 돌기 때문에...


u와 v가 None이 될리가 없이 딱 rel에 있는 것만 뽑아올텐데 왜 key 에러가 뜰까요?


혹시나 싶어서 rel.pop(u), rel.pop(v)에 if u!=None 일 때만 삭제하라고 했을 때는 키에러 안 뜨는 걸로 봐서 저 부분이 문제인 건 맞는 거 같지만


어떠한 경우에도 rel에 없는 키가 나올 수는 없는 구조인 거 같아서요. 물론 그렇게 해도 키에러는 안 떠도 시간초과가 뜨지만...


답답하네요ㅠㅠ