23.03.23 TIL: 프로그래머스150367,169199

최창수·2023년 3월 23일
BFSDFSpython스파르타코딩클럽코딩테스트
0

문제: 표현가능한 이진트리(150367)와 리코쳇 로봇(169199)

학습 목표

  • 코딩 테스트 문제를 읽고 문제의 조건과 제한사항을 올바르게 이해한다.
  • 재귀형 코드와 반복형 코드의 작성법 차이와 장단을 안다.

문제1: 표현가능한 이진트리

각 10진수 수 마다 2진수로 표현했을 때 1과 0의 나열이 포화 이진 트리(node 개수가 2^n - 1개)를 중위순회(L-root-R)한 결과이고, 0은 해당 노드가 존재하지 않음을, 1은 해당 노드가 존재함을 의미한다는 규칙을 세운다.
예를들어 15는 '0001111'이므로 다음과 같은 형상의 트리를 의미한다.

5('101')는 다음과 같은 형상으로, 존재할 수 없는 트리이다.(연결되어 있지 않은 node 존재)

입출력 및 제한

10진수 int들의 list가 주어진다. 각 list의 int들이 존재가능한 이진트리를 나타내는지, 그렇지 않은지 에 따라 1,0을 저장한 list를 반환해야한다.

numbersresult
[7, 42, 5][1, 1, 0]
[63, 111, 95][1, 1, 0]

numbers는 1만개 이하의 요소를 포함한다.
numbers의 각 요소는 1 이상, 1e+15 이하이다.

시도

공통: 포화 이진 트리에 대한 이해를 통한 접근

  1. 이진트리를 하나의 줄로 표현하는 방식에는 전위순회, 후위순회, 중위순회가 있다. 왼쪽 하위트리와 오른쪽 하위트리, 그리고 root를 어떤 순서로 조회하느냐에 따른 분류이다. 각각을 그림으로 나타내면 다음과 같다.(위에서 부터 전 중 후)

    문제에서 판단해야할 것은 트리 전체를 보았을 때, 연결되지 않은 node가 존재하는지 살펴보고 존재하면 0, 존재하지 않다면 1을 출력하는 것이다.
  2. 포화 이진트리라 함은 leaf가 아닌 모든 node에 양쪽 자식이 모두 달려있고, 양쪽 subtree의 depth가 같은 것을 의미한다. 이는 중위 순회 결과를 정확히 root를 중심으로 같은 길이의 list로 나눌 수 있다는 성질을 만든다.

따라서 우리는 int를 길이 3,7,15,... 짜리의 0과 1로 이루어진 list로 표현할 것이며 이를 위해 적절하게 zero padding을 앞쪽에 붙여준다.

def sol(numbers):
    answer = []
    for num in numbers: # 각 int마다 실행
        b = []
        digit = 0
        full_digit = 1
        growth = 2
        while num != 0: # 2진수로 변환하기
            b = [num % 2]+b
            num = num//2
            digit += 1
            if digit > full_digit:
                full_digit += growth
                growth *= 
        if digit < full_digit:  # 패딩 붙이기
            padding = [0 for i in range(full_digit-digit)]
            b = padding+b
        answer.append(0 if is_orphan(b)[0] else 1)# 트리에 연결되지 않은 노드가 있는지 확인![](https://velog.velcdn.com/images/97ckdtn/post/501c4979-cc1e-443c-be92-50851c13617e/image.JPG)

    return answer

1. 재귀함수로 탐색

이진 트리의 root는 오른쪽 왼쪽에 하나씩, 혹은 한쪽에 sub tree를 자식으로 가지며, 이 자식 tree에도 root가 있는 형태이므로 재귀적인 형태이다. 따라서 중위 순회로 표현된 tree를, 재귀적인 방식으로 탐색해 연결되지 않은 노드, 즉 부모 node가 0으로 표현되는 동시에 자신은 1로 표현되는 경우(앞으로 이를 고아 node라고 한다)를 찾는 함수를 만들 수 있다.

def is_orphan(bit_list):
	mid=len(bit_list)//2

재귀함수는 일단 십진수를 이진수로 바꾼 list를 중위순회의 결과로서 가져온다. 포화 이진트리를 가정하므로 언제나 길이//2의 위치에 root가 존재한다.

    
    if len(bit_list) == 3:
        if not (any(bit_list)):
            return (False,False)
        if not bit_list[1]:
            return (True,False)
        return (False,True)

