[파이썬] 1231. 중위순회

다음은 특정 단어(또는 문장)를 트리 형태로 구성한 것으로, in-order 형식으로 순회하여 각 노드를 읽으면 원래 단어를 알 수 있다고 한다.

위 트리를 in-order 형식으로 순회할 경우 SOFTWARE 라는 단어를 읽을 수 있다.

 

제한조건

총 10개의 테스트 케이스가 주어진다.

총 노드의 개수는 100개를 넘어가지 않는다.

트리는 완전 2진 트리 형식으로 주어지며, 노드당 하나의 알파벳만 저장할 수 있다.

노드가 주어지는 순서는 아래 입력 예시와 같이 숫자 번호대로 주어진다.

 

 

입력

입력 파일의 첫 줄에는 각 케이스의 트리가 갖는 정점의 총 수 N(1 <= N <= 100)이 주어진다. 그 다음 N줄에 걸쳐 각각의 정점 정보가 주어진다.

해당 정점에 대한 정보는 해당 정점의 알파벳, 해당 정점의 왼쪽 자손, 오른쪽 자손의 정점번호가 차례대로 주어진다.

정점번호는 1부터 N까지의 정수로 구분된다. 입력에서 정점 번호를 매기는 규칙은 위와 같으며, 루트 정점의 번호는 반드시 1이다.

입력에서 이웃한 알파벳이나 자손 정점의 번호는 모두 공백으로 구분된다.

위의 예시에서, 알파벳 S가 7번 정점에 해당하면 "7 S"으로 주어지고, 알파벳 F가 2번 정점에 해당하면 두 자손익 ㅏㄱ각 알파벳 0인 4번 정점과 알파벳 T인 5번 정점이므로 "2 F 4 5"로 주어진다.

총 10개의 테스트 케이스가 주어진다.

 

입력 예시

8    // 정점의 총 수 N

1 W 2 3   // 해당 정점의 번호, 정점의 알파벳, 왼쪽, 오른쪽 자손

2 F 4 5

3 R 6 7

4 O 8

5 T

6 A

7 E

8 S

 

출력

테스트 케이스 각각에 대한 답을 출력한다. 각 줄은 '#x'로 시작하고 개행을 한 후 다음 답을 기록한다.

여기서 x는 테스트 케이스의 번호이다.

 

출력 예시

#1 SOFTWARE   // 테스트 케이스 1번 답

 

 

🍗 나의 풀이

 

def in_order(v) :		# 중위 순회
  if v <= N :
    in_order(v*2)		# 왼쪽 자식
    print(tree[v], end='')	# 루트
    in_order(v*2+1)		# 오른쪽 자식
    
for test_case in range(10):
    N=int(input())				# 총 정점의 수
    tree=[[0] for _ in range(N+1)]	# 0은 버릴려고 N+1만큼 / 1차원 리스트 [0]*(N+1)로 하기..
    for i in range(N) :				
        info=input().split()			# 정점 정보 입력
        tree[int(info[0])]=info[1]		# 인덱스 = 노드 번호, 값 = 노드 값
    print(f'#{test_case+1} ', end='')
    in_order(1)
    print()

 

정점에 대해 '해당 정점의 번호, 정점의 알파벳, 왼쪽, 오른쪽 자손'으로 주어진다.

왼쪽, 오른쪽 자손 정보는 이용하지 않아도 문제 푸는데 어려움이 없음.

인덱스 번호 v가 정점의 개수 N이 될 때까지 재귀호출.

 

 

🥓 다른 사람 풀이

 

# 출처  https://smilelife12.github.io/Algorithm-SW1231/
def inorder(t, idx) :		# 중위 순회
    temp=''
    if idx*2 < len(t) :
        temp+=inorder(t, idx*2)		# 왼쪽
    temp+=t[idx]		# 루트
    if idx*2+1 < len(t) :
        temp+=inorder(t, idx*2+1)	# 오른쪽
    return temp		# 문자열 완성 후 반환

for test_case in range(10) :
    N=int(input())		# 총 정점의 수
    tree=[0]*(N+1)
    for i in range(1, N+1) :		# 노드 번호 1부터 시작
        s=list(input().split())
        tree[int(s[0])]=s[1]	# 인덱스 = 노드 번호, 값 = 노드 값
    s=inorder(tree, 1)
    print("#"+str(test_case+1)+" "+s)

 

tree를 1차원 리스트로 만들어도 되는데 왜 난 2차원 리스트로 만들었지..??

temp에 문자를 더해가며 문자열을 만들어서 반환.

출력 부분이 아쉽다.

 

# 출처 https://swbeginner.tistory.com/entry/SWEA-%EC%BD%94%EB%94%A9-SW-%EB%AC%B8%EC%A0%9C%ED%95%B4%EA%B2%B0-%EA%B8%B0%EB%B3%B8-%EC%A4%91%EC%9C%84%EC%88%9C%ED%9A%8C-PYTHON-1231
def dfs(idx) :
    global res
    
    # 길이가 4인 경우(자식이 둘인 경우)
    if len(node[idx]) == 4 :
        # 왼쪽 -> 정점 -> 오른쪽 순으로 확인
        dfs(int(node[idx][2]))
        res+=node[idx][1]
        dfs(int(node[idx][3]))
        
    # 길이가 3인 경우(자식이 하나인 경우)
    elif len(node[idx]) == 3 :
        dfs(int(node[idx][2]))
        res+=node[idx][1]
    # 자식이 없는 경우
    else :
        res+=node[idx][1]
    return

for tc in range(1, 11) :
    n=int(input())
    
    # 정점 번호는 1부터 시작이라 앞에 0 추가함
    node=[[0]]+[list(map(str, input().split())) for _ in range(n)]
    
    res=''
    
    # 정점 번호
    dfs(1)
    
    print('#{} {}'.format(tc, res))

 

노드의 자식 수에 따라 재귀 호출 횟수를 달리함.

왼쪽 자식 노드 = 2*i, 오른쪽 자식 노드 = 2*i+1임을 모를 때 사용할 수 있는 방법.

 

 

 

 

 

문제 출처 : SW expert academy