문제
이진트리를 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 그리려고 한다. 이때 다음의 규칙에 따라 그리려고 한다.
이진트리에서 같은 레벨(level)에 있는 노드는 같은 행에 위치한다. 한 열에는 한 노드만 존재한다. 임의의 노드의 왼쪽 부트리(left subtree)에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트리(right subtree)에 있는 노드들은 해당 노드보다 오른쪽의 열에 위치한다. 노드가 배치된 가장 왼쪽 열과 오른쪽 열 사이엔 아무 노드도 없이 비어있는 열은 없다. 이와 같은 규칙에 따라 이진트리를 그릴 때 각 레벨의 너비는 그 레벨에 할당된 노드 중 가장 오른쪽에 위치한 노드의 열 번호에서 가장 왼쪽에 위치한 노드의 열 번호를 뺀 값 더하기 1로 정의한다. 트리의 레벨은 가장 위쪽에 있는 루트 노드가 1이고 아래로 1씩 증가한다.
아래 그림은 어떤 이진트리를 위의 규칙에 따라 그려 본 것이다. 첫 번째 레벨의 너비는 1, 두 번째 레벨의 너비는 13, 3번째, 4번째 레벨의 너비는 각각 18이고, 5번째 레벨의 너비는 13이며, 그리고 6번째 레벨의 너비는 12이다.
우리는 주어진 이진트리를 위의 규칙에 따라 그릴 때에 너비가 가장 넓은 레벨과 그 레벨의 너비를 계산하려고 한다. 위의 그림의 예에서 너비가 가장 넓은 레벨은 3번째와 4번째로 그 너비는 18이다. 너비가 가장 넓은 레벨이 두 개 이상 있을 때는 번호가 작은 레벨을 답으로 한다. 그러므로 이 예에 대한 답은 레벨은 3이고, 너비는 18이다.
임의의 이진트리가 입력으로 주어질 때 너비가 가장 넓은 레벨과 그 레벨의 너비를 출력하는 프로그램을 작성하시오
입력
첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. 노드들의 번호는 1부터 N까지이며, 자식이 없는 경우에는 자식 노드의 번호에 -1이 주어진다.
출력
첫째 줄에 너비가 가장 넓은 레벨과 그 레벨의 너비를 순서대로 출력한다. 너비가 가장 넓은 레벨이 두 개 이상 있을 때에는 번호가 작은 레벨을 출력한다.
My solution (Python)
import sys
def dfs(node, dic, valDic, leftNum, rightNum):
if dic.get(node)[0] + dic.get(node)[1] == -2:
valDic[node] = [0, 0]
return 1
leftRes, rightRes = 0, 0
if dic.get(node)[0] != -1:
leftRes += dfs(dic.get(node)[0], dic, valDic, leftNum, rightNum)
if dic.get(node)[1] != -1:
rightRes += dfs(dic.get(node)[1], dic, valDic, leftNum, rightNum)
valDic[node] = [leftRes, rightRes]
return leftRes + rightRes + 1
def dfs2(node, dic, valDic, flag, prev, depth, levelDic):
nodeLocation = [0, 0]
if flag == 0:
nodeLocation[0] = prev - valDic.get(node)[1] - 1
else:
nodeLocation[0] = prev + valDic.get(node)[0] + 1
nodeLocation[1] = depth + 1
if nodeLocation[1] not in levelDic.keys():
levelDic[nodeLocation[1]] = [nodeLocation[0]]
else:
levelDic.get(nodeLocation[1]).append(nodeLocation[0])
if dic.get(node)[0] != -1:
dfs2(dic.get(node)[0], dic, valDic, 0, nodeLocation[0], depth + 1, levelDic)
if dic.get(node)[1] != -1:
dfs2(dic.get(node)[1], dic, valDic, 1, nodeLocation[0], depth + 1, levelDic)
N = int(sys.stdin.readline())
dic = dict(zip([i for i in range(N + 1)], [[] for _ in range(N + 1)]))
valDic = dict(zip([i for i in range(N + 1)], [[0, 0] for _ in range(N + 1)]))
filterSet = set()
for _ in range(N):
a, b, c = map(int, sys.stdin.readline().split(" "))
dic[a] = [b, c]
filterSet.add(b)
filterSet.add(c)
rootNum = 0
for i in range(1, N + 1):
if i not in filterSet:
rootNum = i
break
dfs(rootNum, dic, valDic, 0, 0)
levelDic = {}
dfs2(rootNum, dic, valDic, 1, 0, 0, levelDic)
res = [0, 0]
for level in levelDic.keys():
if max(levelDic.get(level)) - min(levelDic.get(level)) + 1 > res[1]:
res[0] = level
res[1] = max(levelDic.get(level)) - min(levelDic.get(level)) + 1
print(res[0], res[1])
My logic & Feedback
문제가 요구하는 사고방식의 접근은 어렵지 않았으나, 구현이 빡셌다.
접근방식은,
1) set자료구조로 input으로 들어오는 노드 번호를 넣어서 루트 노드를 찾는다.
2) dfs로 한 노드에 달려있는 왼쪽 subtree와 오른쪽 subtree의 개수를 dictionary에 넣는다. -> valDic[node] = [leftRes, rightRes]
3) 레벨에 따라 포함되는 노드를 levelDic 이라는 dictionary에 넣어 최종적으로 levelDic의 최대 너비를 반환하면 된다.
4) levelDic에 노드를 넣는 dfs2함수를 선언, 2)번과 마찬가지로 dfs를 돌면서 자신의 subtree와 depth를 이용하여 levelDic에 노드의 위치 정보를 넣는다.
5) levelDic의 너비 max값을 반환한다.
결국 각 노드의 subtree 노드를 계산하는 것이 한 부분,
노드 좌표를 이용하여 가장 큰 너비를 반환하는 것이 한 부분인 문제였다.
문제를 풀고 나서 다른사람들의 풀이를 봤는데,
중위순회(in-order) dfs를 사용하여 푸는 것이 정석이라는 것을 깨달았고,
나의 접근방법도 결국엔 중위순회인 것을 알게 되었다(재귀의 왼쪽 결과를 leftRes에 반환하고 다시 dfs에 진입).
중위순회의 개념은 알고 있었지만 ‘이 문제는 중위순회 개념으로 푸는 문제구나’ 라는 것까지는 생각이 미치지 않았다.
트리에서 순회 관련 문제가 나오면 전위,중위,후위,레벨 순회 라는 개념으로 풀 수는 없을까 라고
한번 되짚고 나서 문제풀이를 하는 습관을 기르자.