초기식: bit-list를 root 기준으로 계속 좌우로 나누며 재귀함수를 호출하다보면 길이가 3일 때가 올 것이다. 이때는 더이상 재귀함수를 호출하지 않고 고아(부모없이 존재하는 node)의 존재를 확인하고 고아 존재 여부와 root의 존재 여부를 tuple로 반환한다.

   left_orphan, left_root = is_orphan(bit_list[:mid])
   right_orphan,right_root = is_orphan(bit_list[mid+1:])
   if left_orphan or right_orphan:
       if bit_list[mid]:
           return (True,True)
       else:
           return(True,False)

점화: bit-list(주어진 sub-tree)에서 왼쪽 subtree와 오른쪽 sub-tree의 고아 유무 여부와 root 유무 여부를 확인하기위해 재귀함수를 호출한다. 만약 둘중 한쪽이라도 고아가 있다면, 자신의 root의 존재 여부와 함께 반환한다.

    if not (left_root or right_root or bit_list[mid]):
        return(False, False)
    if not bit_list[mid]:
        return(True,False)
    return (False, True)

만약 둘중 고아가 없다면, 이번에는 자기 자신과 left-subtree, right-subtree가 잘 연결되어있는지 확인한다. 자신의 root, 왼쪽 subtree의 root, 오른쪽 subtree의 root가 모두 비어있다면, 이 단계에서 부모node가 없는 고아는 없으므로 반환한다.
셋중 하나이상 node가 존재하는데 부모가 될 root가 없다면 이는 고아가 존재함이므로 고아있음, 부모 없음을 반환한다.
이외의 경우엔 부모가 될 root가 존재함이므로 정반대로 반환한다.

문제점 봉착: 재귀한계와 시간초과

이 재귀함수는 내 pc 환경에서는 정상작동하였으나 제출하자 런타임 에러가 발생하였다. 이는 python의 재귀한계 설정에 의한 것으로 보통 1천회 이상 재귀가 발생하면 더이상 실행하지 않고 에러를 출력하도록 한다고 한다.

문제 해결 시도: 재귀한계 늘리기-시간초과로 실패

sys모듈을 불러와 다음과 같이 설정하면 재귀한계를 늘릴 수 있으므로 적용해 보았다.

import sys
sys.setrecursionlimit(100000)

그러나 이를 적용해도 시간초과로 인해 해결이 실패하였다. 이는 여러번 재귀를 호출하며 메모리에 접근하는 횟수가 늘어났기 때문으로 보인다(over head). 보다 근본적인 해결을 위해 반복문을 사용하기로 하였다.

시도 2. 반복문 사용

개념상 재귀형 코드를 적용하는 것이 더 직관적인 이진 트리를 어떻게 반복문을 사용하며 모든 노드를 빠짐 없이 조회하여 고아 node를 찾아낼까 고민해보았다.

2-1. 중위 순회 결과를 전/후위 순회로 바꾸기

