[BOJ|PYTHON]백준 17501 - 그래프 표현하는 독특한 방법 +D/BFS

일단 이 문제는 구현이 되게 생소하고 어렵다. 그래프를 표현하는 방법에 대해 생각을 많이 해볼 수 있는 문제라 좋다.

그래프를 배울 때 가장 먼저 배우는 것이자 많이 사용하는 것이 바로 계산하는 순서인 전위/중위/후위 표기식이다. 이런 표기식을 잘 생각해 보면서 문제를 풀어야 한다.

잘 나타내 보면, 규칙은 다음과 같다.

1. ‘+’일 때는 그냥 내려간다.
2. ‘-’일 때는 -오른쪽 자식의 상태를 switch 시킨다.
3. -왼쪽은 그냥 내려간다.

이런 식으로 계속 상태를 바꾸어 주다가 마지막 노드인 1~N까지의 수에 도달하였을 때 연산자가 -라면 -가 몇 개 나오는지 모두 더해준다.

마지막으로 -의 개수(만약 3개라면) 에 따라서 가장 작은 수(3개)의 개수만큼을 최소 heapq에서 뽑아 SUM 값에서 빼준다.

SUM-2*(가장 작은 수 3개의 합) —> 이런 느낌

사용한 툴

1. ^ : 0은 1로 1은 0으로 뒤집어주는 역할
2. Operator=[{'parent':0,'lchild':0,'rchild':0,'val':0} for _ in range(2*N)]
3. 리스트 안에 dictionary를 넣어 트리를 가시화할 수 있고, child나 parent를 따라갈 수 있다.
4. while 문을 사용해 최상위 parent로 접근하는 방법( union find에서의 find와 비슷하다)
5. heapq 사용 → 가장 작은 수부터 하나씩 뽑는다는 것에서 sort보다는 heapq를 사용하면 시간복잡도 측면에서 매우 유리하다.

'''
문제에서 요구하는 형식에 맞게 짜보자
'''
import sys
input=sys.stdin.readline

import heapq
from collections import deque
N=int(input())
List=[]
heapq.heapify(List)
Graph=['' for _ in range(N+1)]
Operator=[{'parent':0,'lchild':0,'rchild':0,'val':0} for _ in range(2*N)]
SUM=0
#일단 트리를 만든다.
for j in range(1,2*N):
    temp=list(input().split())
    if len(temp)==1: 
        x=int(temp[0])
        Operator[j]['val']=x
        heapq.heappush(List,x)
        SUM+=x
    else: 
        x,y,z=temp[0], int(temp[1]),int(temp[2])
        Operator[j]['lchild']=y; Operator[y]['parent']=j
        Operator[j]['rchild']=z; Operator[z]['parent']=j
        Operator[j]['val']=x
    if j==2*N-1: Operator[j]['parent']=j
root=Operator[2*N-1]['parent']

while root!=Operator[root]['parent']:
    root=Operator[root]['parent']

q=deque([])
q.append([root,0]) #처음 root는 +로 초기화
minus=0
while q:
    node,operator=q.popleft()
    if 0< node and node<=N: #숫자라면
        if operator: 
            minus+=1
            #print('해당노드',node)
        continue
    q.append([Operator[node]['lchild'], operator])
    if Operator[node]['val']=='+':
        q.append([Operator[node]['rchild'],operator])
    if Operator[node]['val']=='-': #뒤집어요
        q.append([Operator[node]['rchild'],operator^1])

# print(minus)

for i in range(minus):
    x=heapq.heappop(List)
    SUM-=2*x

print(SUM)

 

복잡하긴 한데, 뭔가 복잡해서 구현할 때 오오오 하면서 재밌는 그런 느낌이 있었다.(???)