(Python) [BOJ 20364] 부동산 다툼

(Python) [BOJ 20364] 부동산 다툼

문제: https://www.acmicpc.net/problem/20364

간단하게 정리하자면, 이진 트리의 노드들을 문제의 요구 사항에 맞게 탐색하는 문제입니다.

이미 점유된 땅은 지나갈 수 없으므로 해당 땅(노드)과 자식 땅들에 대해 더이상 갈 수 없음을 표시하였고, 이때 누구에 의해 점유된 것인지를 기록하여 최대한 불필요한 탐색을 배제하고자 했습니다.

import sys def occupy_area(area, idx): occupied[idx] = area # 어느 지역에 의해 자식들이 점령되었는지 기록 for nex in [idx*2, idx*2+1]: if nex <= N: occupy_area(area, nex) # 1. INPUT & SETTING N, Q = map(int, sys.stdin.readline().split()) occupied = [0] * (N + 1) # 점령 여부를 기록할 리스트 # 2. BODY for area in [int(sys.stdin.readline()) for _ in range(Q)]: # 오리들이 가고자 하는 지역 if not occupied[area]: # 아직 점령되지 않은 곳 print(0) # 3. OUTPUT occupy_area(area, area) # 점령 처리 else: # 점령된 곳 print(occupied[area]) # 3. OUTPUT: 누가 점령했는지 출력

from http://sangdanghyunjeo.tistory.com/5 by ccl(A) rewrite - 2021-12-14 14:26:26