โ›น๏ธ ๋ผ์ดํ”„/2020 ๊ฒจ์šธ๋ฐฉํ•™ ๋ชจ๊ฐ์ฝ”(๊ฐœ์ธ)

[์ฝ”๋…ํ•˜๊ตฌ๋งŒ ํŒ€] 2020.01.05(ํ™”) - 3์ฃผ์ฐจ ๊ฐœ์ธ ๊ฒฐ๊ณผ

2021. 1. 5. 22:34
๋ชฉ์ฐจ
  1. - ๋ชฉํ‘œ -
  2. 1. root ์ฐพ๊ธฐ
  3. 2. ํŠธ๋ฆฌ ์ˆœํšŒ
  4. 3. ์ตœ์†Œ ๊ณตํ†ต ์กฐ์ƒ ๋…ธ๋“œ
  5. - ๊นƒํ—ˆ๋ธŒ -

- ๋ชฉํ‘œ -

codekodo.tistory.com/12

 

[์ฝ”๋…ํ•˜๊ตฌ๋งŒ ํŒ€] 2021.01.05(ํ™”) - 3์ฃผ์ฐจ ๊ฐœ์ธ ๋ชฉํ‘œ

๋ชฉํ‘œ : LCA(Lowest Common Ancestor) ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ฐœ๋… ๋ฐ ์‹ค์Šต ๋ฌธ์ œ๋ฅผ ๋ณต์Šตํ•˜๊ณ  ๋ฐฑ์ค€ ๋ฌธ์ œ๋ฅผ ํ†ตํ•ด ์‹ค์ œ ๋ฌธ์ œ์— ์ ์šฉํ•ด๋ณธ๋‹ค. ์‹ค์Šต์€ ์ด 4๋ฌธ์ œ๋กœ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ˆ˜์—… ์‹œ๊ฐ„์ด ์ง„ํ–‰๋˜์—ˆ๋˜ ์‹ค์Šต ๋ฌธ์ œ์ด๋‹ค. 1. root ์ฐพ๊ธฐ

codekodo.tistory.com

 

LCA(Lowest Common Ancestor) ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ฐœ๋… ๋ฐ ์‹ค์Šต ๋ฌธ์ œ๋ฅผ ๋ณต์Šตํ•˜๊ณ  ๋ฐฑ์ค€ ๋ฌธ์ œ๋ฅผ ํ†ตํ•ด ์‹ค์ œ ๋ฌธ์ œ์— ์ ์šฉํ•ด๋ด„์œผ๋กœ์จ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋™์ž‘๋ฐฉ์‹์— ๋Œ€ํ•ด ์•Œ๊ฒŒ ๋˜์—ˆ๋‹ค. ์‹ค์Šต์—์„œ ๋ฐฐ์šด ๋ฐฉ์‹์œผ๋กœ ๋ฐฑ์ค€ ๋ฌธ์ œ๋ฅผ ์ ‘๊ทผํ•˜์˜€์ง€๋งŒ ์•„์ง ํ’€์ง€ ๋ชปํ•˜์˜€๋‹ค. ๋‹ค๋ฅธ ๋ฐฉ์‹์œผ๋กœ LCA๋ฅผ ์ ‘๊ทผํ•ด๋ณด๋ ค๊ณ  ํ•œ๋‹ค.

 

1. root ์ฐพ๊ธฐ

def main():
    n = int(input())
    parent = []
    child = []
    
    for _ in range(n):
        node = list(input().split())
        if node[1] != '.' or node[2] != '.':
            parent.append(node[0])
            child.append(node[1])
            child.append(node[2])
    
    for i in parent:    # ๋ถ€๋ชจ ๋…ธ๋“œ๊ฐ€ ์ €์žฅ๋œ ๋ฆฌ์ŠคํŠธ์˜ ์›์†Œ๊ฐ€
        if i not in child:  # ์ž์‹ ๋…ธ๋“œ๊ฐ€ ์ €์žฅ๋œ ๋ฆฌ์ŠคํŠธ์— ์—†์œผ๋ฉด
            root = i
            break
    
    print(root)

if __name__ == "__main__":
    main()

 

A B C ์ธ ๊ฒฝ์šฐ A๊ฐ€ ๋ถ€๋ชจ ๋…ธ๋“œ, B์™€ C๊ฐ€ ์ž์‹ ๋…ธ๋“œ์ด๋‹ค.

B D . ์ธ ๊ฒฝ์šฐ B๊ฐ€ ๋ถ€๋ชจ ๋…ธ๋“œ, D๊ฐ€ ์ž์‹ ๋…ธ๋“œ์ด๋‹ค.