특히 전위 순회로 바꾸면 root가 앞으로 오고, left subtree의 root는 bit_list[1]에, right subtree의 root는 bit_list[len(bit_list)//2 + 1]에 오므로 더 쉽게 조회가 가능할 거라고 생각했다.
그러나 근본적으로 반복문을 1회 실행할 때마다 sub list가 2개씩 생기는건 동일하므로 단순히 형식을 바꾼다고 해결되지는 않는다.

2-2. '한 층 씩' 조회하기

고민끝에 다음과 같이 하기로 했다.

def is_orphan(bit_list):
    sub_lists = [bit_list]
    while len(sub_lists[0]) != 1:

먼저 bit_list를 요소로 가지는 list(sub_lists) 하나를 만든다.
이후 반복문을 돌린다.

        temp = []
        for sub_list in sub_lists:
            mid = len(sub_list)//2
            l_root = sub_list[mid//2]
            r_root = sub_list[mid + 1 + mid//2]

sub_lists에 대한 반복문을 한번 더 돌린다. 이전(재귀형 코드)과 마찬가지로 subtree를 표현하는 list 길이를 기준으로 subtree의 root, left-subtree root, right-subtree root를 찾을 수 있다.

         
            if (not sub_list[mid]) and (l_root or r_root):
                return True

sub_lists속 list들에서 고아 유무를 판별한다. 반복문 안에서 고아가 발견되면 즉시 반환하고, 

            temp.append(sub_list[:mid])
            temp.append(sub_list[mid+1:])
        sub_lists = temp[:]
    return False

아니면 sub_list를 root 위치를 기준으로 둘로 나누어(left subtree, right subtree) 새로운 list 하나에 append한다.
이후 for문이 끝나면 sub_lists를 쪼개진 sublist들로 갱신하고 다시 while문을 시작한다. sub_lists의 요소의 길이가 1이 되면(subtree의 node 갯수가 1개가 되면)더이상 탐색을 진행할 필요가 없으므로 종료하고 이때까지 고아가 없었다면 False를 반환한다.
반복문을 사용한 코드의 경우 모든 테스트케이스들을 성공적으로 통과하였다.

그러나 반복문을 2번 돌리는 것은 간결하지 못하며, 더 나은 탐색 방법이 있을 것이라 생각하여 DFS와 BFS를 응용해보기로 했다.

문제2: 리코쳇 로봇

BFS를 이용하는 문제이다. 격자모양의 게임판이 주어진다.
게임판에서 .은 빈공간, D는 벽, R은 시작할때의 로봇의 위치, G는 도착하면 승리하는 목표지점이다.
로봇은 상하좌우로 이동하며 벽이나 게임판 경계에 닿을 때 까지 쭉 미끄러진다.
로봇이 G에 도달하기 까지의 최단 이동횟수를 반환해야 한다. 영원히 도달하지 못할 시 -1을 반환한다.

위와 같은 경우 총 7번 만에 G에 도달가능하다.

시도 및 해결 : BFS

BFS는 broad first search로, edge에 가중치가 없는 graph에서 한 상태에서 다른 상태로의 이동횟수가 가장 적은 경로를 찾기위해 tree형태로 graph를 재해석하여 한층한층 탐색하는 알고리즘이다.
해답 일부를 보면 다음과 같이 작동한다.

start_node = Node(start_state, [])
    next_nodes = [start_node]
    visited = []

Node 객체에는 위치와 시작지점부터 그 위치까지의 경로가 저장되어있다. queue(선입선출형태) 형태로 쓸 list 하나와, set처럼 쓸 visited list를 쓴다.

    while next_nodes:
        new_node = next_nodes.pop(0)
        if new_node.location == the_map.goal:
            return len(new_node.path)
        if new_node.location in visited:
            continue

next_node에서 가장 첫번째 Node하나를 pop(리스트에서 삭제, 반환)하고 goal 위치와 일치하는지 확인한다. 그리고 이미 방문했던 지점인지 한번 확인한다. 게임에서 가능한 상태들의 graph는 tree가 아니며 cycle이 있을 수 있으므로 visited를 통해 사이클을 방지해 트리처럼 다룰 수 있다.

        visited.append(new_node.location)
        new_next_nodes = the_map.gen_next_node(new_node)
        for n in new_next_nodes:
            if n.location in visited:
                continue
            next_nodes.append(n)
    return -1

visited에 현재 node의 위치를 넣고, 현재 위치(노드)에서 도달가능한 다음 위치(노드)들을 생성한다. 이때 새 노드들의 path는 현재 노드의 path+새 위치 이다. 만약 새로 생성된 위치들이 이미 방문한 곳일면 next_nodes에 해당 위치의 노드는 추가하지 않고 넘어가며 next_nodes에 이어붙인다.

이 반복문을 if new_node.location == the_map.goal:이 실행될 때 까지, 혹은 더이상 방문하지 않은 곳이 없어 움직일 데가 없을 때 까지next_nodes==[] 실행한다.
이렇게 하면 다음과 같은 순서로 탐색이 진행된다.

BFS 이외의 다른 부분(다음에 도달할 수 있는 상태-노드 목록 만들기 등)은 다음과 같이 Board 클래스 내에 만들었다.

class Board():
    def __init__(self, board_) -> None:
        self.grid = board_
        self.walls = []
        for i, row in enumerate(board_):
            for j, point in enumerate(row):
                if point == 'D':
                    self.walls.append([i, j])
                elif point == 'G':
                    self.goal = [i, j]
                elif point == 'R':
                    self.start = [i, j]
                else:
                    False

인스턴스가 생성됨과 동시에 벽 정보와 goal정보를 따로 저장해둔다.

    def iswall(self, location: list) -> bool:
        if location in self.walls:
            return True
        if location[0] in [-1, len(self.grid)]:
            return True
        if location[1] in [-1, len(self.grid[0])]:
            return True
        return False

로봇이 이동한 위치가 벽이거나, 보드판 밖인지 확인하는 함수이다.

    def gen_next_node(self, node: Node):
        next_nodes = []
        for direction in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
            next_loc = node.location[:]
            while not self.iswall(next_loc):
                next_loc[0] += direction[0]
                next_loc[1] += direction[1]
            next_loc[0] -= direction[0]
            next_loc[1] -= direction[1]
            next_nodes.append(Node(next_loc, node.path+[next_loc]))
        return next_nodes

한 상태(위치)에서 이동했을 때 가능한 상태(위치) 들을 생성하고 Node형태로 경로와 함께 저장해 반환한다.
가능한 상태는 4방향 중 한 방향으로 이동했을 때 벽이나 보드판 경계 직전의 위치이므로 반복문을 통해 그 전까지 쭉 이동하는 것을 구현했다.

문제 1로 돌아오기: BFS 적용, DFS로 변형해보기

BFS

문제1 에서 반복문 버전 is_orphan()은 while문과 for문 두개를 통해 순차적으로 tree의 모든 계층을 탐색하였다. 이는 기능적으로는 BFS와 다르지 않으며, BFS와 같이 queue를 사용해 while문만으로 같은 기능을 수행하게 할 수 있다.

def is_orphan(bit_list):
    sub_lists = [bit_list]
    while len(sub_lists[0]) != 1:
        sub_list = sub_lists.pop(0)
        mid = len(sub_list)//2
        l_root = int(sub_list[mid//2])
        r_root = int(sub_list[mid + 1 + mid//2])
        if (not int(sub_list[mid])) and (l_root or r_root):
            return True
        sub_lists.append(sub_list[:mid])
        sub_lists.append(sub_list[mid+1:])
    return False

sub_lists는 리코쳇 로봇에서 next_nodes 처럼 앞으로 탐사해야할 노드들을 담는 queue의 역할을 한다. 또한 탐색할 graph가 tree형태이므로 visited list는 필요없다.
gen_next_node의 역할은 subtree의 root를 len(sub_list)를 통해 찾아내는 것으로 대신한다.
goal check는 해당 노드가 존재하지 않고 해당 노드의 subtree의 root들이 존재하는지 체크하는 것이 대신한다.
이렇게 하여 더 간결하게 tree를 탐색하는 코드를 만들 수 있었다.

DFS(깊이 우선 탐색)

깊이 우선 탐색은 BFS와 달리 Queue 대신 Stack 자료형(선입-후출)을 사용한다. 이렇게 하면 가장 최근에 조회한 노드의 자식 노드를 가장 먼저 조회하는 식이 되어 leaf 노드까지 빠르게 훑고 다시 돌아오는 식으로 탐색한다.
BFS로 작성한 코드를 DFS로 변경하는것은 매우 간단하다. queue만 stack으로 바꾼다.

sub_lists = [sub_list[:mid], sub_list[mid+1:]]+sub_lists

둘의 장단점 비교

BFS는 무조건 가장 가까운 고아(goal)을 찾는다. 만약 고아 노드가 leaf가까이에 있다면 DFS에 비해 느리다.
DFS는 BFS와 달리 가장 가까운 고아(goal)노드를 찾는다는 보장이 없으나, 고아노드가 leaf 가까이에 있다면 비교적 빠를 수 있다.

실재 실행시간비교

컴퓨터의 CPU성능이 좋지않아 정확한 비교가 힘든 관계로 추후 실행 예정

배운점

  • BFS와 DFS를 복습
  • 재귀형 코드는 직관적이나 오버헤드와 메모리 문제가 존재한다.
  • DFS와 BFS를 이진tree에도 쉽게 적용할 수 있다.
  • 꼬리 재귀 함수: 재귀호출한 함수가 호출 과 동시에 return되어 아무것도 하지 않아도 되는 재귀함수로, 자동적으로 반복문형태로 최적화 되기 때문에 재귀형 코드의 고질적인 오버헤드와 메모리 문제를 해결할 수 있다.

추가 학습 필요

  • 꼬리 재귀함수를 이용해보기
profile
최창수
Hallow Word!
이전 포스트

23.03.22 TIL

다음 포스트

23.03.24 TIL

0개의 댓글