프로그래머스 - 길 찾기 게임(Python3) Class(Node)를 이용해보기
해당 문제는 2019 KAKAO BLIND RECRUITMENT에 나왔던 문제로 다른 사람들의 풀이와는 다르진 않지만 Class(Node)를 이용해서 풀어보는 법을 공유해보고자 한다.
길 찾기 게임
전무로 승진한 라이언은 기분이 너무 좋아 프렌즈를 이끌고 특별 휴가를 가기로 했다.
내친김에 여행 계획까지 구상하던 라이언은 재미있는 게임을 생각해냈고 역시 전무로 승진할만한 인재라고 스스로에게 감탄했다.
라이언이 구상한(그리고 아마도 라이언만 즐거울만한) 게임은, 카카오 프렌즈를 두 팀으로 나누고, 각 팀이 같은 곳을 다른 순서로 방문하도록 해서 먼저 순회를 마친 팀이 승리하는 것이다.
그냥 지도를 주고 게임을 시작하면 재미가 덜해지므로, 라이언은 방문할 곳의 2차원 좌표 값을 구하고 각 장소를 이진트리의 노드가 되도록 구성한 후, 순회 방법을 힌트로 주어 각 팀이 스스로 경로를 찾도록 할 계획이다.
라이언은 아래와 같은 특별한 규칙으로 트리 노드들을 구성한다.
- 트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다.
- 모든 노드는 서로 다른 x값을 가진다.
- 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다.
- 자식 노드의 y 값은 항상 부모 노드보다 작다.
- 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
- 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.
아래 예시를 확인해보자.
라이언의 규칙에 맞게 이진트리의 노드만 좌표 평면에 그리면 다음과 같다. (이진트리의 각 노드에는 1부터 N까지 순서대로 번호가 붙어있다.)
이제, 노드를 잇는 간선(edge)을 모두 그리면 아래와 같은 모양이 된다.
위 이진트리에서 전위 순회(preorder), 후위 순회(postorder)를 한 결과는 다음과 같고, 이것은 각 팀이 방문해야 할 순서를 의미한다.
- 전위 순회 : 7, 4, 6, 9, 1, 8, 5, 2, 3
- 후위 순회 : 9, 6, 5, 8, 1, 4, 3, 2, 7
다행히 두 팀 모두 머리를 모아 분석한 끝에 라이언의 의도를 간신히 알아차렸다.
그러나 여전히 문제는 남아있다. 노드의 수가 예시처럼 적다면 쉽게 해결할 수 있겠지만, 예상대로 라이언은 그렇게 할 생각이 전혀 없었다.
이제 당신이 나설 때가 되었다.
곤경에 빠진 카카오 프렌즈를 위해 이진트리를 구성하는 노드들의 좌표가 담긴 배열 nodeinfo가 매개변수로 주어질 때,
노드들로 구성된 이진트리를 전위 순회, 후위 순회한 결과를 2차원 배열에 순서대로 담아 return 하도록 solution 함수를 완성하자.
제한사항
- nodeinfo는 이진트리를 구성하는 각 노드의 좌표가 1번 노드부터 순서대로 들어있는 2차원 배열이다.
- nodeinfo의 길이는 1 이상 10,000 이하이다.
- nodeinfo[i] 는 i + 1번 노드의 좌표이며, [x축 좌표, y축 좌표] 순으로 들어있다.
- 모든 노드의 좌표 값은 0 이상 100,000 이하인 정수이다.
- 트리의 깊이가 1,000 이하인 경우만 입력으로 주어진다.
- 모든 노드의 좌표는 문제에 주어진 규칙을 따르며, 잘못된 노드 위치가 주어지는 경우는 없다.
1. 문제 접근
1. 트리를 어떻게 만들어 낼것인가?
2. 만든 트리의 전위, 후위 탐색
(2번 전위 탐색, 후위 탐색은 개념만 알고 있다면 구현이 어렵진 않아서 따로 기술 하진 않겠다.)
1번은 여러가지 방법이 있겠지만 나같은 경우엔 Dictionary를 이용하여 먼저 Node_Info를 정리하고 이를 이용해 이진 트리를 만드는 방법을 선택했다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Node:
def __init__(self, x, data):
self.parent = None # 부모 노드
self.children = [None, None] # 자식 노드 2개
self.node_x = x # 해당 노드의 x 값
self.data = data # 해당 노드의 데이터
# dic[node_y] = [[node1_x, data1], [node2_x, data2], ...]
dic = {
1: [[2, 3], [4, 4]],
2: [[3, 2]],
3: [[5, 1]]
}
|
cs |
문제는 이진트리의 생성이다.
내가 생각한 이진트리의 생성은 이중 for문을 이용하여 루트 부터 leaf 노드까지 만들어 나가는 것인데 코드는 다음과 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
# 루트 노드부터 리프 노드까지
for Top, y in enumerate(sorted(dic, reverse=True)):
new_p = []
# 왼쪽부터 오른쪽으로
for n in sorted(dic[y]):
new_node = Node(n[0], n[1])
if Top == 0: # 해당 노드가 시작이라면(루트 노드)
new_node.parent = root # root를 찾기 위한 가짜 root 노드의 자식인 진짜 root 노드
else:
past = None # 부모 노드 후보군
# 부모 노드를 결정하기 위한 반복문
for p_node in p:
# 만약 새로운 노드가 부모 노드보다 x값이 작다면
if n[0] < p_node.x:
# 부모 후보군이 있다면 후보군과의 거리를 비교하여
# 더 가까운 노드를 부모 노드로 선택
if past and p_dist < abs(p_node.x - new_node.x):
new_node.parent = past
break
new_node.parent = p_node
break
# 만약 새로운 노드가 부모 노드보다 x값이 크다면
elif not p_node.children[1]:
# 거리와 부모 후보군을 저장
p_dist = abs(p_node.x - new_node.x)
past = p_node
else:
# 만약 마지막 노드가 부모 후보군이였다면 부모 노드로 결정
new_node.parent = p_node
# 부모 노드보다 x가 작다면 왼쪽 자식으로 아니면 오른쪽으로
if new_node.parent.x > new_node.x:
new_node.parent.children[0] = new_node
else:
new_node.parent.children[1] = new_node
# 다음 세대의 부모 노드
new_p.append(new_node)
p = new_p
|
cs |
이 때 애매한 경우가 생긴다. 새로운 노드가 부모노드의 왼쪽과 오른쪽중 어느쪽으로 정해지는 지는 x값을 통해 정할 수 있지만 부모 노드의 결정이 애매할 때가 있다.
좌표계 형태로 데이터가 있기 떄문에 9번과 5번은 거리가 약 489.001 1번과 5번의 거리는 약 11.045다
문제에선 자식노드가 다음과 같을경우 어떤 노드를 우선순위로 한다는 말이 제한사항에 없어서
조건 누락으로 생각했고 거리를 통해 결정하게 만들었었다. 결과는 실패
원인을 찾기 위해 문제를 다시 보던 중 문항에 특별한 규칙 부분을 다시 보았다.
- 트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다. (패스)
- 모든 노드는 서로 다른 x값을 가진다. (패스)
- 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다. (패스)
- 자식 노드의 y 값은 항상 부모 노드보다 작다. (패스)
- 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다. (?)
- 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다. (?)
서브 트리의 모든 노드가 크거나 작아야 됨으로 5번 노드는 4번 노드 보다 x값이 작으므로 무조건 4번 노드의 왼쪽 으로 가야되므로 9번의 자식 노드가 되야 했다.
그렇다면 노드의 위치를 결정하는것은 자신의 부모 뿐만 아니라 부모의 부모들도 영향을 끼치는 것이였고 이를 이용하기 위해 max_right를 node의 요소로 만들었다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Node:
def __init__(self, x, data):
self.parent = None # 부모 노드
self.children = [None, None] # 자식 노드 2개
self.node_x = x # 해당 노드의 x 값
self.data = data # 해당 노드의 데이터
self.max_right = 100000 # 오른쪽 최대 범위
# dic[node_y] = [[node1_x, data1], [node2_x, data2], ...]
dic = {
1: [[2, 3], [4, 4]],
2: [[3, 2]],
3: [[5, 1]]
}
|
cs |
현재 노드가 부모 노드보다 x값이 크다면 부모의 max_right 값을 작다면 부모의 x값을 max_right로 가지게 된다.
코드는 다음과 같이 변경 되었다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
for Top, y in enumerate(sorted(dic, reverse=True)):
new_p = []
for n in sorted(dic[y]):
new_node = Node(n[0], n[1])
if Top == 0:
new_node.parent = root
new_node.max_right = root.max_right
root.children[0] = new_node
else:
for p_node in p:
# 현재 노드의 x가 부모 노드의 max_right 보다 크다면 해당 부모를 가질 수 없음
if p_node.max_right < new_node.x:
continue
# 아니라면 무조건 해당 부모의 자식 이므로 x 값을 비교하여
# 왼쪽 오른쪽 까지 결정
new_node.parent = p_node
if new_node.parent.x > new_node.x:
new_node.parent.children[0] = new_node
new_node.max_right = new_node.parent.x
else:
new_node.parent.children[1] = new_node
new_node.max_right = new_node.parent.max_right
break
new_p.append(new_node)
p = new_p
|
cs |
전체 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
from collections import deque
class Node:
def __init__(self, x, data):
self.parent = None
self.children = [None, None]
self.x = x
self.data = data
self.max_right = 100000
def solution(nodeinfo):
dic = {}
root = Node(0, 0)
# 노드 구성을 위한 dictionary 작업
for cnt, node in enumerate(nodeinfo):
node_x, node_y = node
dic[node_y] = dic.get(node_y, []) + [[node_x, cnt + 1]]
# 노드 구성
for Top, y in enumerate(sorted(dic, reverse=True)):
new_p = []
for n in sorted(dic[y]):
new_node = Node(n[0], n[1])
if Top == 0:
new_node.parent = root
new_node.max_right = root.max_right
root.children[0] = new_node
else:
for p_node in p:
if p_node.max_right < new_node.x:
continue
new_node.parent = p_node
if new_node.parent.x > new_node.x:
new_node.parent.children[0] = new_node
new_node.max_right = new_node.parent.x
else:
new_node.parent.children[1] = new_node
new_node.max_right = new_node.parent.max_right
break
new_p.append(new_node)
p = new_p
# 전위 탐색 가운데, 오른쪽, 왼쪽
now_node = root.children[0]
q = deque()
visited = set()
front = []
while True:
front.append(now_node.data)
visited.add(now_node.data)
left, right = now_node.children
if not left and not right and not q:
break
if right:
q.append(right)
if left and left.data not in visited:
now_node = left
else:
now_node = q.pop()
# 후위 탐색 왼쪽, 오른쪽, 가운데
now_node = root.children[0]
q = deque()
visited = set()
back = []
while True:
left, right = now_node.children
if (not left or left.data in visited) and (not right or right.data in visited):
back.append(now_node.data)
visited.add(now_node.data)
if q:
now_node = q.pop()
else:
break
elif left and left.data not in visited:
q.append(now_node)
now_node = left
elif right and right.data not in visited:
q.append(now_node)
now_node = right
return [front, back]
|
cs |
채점 결과
