카카오 : 길찾기 게임 — 파이썬: 2019 BLIND TEST 문제 풀이

“괜찮아! 아직 코딩테스트까지 3일이나 남았어” 프로젝트 (4)

2019 카카오 블라인드 테스트

1. 오픈채팅방
2. 실패율
3. 후보키
4. 무지의 먹방 라이브
5. 길찾기 게임
6. 매칭점수
7. 블록 게임

공식해설

2019 카카오 신입 공채 1차 코딩 테스트 문제 해설

문제

코딩테스트 연습 - 길 찾기 게임

문제 분해

• 우선 주어진 자료 → 트리로 표현
• 차수 별로 나누기
• 높은 차수, 낮은 차수 노드랑 연결
• 전위 순회, 후위 순회

자료표현

• 트리 → 연결리스트로 표현

일반화

트리 구현을 재귀적으로 수행

공식 해설

각 노드의 오른쪽 자식 노드는 다음과 같이 찾을 수 잇습니다.

먼저 현재 노드 P의 x 값을 Px, 현재 노드의 자식 노드가 가질 수 있는 x 범위를 Lx, Rx(Lx < Px < Rx)라고 하겠습니다. 또 어떤 노드 K의 x 값을 Kx라고 하겠습니다. K는 노드 P의 왼쪽 자식이 됩니다. 이때, 노드 K의 자식 노드가 가질 수 있는 x 값의 범위는 Lx ≤ x ≤ Px-1(x != Kx) 가 됩니다.

마찬가지로 현재 노드의 바로 다음 레벨에 Px ≤ Kx ≤ Rx를 만족하는 노드 K가 있다면, K는 노드 P의 오른족 자식이 되며, 노드 K의 자식 노드가 가질 수 있는 x의 범위는 Px+1≤ x ≤ Rx(x!=Kz)가 욉니다.

이 과정을 재귀적으로 반복하면서 각 노드의 왼쪽, 오른쪽 자식을 찾아주면 트리를 구성할 수 있습니다.

노드별 왼쪽, 오른쪽 자식을 찾는 방법 중 하나로, 재귀적으로 순회하며, 트리를 만들면 같은 level의 노드는 x 값이 작은 노드부터 방문하게 되므로, 큐를 트리의 레벨 만큼 만들어 두고, x 축 기준으로 오름차순 정렬된 노드들을 y축 값이 같은 노드끼리 각 큐에 넣어두면 큐의 front를 확인하는 방법으로 O(1)에 찾을수 있습니다.

구현

개념

• 전위 순회: 뿌리(root)를 먼저 방문
• 중위 순회: 왼쪽 하위 트리를 방문 후 뿌리(root)를 방문
• 후위 순회: 하위 트리를 모두 방문 후 뿌리(root)를 방문