카카오 블라인드 채용

[카카오] 2019 KAKAO BLIND RECRUITMENT 1차 풀이 – 길 찾기 게임

이 포스팅에서는 2019 카카오 블라인드 채용 1차 문제인 ‘오픈채팅방’ 문제를 해설합니다. 본 풀이에 대한 테스트는 https://programmers.co.kr/learn/courses/30/lessons/42892에서 수행하였으며 공식 풀이와 일치하지 않을 수 있습니다.

공식 풀이는 링크를 참조하시기 바랍니다.


길찾기 게임

출처 : 2019 KAKAO 블라인드 채용 온라인 1차
링크 : https://programmers.co.kr/learn/courses/30/lessons/42892
카테고리 : Graph, DFS, BFS
난이도 : 보통


문제 설명

노드들의 (x, y) 좌표들이 주어진다. 가장 y 값이 큰 것이 root가 되고 그 아래로 자식들이 나열된다. 부모 노드의 왼쪽 자식은 항상 부모보다 작은 x값을 가지고, 부모 노드의 오른쪽 자식은 항상 부모보다 큰 x값을 가진다. 동일한 LEVEL은 같은 y 값을 가진다.

주어진 노드로부터 그래프를 구성할 때 이 그래프를 DFS, BFS로 각각 탐색한 결과를 출력하여라.


문제 풀이

y값에 따라 각 노드를 level 별로 분류한 후 내림차순 정렬한다.

모든 노드는 [부모, 왼쪽 자식, 오른쪽 자식, 왼쪽 경계, 오른쪽 경계]의 값을 가진다. 가장 처음에는 [-1, -1, -1, -1, MAX + 1]로 초기화한다.

각 LEVEL을 탐색하면서 다음 LEVEL의 노드들에 대해 자신의 자식이 될 수 있는지를 살핀다. 왼쪽 자식이 되기 위해서는 (왼쪽 경계, 자신)의 범위에 노드가 있어야하고, 오른쪽 자식이 되기 위해서는 (자신, 오른쪽 경계)의 범위에 있어야한다.

노드는 부모와 그 모든 부모 노드들에 대해 영역 범위를 만족시켜야 하기 때문에, 부모 노드의 경계 범위는 자식 노드에게도 그대로 적용되어야 한다. 즉, 자식 노드는 (부모의 왼쪽 경계, 부모 노드의 위치) 또는 (부모 노드의 위치, 부모의 오른쪽 경계)의 경계 범위를 갖게 된다.

만들어진 그래프에 대해 DFS, BFS를 수행한 결과를 출력한다.


정답 코드

import sys
x = 10000
sys.setrecursionlimit(x)
# Parent가 없는 노드가 Root다.
def get_root(graph):
for i in range(len(graph)):
if graph[i][0] == 1:
return i
# DFS
def dfs(cur, graph):
ret = [cur + 1]
if graph[cur][1] != 1:
ret += dfs(graph[cur][1], graph)
if graph[cur][2] != 1:
ret += dfs(graph[cur][2], graph)
return ret
# BFS
def bfs(cur, graph):
ret = []
if graph[cur][1] != 1:
ret += bfs(graph[cur][1], graph)
if graph[cur][2] != 1:
ret += bfs(graph[cur][2], graph)
return ret + [cur + 1]
def solution(nodeinfo):
nodes = {}
graph = []
# 각 노드에 대해 [Parent, Left Child, Right Child, Left boundary, Right boundary]
# 각 Boundary는 노드의 child가 가질 수 있는 x의 범위를 규정한다.
# Parent A를 갖는 노드 B가 Child C를 가질 때, C의 x가 parent를 넘어가선 안되기 때문이다.
for i in range(len(nodeinfo)):
x, y = nodeinfo[i]
graph.append([1, 1, 1, 1, 10000000])
if y not in nodes:
nodes[y] = []
# 같은 레벨의 노드는 같은 y를 가지므로, 같은 y를 가지는 것끼리 묶는다.
nodes[y].append([x, i])
# y가 클수록 레벨이 낮으므로, y역순으로 다음 레벨에서 child를 찾는다.
y_list = list(nodes.keys())
y_list.sort(reverse=True)
for y in y_list:
nodes[y].sort()
for i in range(len(y_list) 1):
y = y_list[i]
# 다음 레벨의 노드들을 탐색하는데 쓸 인덱스
k = 0
# 현재 레벨의 노드들에 대해
for j in range(len(nodes[y])):
cur = nodes[y][j]
next_y = y_list[i + 1]
# 다음 레벨의 child 후보들에 대해
while k < len(nodes[next_y]):
child_candidate = nodes[next_y][k]
# 왼쪽 child가 가능한지
# 현재 노드보다 왼쪽에 있고, 노드의 left boundary 보다는 오른쪽
if cur[0] > child_candidate[0] and graph[cur[1]][3] < child_candidate[0]:
graph[cur[1]][1] = child_candidate[1]
graph[child_candidate[1]][0] = cur[1]
graph[child_candidate[1]][3] = graph[cur[1]][3]
graph[child_candidate[1]][4] = cur[0]
k += 1
# 현재 노드보다 오른쪽에 있고, 노드의 right boundary 보다는 왼쪽
elif cur[0] < child_candidate[0] and graph[cur[1]][4] > child_candidate[0]:
graph[cur[1]][2] = child_candidate[1]
graph[child_candidate[1]][0] = cur[1]
graph[child_candidate[1]][3] = cur[0]
graph[child_candidate[1]][4] = graph[cur[1]][4]
k += 1
else:
break
# dfs, bfs 결과를 출력
return ([dfs(get_root(graph), graph), bfs(get_root(graph), graph)])
cs

Competition 카카오 블라인드 채용 길 찾기 게임

admin

Recent Posts

2024년 11월 3일 일요일 – 서울 생활 127주차

반복적인 일상 매일 아침 일어나 회사에 출근하고, 저녁을 먹고 돌아오는 일상의 반복이다. 주말은 가족을 보러…

2일 ago

2024년 10월 6일 일요일 – 서울 생활 123주차

Planning A well-structured plan has the following characteristics:   First, the ultimate vision you aim to…

1개월 ago

2024년 9월 29일 일요일 – 서울 생활 122주차

English The most common problem for English learners like myself is that we often use…

1개월 ago

2024년 9월 22일 일요일 – 서울 생활 121주차

추석 추석을 맞아 친가 외가 처가 어르신들을 모두 뵙고 돌아왔다. 아이가 태어난지는 좀 됐지만 한국에서…

1개월 ago

2024년 9월 8일 일요일 – 서울 생활 119주차

주말 이번주는 아내가 올라와서 주말을 함께 보냈다. 둘만 밥도 먹고 뮤지컬도 보고, 모임도 나가고 집에서…

2개월 ago

2024년 9월 1일 일요일 – 서울 생활 118주차

여행 지난주에 코로나에 걸리는 바람에 근 3주만에 가족을 만나고 왔다. 집에 있어봐야 시간도 안가고 할…

2개월 ago

This website uses cookies.