๋”ฐ๋ผ์„œ . ๋ฅผ 1๊ฐœ ์ดํ•˜๋กœ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค๋ฉด ๋ถ€๋ชจ ๋…ธ๋“œ - ์ž์‹ ๋…ธ๋“œ ์Œ์œผ๋กœ ๋ณผ ์ˆ˜ ์žˆ๋‹ค.

์ดํ›„ ๋ถ€๋ชจ ๋…ธ๋“œ์™€ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๊ฐ๊ฐ ๋‹ค๋ฅธ ๋ฆฌ์ŠคํŠธ์— ์ €์žฅํ•œ๋‹ค.

๋ถ€๋ชจ ๋…ธ๋“œ ๋ฆฌ์ŠคํŠธ์˜ ์›์†Œ๊ฐ€ ์ž์‹ ๋…ธ๋“œ ๋ฆฌ์ŠคํŠธ์— ์—†์œผ๋ฉด ์ด๋Š” ๋ฃจํŠธ ๋…ธ๋“œ๋ผ๊ณ  ๋ณผ ์ˆ˜ ์žˆ๋‹ค.

 

2. ํŠธ๋ฆฌ ์ˆœํšŒ

def preorder(node, tree, visit):
    visit.append(node)
    if tree[node][0] != '.':
        preorder(tree[node][0], tree, visit)
    if tree[node][1] != '.':
        preorder(tree[node][1], tree, visit)
    
    return visit

def inorder(node, tree, visit):
    if tree[node][0] != '.':
        inorder(tree[node][0], tree, visit)
    visit.append(node)
    if tree[node][1] != '.':
        inorder(tree[node][1], tree, visit)

    return visit

def postorder(node, tree, visit):
    if tree[node][0] != '.':
        postorder(tree[node][0], tree, visit)
    if tree[node][1] != '.':
        postorder(tree[node][1], tree, visit)
    visit.append(node)

    return visit

def main():
    n = int(input())
    tree = {}
    parent = []
    child = []
    
    for _ in range(n):
        node = list(input().split())
        tree[node[0]] = [node[1], node[2]]  # tree๋ฅผ ๊ตฌํ˜„ํ•œ๋‹ค
        if node[1] != '.' or node[2] != '.':
            parent.append(node[0])
            child.append(node[1])
            child.append(node[2])
    
    for i in parent:    # ๋ถ€๋ชจ ๋…ธ๋“œ๊ฐ€ ์ €์žฅ๋œ ๋ฆฌ์ŠคํŠธ์˜ ์›์†Œ๊ฐ€
        if i not in child:  # ์ž์‹ ๋…ธ๋“œ๊ฐ€ ์ €์žฅ๋œ ๋ฆฌ์ŠคํŠธ์— ์—†์œผ๋ฉด
            root = i
            break
    
    visit = []
    print(*preorder(root, tree, visit))

    visit = []
    print(*inorder(root, tree, visit))

    visit = []
    print(*postorder(root, tree, visit))

if __name__ == "__main__":
    main()

 

1๋ฒˆ ๋ฌธ์ œ๋ฅผ ํ’€๋ฉด์„œ ์‚ฌ์šฉํ•œ root ๋…ธ๋“œ ์ฐพ๋Š” ์ฝ”๋“œ๋ฅผ ๊ทธ๋Œ€๋กœ ์‚ฌ์šฉํ•œ๋‹ค.

์ดํ›„ ์ „์œ„, ์ค‘์œ„, ํ›„์œ„ ํƒ์ƒ‰์„ ์ง„ํ–‰ํ•œ๋‹ค.

์ „์œ„ ํƒ์ƒ‰์˜ ๊ฒฝ์šฐ root > left > right ์ˆœ์œผ๋กœ ๋ฐฉ๋ฌธํ•œ๋‹ค.

์ค‘์œ„ ํƒ์ƒ‰์˜ ๊ฒฝ์šฐ left > root > right ์ˆœ์œผ๋กœ ๋ฐฉ๋ฌธํ•œ๋‹ค.

ํ›„์œ„ ํƒ์ƒ‰์˜ ๊ฒฝ์šฐ reft > right > root ์ˆœ์œผ๋กœ ๋ฐฉ๋ฌธํ•œ๋‹ค.

์œ„์˜ ๊ฐœ๋…์„ ์ฝ”๋“œ๋กœ ๊ตฌํ˜„ํ•œ๋‹ค.

 

