백준20364 - 부동산 다툼 (트리) Python

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

문제 해결 방식

각 정점의 부모는 정점 번호 // 2 (2로 나눈 뒤 소숫점 버림)이라는 규칙을 가지고 있기 때문에, 해당 정점에서 위로 올라가는 식으로 로직을 구현했다. 이때, 만약 방문하는 정점이 누군가가 이미 위치한 땅이라면 해당 땅 번호를 리턴하고, 최정점 루트인 1에 도달할 때까지 누군가 선점한 땅을 마주치지 않는다면, 해당 정점을 기록하고 0을 리턴하도록 했다.

전체 소스 코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()

def solution (data) :
  data.pop(0)
  arr = list(map(int, data))
  visited = {}
  
  def DFS (n) :
    node = n
    answer = 0
    while node > 0 :
      if visited.get(node, None) :
        answer = node
      node //= 2

    if answer == 0 :
      visited[n] = True
    return answer
    
  result = []
  for duck in arr :
    result.append(DFS(duck))
    
  print('\n'.join(map(str,result)))
     
solution(input_data)