[BOJ/백준] 2233 사과 나무

import sys
sys.setrecursionlimit(10000)
def input():
    return sys.stdin.readline().rstrip()


def LCS(X,Y):
    if depth[X] != depth[Y]:
        if depth[X]>depth[Y]:
            X,Y = Y,X
        for i in range(MAX_NODE-1,-1,-1):
            if (depth[Y]-depth[X] >= (1<<i)):
                Y = parents[Y][i]
    if X == Y:
        return X
    if (Y != X):
        for i in range(MAX_NODE-1,-1,-1):
            if parents[X][i] != parents[Y][i]:
                X = parents[X][i]
                Y = parents[Y][i]
    return parents[X][0]
def tree_make(idx,cur_node,node_cnt,parent_idx):
    if idx == len(binary_list):
        return
    if binary_list[idx] == 0:
        node_cnt += 1
        cur_node = node_cnt
        binary_search[idx+1] = cur_node
        tree[cur_node].visited.append(idx+1)
        tree[cur_node].parent = parent_idx
        depth[cur_node] = depth[parent_idx] + 1
        parents[cur_node][0] = parent_idx
        if cur_node != 1:
            parent_node = tree[cur_node].parent
            if tree[parent_node].left == None:
                tree[parent_node].left = cur_node
            else:
                tree[parent_node].right = cur_node
        tree_make(idx+1,cur_node,node_cnt,cur_node)
    else:
        binary_search[idx+1] = cur_node
        tree[cur_node].visited.append(idx+1)
        cur_node = tree[cur_node].parent
        tree_make(idx+1,cur_node,node_cnt,cur_node)



class Node():
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None
        self.parent = None
        self.visited = []

N = int(input())
binary_list = list(map(int,list(input())))
i,j = map(int,input().split())
tree = [Node(i) for i in range(N+1)]
MAX_NODE = 15
binary_search = [0 for _ in range(len(binary_list)+1)]
depth = [0 for _ in range(N+1)]
parents = [[0 for _ in range(MAX_NODE)] for _ in range(N+1)]

tree_make(0,0,0,0)
for par_idx in range(1,MAX_NODE):
    for k in range(1,N+1):
        parents[k][par_idx] = parents[parents[k][par_idx-1]][par_idx-1]

X,Y = binary_search[i],binary_search[j]

result_node = LCS(X,Y)
print(*tree[result_node].visited)

 

 

LCA를 이용해서 풀어본 처음 문제였다.

 

LCA를 공부하면서 푼 풀이이다. 

 

LCA에 대한 자세한 설명은

 

https://jason9319.tistory.com/90    https://www.crocus.co.kr/660    https://m.blog.naver.com/kks227/220820773477  https://velog.io/@lre12/LCA-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Lowest-Common-Ancestor

LCA(Lowest Common Ancestor)

위의 사이트들을 참조하길 바란다.

 

 

LCA를 공부하면서, 이해하다가 막혔다가 푼 부분을 적으면 다음과 같다.

 

 

1. 부모를 저장하는 dp 테이블에는 해당 노드의 모든 부모를 저장하는 것이 아닌 2^k번째 부모들만 압축해서 저장해놓는것이다.

 

2. 위의 파생이지만, 그렇기 때문에, 두 높이의 차이가 1<<i 즉 2^i 차이가 나면, i만큼 올려주면 되는것이다.

 

3. 그리고 두 높이가 같고, 서로 다르다면, k번째 위치부터 다른 값까지 한꺼번에 올려버린다.

  즉, dp[node1][k] , dp[node2][k] 는 다르지만, dp[node1][k+1], dp[node][k+1]이 같으면

   각 노드들의 2^k + 1 ~ 2^(k+1) 사이에 최소 공통 조상이 있을 것이다. 이 부분을 주의하면 된다.

 

4. 또한, 첫번째에서 말한것처럼 2^k번째 만 저장을 시켜놓은것이기때문에

 

    2^(k+1) = 2^k + 2^k 이다.

    2^k = 2^(k-1) + 2^(k-1) 이므로,

dp[node][k] = dp[ dp[node][k-1] ] [k-1] 으로 하면 LCA의 해당 노드들의 모든 공통조상부모에 대해서 저장시킬수 있다.

 

위의 것들이 윗 링크들을 공부하면서 제가 깨달은 부분이다.

 

인제는 문제로 돌아가서 

 

여기서 문제에 주어진 비트를 트리구조로만 바꾸면 우리는 위에서 배운 LCA를 적용시키면 된다.

 

저는 여기서 이 문제를 해결하기 위해 Node라는 클래스를 만들어놨습니다.

 

해당 Node에는 총 5가지의 파라미터가 있습니다.

 

data는 이 노드의 번호를 나타내고,

left는 왼쪽 자식번호

right는 오른쪽 자식번호

parent는 부모 번호

visited는 우리가 주어진 비트에서 몇번재 비트에서 이 노드를 방문했는지 표시르 위한 것입니다.

 

저는 tree_make라는 재귀함수를 만들어 이 문제를 해결했습니다.

 

입력 parameter는 4가지가 있고, idx는 현재 입력으로 주어진 비트의 몇번째 idx인지를 나타냅니다.

 

cur_node는 현재 노드의 번호입니다.

 

node_cnt는 지금까지 생성된 노드의 개수입니다.

 

parent_idx는 부모 노드의 번호입니다.

 

비트에서 우리가 0을 만나면 최초로 생성되는 노드로 진입하게 되는겁니다.

 

그래서 node_cnt를 1을 늘려주고, cur_node를 node_cnt로 바꿔줍니다.

 

그러면 우리는 현재 부모노드의 정보를 알고 있으므로,

 

부모노드의 left와 right 중 빈 순서대로 넣어주면 됩니다.

 

그리고 1을 만나게 되면 우리는 현재 방문하고 있던 노드에서 다시 되돌아가서 부모노드로 가야합니다.

 

그렇기 때문에 cur_node를 부모노드로 치환시키고, 재귀를 반복하면 됩니다.

 

즉 0을 만나면 새로운 노드가 생성이되고,

 

1을 만나면 부모노드로 되돌아간다는 점만 기억을 하면, 문제에서 주어진 비트를 트리로 만들 수 있습니다.

 

코드가 깔끔하지 못해, 다른 분들의 코드를 보는 것을 더 추천합니다.

 

위와 같은 작업을 해서 비트를 트리구조로 바꾼뒤에 LCA을 적용시키면 이 문제를 해결 할 수 있습니다.

 

LCA와 관련된 문제를 처음 풀어보았기에, 헷갈리던 점도 많았고, 트리에 대해 숙달되지 못했기에,

 

비트를 트리로 구현하는데에 오래 걸린 문제였습니다.

 

매번 트리와 관련된 문제가 나오면 문제를 해결하는데 시간이 오래걸리는 것 같은데,

 

이 부분을 숙달하는데 더 노력을 해야할 것 같습니다.