3. ์ตœ์†Œ ๊ณตํ†ต ์กฐ์ƒ ๋…ธ๋“œ

def preorder(root, tree, visit, depth_list, depth): # ์ „์œ„ํƒ์ƒ‰์„ ์ง„ํ–‰ํ•˜๋ฉด์„œ ๋ฐฉ๋ฌธ ์ˆœ์„œ์™€ ํƒ์ƒ‰ ๊นŠ์ด๋ฅผ ์ €์žฅํ•œ๋‹ค
    visit.append(root)
    depth_list.append(depth)
    depth += 1
    if tree[root][0] != '.':
        preorder(tree[root][0], tree, visit, depth_list, depth)
        visit.append(root)
        depth -= 1
        depth_list.append(depth)
    depth += 1
    if tree[root][1] != '.':
        preorder(tree[root][1], tree, visit, depth_list, depth)
        visit.append(root)
        depth -= 1
        depth_list.append(depth)

    return visit, depth_list

def main():
    n = int(input())
    tree = {}
    parent = []
    child = []
    
    for _ in range(n):
        node = list(input().split())
        tree[node[0]] = [node[1], node[2]]  # tree๋ฅผ ๊ตฌํ˜„ํ•œ๋‹ค
        if node[1] != '.' or node[2] != '.':
            parent.append(node[0])
            child.append(node[1])
            child.append(node[2])
    
    for i in parent:    # ๋ถ€๋ชจ ๋…ธ๋“œ๊ฐ€ ์ €์žฅ๋œ ๋ฆฌ์ŠคํŠธ์˜ ์›์†Œ๊ฐ€
        if i not in child:  # ์ž์‹ ๋…ธ๋“œ๊ฐ€ ์ €์žฅ๋œ ๋ฆฌ์ŠคํŠธ์— ์—†์œผ๋ฉด
            root = i
            break

    visit = []
    depth_list = []
    depth = 0
    visit, depth_list = preorder(root, tree, visit, depth_list, depth)
    
    find = list(input().split())    # ์งˆ์˜ ๋…ธ๋“œ
    first_index = visit.index(find[0])  # ๋ฐฉ๋ฌธ ์ˆœ์„œ๊ฐ€ ์ €์žฅ๋œ ๋ฆฌ์ŠคํŠธ์—์„œ ์งˆ์˜ ๋…ธ๋“œ๋ฅผ ์ฒ˜์Œ ๋ฐฉ๋ฌธํ•œ index๋ฅผ ์ฐพ๋Š”๋‹ค
    second_index = visit.index(find[1])

    if first_index > second_index:  # ํƒ์ƒ‰์„ ์œ„ํ•ด ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•ด์ค€๋‹ค
        first_index, second_index = second_index, first_index

    max_depth = depth_list[first_index]
    for i in range(first_index+1, second_index+1): # ์ฃผ์–ด์ง„ ๊ตฌ๊ฐ„ ์•ˆ์—์„œ ์ตœ๋Œ€ ๊นŠ์ด๋ฅผ ์ฐพ๋Š”๋‹ค
        if depth_list[i] < max_depth:
            max_depth = depth_list[i]
    
    max_index = depth_list.index(max_depth) # ์ตœ๋Œ€ ๊นŠ์ด์˜ index๋ฅผ ์ €์žฅํ•œ๋‹ค

    print(visit[max_index])

if __name__ == "__main__":
    main()

 

1, 2๋ฒˆ์„ ๋ชจ๋‘ ํ™œ์šฉํ•œ ๋ฌธ์ œ์ด๋‹ค.

์ „์œ„ํƒ์ƒ‰์„ ํ†ตํ•œ ๋…ธ๋“œ ๋ฐฉ๋ฌธ ์ˆœ์„œ์™€ ๋…ธ๋“œ์˜ ๊นŠ์ด๋ฅผ ๊ฐ๊ฐ ๋‹ค๋ฅธ ๋ฆฌ์ŠคํŠธ์— ์ €์žฅํ•œ๋‹ค.

์ฃผ์–ด์ง„ ์ž…๋ ฅ ๊ฐ’์œผ๋กœ ์ด๋ฅผ ๊ตฌํ•ด๋ณด๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

๋ฐฉ๋ฌธ ์ˆœ์„œ : 1 2 4 2 5 2 1 3 1

        ๊นŠ์ด : 0 1 2 1 2 1 0 1 0

 

์ดํ›„ ์ž…๋ ฅ๋œ ์งˆ์˜ ๋…ธ๋“œ์˜ ๋ฐฉ๋ฌธ ์ˆœ์„œ ๋ฆฌ์ŠคํŠธ์—์„œ์˜ index ๊ฐ’์„ ์ฐพ์•„๋‚ธ๋‹ค.

