문제 정보
https://www.acmicpc.net/problem/1991
문제
이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.
예를 들어 위와 같은 이진 트리가 입력되면,
- 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
- 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
- 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)
가 된다.
입력
첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.
출력
첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.
접근방법
1. 트리를 만들자
트리는 부모 - 왼쪽자식, 오른쪽 자식 으로 이루어져 있다.
리스트에 각각 노드의 값을 넣어두고 순회할 때 이를 사용하자
2. 각 순회의 개념에 대해 잘 생각해보자
부모를 N 왼쪽 자식을 L 오른쪽 자식을 R 이라고 했을 때
전위 => N L R
중위 => L N R
후위 => L N R
으로 출력할 수 있다.
재귀를 이용해서 노드를 파고들 수 있게 하고 전부 파고든 뒤 조건에 맞게 출력하자
3. 문자로 이루어진 트리이다.
일반적인 트리와 달리 문자로 이루어져 있다.
출력할 수 있는 조건을 잘 맞춰주자
1차 풀이(오답)
import sys;
sys.stdin = open('sample.txt')
def PRE(v):
if v == 0:
return
print(T[v], end='')
PRE(L[v])
PRE(R[v])
def IN(v):
if v == 0:
return
IN(L[v])
print(T[v], end='')
IN(R[v])
def POST(v):
if v == 0:
return
POST(L[v])
POST(R[v])
print(T[v], end='')
V = int(input())
# 왼쪽
L = [0] * (V+1)
# 오른쪽
R = [0] * (V+1)
# 트리 연결용
T = [0] * (V+1)
# 입력 받을것 T[i] 에 루트를 넣을거임
for i in range(V):
tree = input().split()
T[i+1] = tree[0]
if tree[1] == '.':
pass
else:
L[i+1] = tree[1]
# L[i+1] = i+2
if tree[2] == '.':
pass
else:
R[i+1] = tree[2]
# R[i+1] = i+3
PRE(1)
print()
IN(1)
print()
POST(1)
정답 자체는 제출하지 않았지만
계속 인덱스 오류가 나서 많이 애먹었다.
접근방법의 3을 생각하지 않아서 생긴 문제였다.
T = [0, 'A', 'B', 'C', 'E', 'F', 'D', 'G']
R = [0, 'C', 0, 'F', 0, 'G', 0, 0]
L = [0, 'B', 'D', 'E', 0, 0, 0, 0]
각 트리들은 위 처럼 문자와 숫자로 구성돼 있는데 함수 호출은 1으로 하고 있기 때문에
재귀 호출을 만나면 숫자 => 문자로 바뀌고 에러가 나온다.
2차 풀이(정답)
import sys;
sys.stdin = open('sample.txt')
def PRE(v):
if v == 0:
return
if v in T:
v = T.index(v)
print(T[v], end='')
PRE(L[v])
PRE(R[v])
def IN(v):
if v == 0:
return
if v in T:
v = T.index(v)
IN(L[v])
print(T[v], end='')
IN(R[v])
def POST(v):
if v == 0:
return
if v in T:
v = T.index(v)
POST(L[v])
POST(R[v])
print(T[v], end='')
V = int(input())
# 왼쪽
L = [0] * (V+1)
# 오른쪽
R = [0] * (V+1)
# 트리 연결용
T = [0] * (V+1)
# 입력 받을것 T[i] 에 루트를 넣을거임
for i in range(V):
tree = input().split()
T[i+1] = tree[0]
if tree[1] == '.':
pass
else:
L[i+1] = tree[1]
if tree[2] == '.':
pass
else:
R[i+1] = tree[2]
PRE('A')
print()
IN('A')
print()
POST('A')
위의 문제를 해결했다.
노드의 이름은 'A' 부터 시작한다는 조건이 있기 때문에 가장 최상위 부모노드는 무조껀 'A'가 된다.
따라서 함수를 호출할 때 가장 최상위 노드를 직접적으로 호출했다.
문자가 그대로 넘어가면 해당 위치에 어떤 문자가 있는지 알 수 없기 때문에
이를 전체 트리 리스트의 인덱스 위치로 바꿀 수 있도록 내장메서드 index를 사용하였고
1. 순회함수('A') 가 호출됨
2. v = 'A'
3. v가 0 이면(자식 노드가 없으면) 리턴
4. v(문자)가 트리 안에 있을 경우
v = T.index(v) 를 통해서 트리의 어디에 있는지 찾고
조건에 맞는 함수를 재귀호출 => 자식이 없는 위치까지 파고듬
위와 같은 순서로 코드가 진행될 수 있게 해 주었다.
느낀점
트리 수업을 자세하게 하지 않았고, 꽤 오래전에 배웠는데 그동안 한번도 문제를 풀어보지 않았다.
내일부터 다시 알고리즘 주간에 들어가는데 첫 수업이 트리이기도 하고 스터디에서 트리 문제가 나와서
유튜브를 통해서 아주 기초적인 부분을 공부했다.
트리 개념과 트리 순회(전위, 중위 후위)를 공부하기에 좋을 것 같아서 선택한 문제였고 백준 티어는
신경쓰지 않았는데 막상 문제를 풀어보니 티어가 높은 이유는 있는 것 같더라
내장 메서드를 사용하긴 했지만 문자로 된 리스트에서 어떻게 인덱스 접근을 해야할지 조금은 다시 생각해 본 것 같다.
다른사람 풀이를 보니까 딕셔너리를 사용한 사람도 있었다. 문제를 풀때 매번 리스트만 사용하고 있는데
딕셔너리를 사용하는 연습도 해야할 것 같다.
'컴퓨터 > Algorithm' 카테고리의 다른 글
백준 1181 단어 정렬 (파이썬) (0) | 2022.09.20 |
---|---|
백준 2589 보물섬 (파이썬) (0) | 2022.09.14 |
백준 17298 오큰수 (파이썬) (0) | 2022.09.12 |
백준 1759 암호 만들기 (파이썬) (0) | 2022.09.09 |
백준 15649 N과 M (4) (파이썬) (0) | 2022.09.07 |