[Python] 20364번: 부동산 다툼

 

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

20364번: 부동산 다툼

시간 제한: 2초

메모리 제한:  1024mb

<문제 풀이전 나의 생각>**************************************************

메모리 제한이 널널하다 1024mb로

그래프 탐색을 진행하면서 플래그 신호 처럼 이미 왔던곳이면 check 해 두면서 탐색을 진행하면 될것같다

 

그래프 저장하는 형태만 잘 구상한다면 

생각보다 쉬워 보이는걸

이진트리의 2k, 2k+1의 자식 땅 매핑 정보를 잘 활용하여 저장 정보를 만들어 보자

 

노드가 가져야 할것: 자식노드 정보, 해당 노드 값

 

 

<문제 푸는중 고민>**********************************************************

2k, 2k+1로 왼쪽자식, 오른쪽 자식을 의미한다.

노드의 층수를 구해야 하나 일단 math.log(x,2)를 활용해서 2의로그를 구한다?

 

정정 층수를 구하는 필요가 없음

그냥 바텀업 방식으로 타겟 층수를 파악후에 1까지 거슬러 올라가면서 체크 한다.

 

<바텀업 방식>

전부 방문한적이 없는 노드이다 --> Target 노드를 True로 바꿔주고 0 출력

거슬러 올라가면서 방문한적이 있는 노드를 발견했다면 --> 1까지 올라가되, 가장 1에서 가까운 True 를 index 찾아서 출력

최신화 하는 방식을 사용하면 될듯 하듯

 

제출했는데 틀렸음, 1을 입력 받았을때 멈춰 버림 ㅎㅎ

예외 처리를 해주자

 

음 근데 문제를 다시 보니깐 땅번호 1은 들어올수가 없다.

그렇다면 다른 곳에서 문제가 발생했다는 뜻 인데... 못 찾을듯 ㅎㅎ

 

# 그래프 탐색 문제이다.
# 이번 기회에 그래프 탐색을 박살내겠다
'''
test 케이스1
<입력>
11 5
9
2
4
5
11

<출력>
0
0
2
2
2


test case 2
<입력>
11 5
1
2
3
4
5

<출력>
0
1
1
1
1
1
'''
import sys
import math
# x = 8
# result = math.log(x, 2)  #log2에x승을 의미한다.
# print(result)

# 땅 개수, 오리 개수
Ground, duck = map(int, sys.stdin.readline().split())

# 인덱스 1번부터 사용할 예정임
graph = [False]*(Ground+1)

for i in range(duck):
    Want=int(sys.stdin.readline())
    b = Want
    
    # 뭔가 이거 바텀업 방식으로 하는게 맞는것 같다
    조상님과가장가까운True노드번호=-1
    while(Want!=1):
        # 1회 조상님 방문 거슬러 올라가기
        if graph[Want]:    #True면 누가 땅 먹은곳에서 만나게 됨
            조상님과가장가까운True노드번호=Want
        Want//=2    # 이것 때문에 틀림 57행에 넣어서

    # 올라가면서 단 한번도 주인있는 땅을 만나지 않음
    if 조상님과가장가까운True노드번호 == -1:
        print(0)    #, "막히지 않음"
        graph[b] = True
    else:
        print(조상님과가장가까운True노드번호)    #, "이 노드에서 막혔음"

 

<문제를 풀고난뒤 후기>*********************************************************

진짜 거의 다풀었는데 너무 허무하게 한곳에서 막혀서 속상하다

while문에서 Want//2를 나누고 시작해 버렸다.

문제에서 "오리가 원하는 땅까지 가는 길에는 오리가 원하는 땅도 포함된다" 라는걸 읽지 못하고 원하는 땅을 당연히 누가 안먹었겠지 한것과 같은 원리로 취급했기 때문이다.

원하는 땅 노드를 검사한 후에 Want//2를 해야 한다.

 

항상 조건문을 쓸때는 조심하자

그래도 좋은 시도 였다.

 

알게된점: 해당 노드까지 포함되는지 조건문 설정을 잘 하고, 코너케이스에 만족을 하는지 잘 생각 해보자,

result = math.log(x, 2)

import math 후 로그 사용법이다.