์ฃผ์–ด์ง„ ์ž…๋ ฅ๊ฐ’(3, 4)์œผ๋กœ ์ด๋ฅผ ๊ตฌํ•ด๋ณด๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

๋ฐฉ๋ฌธ ์ˆœ์„œ : 1 2 4 2 5 2 1 3 1

 

์ด index ๊ฐ’์„ ๊นŠ์ด ๋ฆฌ์ŠคํŠธ์—์„œ์˜ ํƒ์ƒ‰ ๋ฒ”์œ„๋กœ ์ •ํ•˜๊ณ  ๋ฒ”์œ„ ์ด๋‚ด์—์„œ ๊ฐ€์žฅ ์ž‘์€ ๊นŠ์ด๊ฐ€ LCA์˜ ๊นŠ์ด๊ฐ€ ๋œ๋‹ค.

  ๊นŠ์ด : 0 1 2 1 2 1 0 1 0

index : 0 1 2 3 4 5 6 7 8

 

๋”ฐ๋ผ์„œ LCA๋Š” ๋ฐฉ๋ฌธ ์ˆœ์„œ ๋ฆฌ์ŠคํŠธ์˜ 7๋ฒˆ์งธ ์›์†Œ์ธ 1์ด ๋œ๋‹ค.

 

- ๊นƒํ—ˆ๋ธŒ -

github.com/k906506/2020_Winter_Assemble-And-selfcode

 

k906506/2020_Winter_Assemble-And-selfcode

Contribute to k906506/2020_Winter_Assemble-And-selfcode development by creating an account on GitHub.

github.com

 

์ €์ž‘์žํ‘œ์‹œ (์ƒˆ์ฐฝ์—ด๋ฆผ)

'โ›น๏ธ ๋ผ์ดํ”„ > 2020 ๊ฒจ์šธ๋ฐฉํ•™ ๋ชจ๊ฐ์ฝ”(๊ฐœ์ธ)' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[์ฝ”๋…ํ•˜๊ตฌ๋งŒ ํŒ€] 2021.01.13(์ˆ˜) - 4์ฃผ์ฐจ ๊ฐœ์ธ ๊ฒฐ๊ณผ  (0) 2021.01.13
[์ฝ”๋…ํ•˜๊ตฌ๋งŒ ํŒ€] 2021.01.13(์ˆ˜) - 4์ฃผ์ฐจ ๊ฐœ์ธ ๋ชฉํ‘œ  (0) 2021.01.13
[์ฝ”๋…ํ•˜๊ตฌ๋งŒ ํŒ€] 2021.01.05(ํ™”) - 3์ฃผ์ฐจ ๊ฐœ์ธ ๋ชฉํ‘œ  (0) 2021.01.05
[์ฝ”๋…ํ•˜๊ตฌ๋งŒ ํŒ€] 2020.12.30(์ˆ˜) - 2์ฃผ์ฐจ ๊ฐœ์ธ ๊ฒฐ๊ณผ  (0) 2020.12.30
[์ฝ”๋…ํ•˜๊ตฌ๋งŒ ํŒ€] 2020.12.30(์ˆ˜) - 2์ฃผ์ฐจ ๊ฐœ์ธ ๋ชฉํ‘œ  (0) 2020.12.30
  1. - ๋ชฉํ‘œ -
  2. 1. root ์ฐพ๊ธฐ
  3. 2. ํŠธ๋ฆฌ ์ˆœํšŒ
  4. 3. ์ตœ์†Œ ๊ณตํ†ต ์กฐ์ƒ ๋…ธ๋“œ
  5. - ๊นƒํ—ˆ๋ธŒ -
'โ›น๏ธ ๋ผ์ดํ”„/2020 ๊ฒจ์šธ๋ฐฉํ•™ ๋ชจ๊ฐ์ฝ”(๊ฐœ์ธ)' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [์ฝ”๋…ํ•˜๊ตฌ๋งŒ ํŒ€] 2021.01.13(์ˆ˜) - 4์ฃผ์ฐจ ๊ฐœ์ธ ๊ฒฐ๊ณผ
  • [์ฝ”๋…ํ•˜๊ตฌ๋งŒ ํŒ€] 2021.01.13(์ˆ˜) - 4์ฃผ์ฐจ ๊ฐœ์ธ ๋ชฉํ‘œ
  • [์ฝ”๋…ํ•˜๊ตฌ๋งŒ ํŒ€] 2021.01.05(ํ™”) - 3์ฃผ์ฐจ ๊ฐœ์ธ ๋ชฉํ‘œ
  • [์ฝ”๋…ํ•˜๊ตฌ๋งŒ ํŒ€] 2020.12.30(์ˆ˜) - 2์ฃผ์ฐจ ๊ฐœ์ธ ๊ฒฐ๊ณผ
