[실버 I] 1991번. 트리 순회

 문제 

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

1991번: 트리 순회

 사용 언어 

Python3

 풀이 과정 

사실 이 문제는 4256번. 트리 문제를 풀기 전에 풀었어야 순서적으로 맞았을 것 같다.

그 때 더 어려운 문제를 풀면서 확실히 기억했던 건 전위순회, 중위순회, 후위순회의 구현시 차이점은 print() 하는 순서의 차이였다는 것..?

그래서 딕셔너리를 이용해 혼자 풀어보다가, 마음에 안들어서 구글링을 한 뒤 class를 이용한 풀이로 변경했다.

 

아직까지 파이썬에서는 문제 풀이에 class를 사용해본 적이 없었는데, 트리의 경우 본인과 왼쪽, 오른쪽 노드가 있어 class의 __init__함수를 사용해보기에 적절했다.

 

암튼 맞았습니다!!

 

 제출 답안 

from sys import stdin
input = stdin.readline

N = int(input())
inputs = [list(input().split()) for _ in range(N)]

class Node():
    def __init__(self, item, left, right):
        self.item = item
        self.left = left
        self.right = right

def preorder(node):
    print(node.item, end = '')
    if node.left != ".":
        preorder(tree[node.left])
    if node.right != '.':
        preorder(tree[node.right])

def inorder(node):
    if node.left != '.':
        inorder(tree[node.left])
    print(node.item, end = '')
    if node.right != '.':
        inorder(tree[node.right])

def postorder(node):
    if node.left != '.':
        postorder(tree[node.left])
    if node.right != '.':
        postorder(tree[node.right])
    print(node.item, end = '')

tree = {}
for item, left, right in inputs:
    tree[item] = Node(item, left, right)
    
preorder(tree['A'])
print()
inorder(tree['A'])
print()
postorder(tree['A'])

 

 공부한 내용 

파이썬의 클래스와 메서드

1. 선언하기

클래스는 class에 클래스 이름을 지정하고 :(콜론)을 붙인 뒤 다음 줄부터 def로 메서드를 작성하면 된다. 여기서 메서드는 클래스 안에 들어있는 함수를 뜻한다.

클래스 이름을 짓는 방법은 변수와 같다. 하지만 몇 가지 규칙이 있는데 다음과 같다.

• 보통 파이썬에서는 클래스의 이름은 대문자로 시작한다.
• 메서드 작성 방법은 함수와 같으며 코드는 반드시 들여쓰기를 해야 한다.
• 메서드의 첫 번째 매개변수는 반드시 self로 지정해야 한다.

class 클래스이름:
    def 메서드(self):
        코드

2. 할당하기

클래스는 특정 개념을 표현만 할 뿐 사용을 하려면 인스턴스를 생성해야 한다.

인스턴스명 = 클래스()

3. 메서드 호출하기

메서드는 클래스가 아니라 인스턴스를 통해 호출한다. 인스턴스 뒤에 .(점)을 붙이고 메서드를 호출하면 된다.

인스턴스명.메서드()

4. 기타

지금까지 사용한 int, list, dict 등도 사실 클래스이고 지금까지 이 클래스로 인스턴스를 만들고 메서드를 사용했다고 이해하니 편했다.

 

아래는 list 클래스의 인스턴스 a를 할당하고 a의 메서드 sort를 호출한 것이라고 할 수 있다.

sort와 sorted 중 어떤 게 반환값을 return 해주는 함수인지 계속 헷갈렸는데 list 클래스의 메서드 sort는 반환을 해주고 python의 내장함수 sorted는 반환값을 변수에 할당해줘야 한다는 차이가 이제 좀 이해가 되는....순간이다..ㅎ

a = list(range(10)) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
a.sort(reverse = True)
print(a) # [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

 

출처: https://dojang.io/mod/page/view.php?id=2372

 

 다른 풀이 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def preorder(node):
    if node == '.':
        return
    print(node, end = "")
    preorder(tree[node][0])
    preorder(tree[node][1])

def inorder(node):
    if node == '.':
        return
    inorder(tree[node][0])
    print(node, end = "")
    inorder(tree[node][1])

def postorder(node):
    if node == '.':
        return
    postorder(tree[node][0])
    postorder(tree[node][1])
    print(node, end = "")

n = int(input())
tree = {}

for _ in range(n):
    root, left, right = input().split()
    tree[root] = (left, right)

preorder('A')
print()
inorder('A')
print()
postorder('A')

➡ 사용한 메모리와 걸린 시간 모두 class를 사용했을 때와 똑같다. 그래도 경우에 따라 class를 사용한 풀이가 더 좋은 대접(?)을 받는 것 같아 파이썬에서의 class 사용 방법도 알아둬야겠다.