kodo_o
kodo_o
iOS ๊ฟ€์žผ!
kodo_o
๐ŸŽ๐Ÿ
kodo_o
์ „์ฒด
์˜ค๋Š˜
์–ด์ œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (149)
    • ๐Ÿ”จ ํ”„๋กœ์ ํŠธ (0)
      • TP 1 (0)
      • WhiteHCCTV (0)
      • FootPrint (0)
    • ๐Ÿ’ป ๊ฐœ๋ฐœ (63)
      • iOS (30)
      • Android (6)
      • Kotlin (4)
      • Flutter (9)
      • Node.js (5)
      • Architecture (1)
      • ์˜ค๋Š˜์˜ ์‚ฝ์งˆ (7)
      • ์—๋Ÿฌ์™€์˜ ๋™์นจ (1)
    • โœ๏ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (6)
      • Graph (6)
      • String (0)
      • Sort (0)
    • โœ๏ธ ์ฝ”ํ…Œ ์ค€๋น„ (44)
      • Math (1)
      • Implementation (3)
      • String (3)
      • Brute Force (5)
      • Back Tracking (7)
      • Greedy (0)
      • Dynamic Programming (13)
      • Binary Search (1)
      • DFS, BFS (5)
      • Shortest Path (2)
      • Two Pointer (4)
      • MST (0)
    • ๐Ÿ“š CS (6)
      • Operating System (6)
    • โ›น๏ธ ๋ผ์ดํ”„ (30)
      • 2020 ๊ฒจ์šธ๋ฐฉํ•™ ๋ชจ๊ฐ์ฝ”(๊ฐœ์ธ) (12)
      • 2021 ์—ฌ๋ฆ„๋ฐฉํ•™ ๋ชจ๊ฐ์ฝ”(๊ฐœ์ธ) (6)
      • ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ (1)
      • ํšŒ๊ณ  (10)

๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

  • ํ™ˆ
  • ๊นƒํ—ˆ๋ธŒ

์ธ๊ธฐ ๊ธ€

์ตœ๊ทผ ๊ธ€

์ตœ๊ทผ ๋Œ“๊ธ€

hELLO ยท Designed By ์ •์ƒ์šฐ.
kodo_o
[์ฝ”๋…ํ•˜๊ตฌ๋งŒ ํŒ€] 2020.01.05(ํ™”) - 3์ฃผ์ฐจ ๊ฐœ์ธ ๊ฒฐ๊ณผ
์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”

๋‹จ์ถ•ํ‚ค

๋‚ด ๋ธ”๋กœ๊ทธ

๋‚ด ๋ธ”๋กœ๊ทธ - ๊ด€๋ฆฌ์ž ํ™ˆ ์ „ํ™˜
Q
Q
์ƒˆ ๊ธ€ ์“ฐ๊ธฐ
W
W

๋ธ”๋กœ๊ทธ ๊ฒŒ์‹œ๊ธ€

๊ธ€ ์ˆ˜์ • (๊ถŒํ•œ ์žˆ๋Š” ๊ฒฝ์šฐ)
E
E
๋Œ“๊ธ€ ์˜์—ญ์œผ๋กœ ์ด๋™
C
C

๋ชจ๋“  ์˜์—ญ

์ด ํŽ˜์ด์ง€์˜ URL ๋ณต์‚ฌ
S
S
๋งจ ์œ„๋กœ ์ด๋™
T
T
ํ‹ฐ์Šคํ† ๋ฆฌ ํ™ˆ ์ด๋™
H
H
๋‹จ์ถ•ํ‚ค ์•ˆ๋‚ด
Shift + /
โ‡ง + /

* ๋‹จ์ถ•ํ‚ค๋Š” ํ•œ๊ธ€/์˜๋ฌธ ๋Œ€์†Œ๋ฌธ์ž๋กœ ์ด์šฉ ๊ฐ€๋Šฅํ•˜๋ฉฐ, ํ‹ฐ์Šคํ† ๋ฆฌ ๊ธฐ๋ณธ ๋„๋ฉ”์ธ์—์„œ๋งŒ ๋™์ž‘ํ•ฉ๋‹ˆ๋‹ค.