구글 코드잼 2012-SR-C 문제 풀이
다이아몬드 상속 찾아내기 ----------------------------- ### 들어가며 평소 자주 보는 [Outsider][outsider]님을 통해 우연히 2012년 [구글 코드잼][codejam]에 참여했다. 코드잼 덕분에 오랜만에 코딩의 즐거움에 푹 빠져보기도 하고, 느려터진 코딩 속도에 자책도 하는 등 유익한 수련의 시간을 보냈다. 언제나 새로운 먹잇감을 찾아 헤매는(?) Outsider님에게 고마운 맘도 든다. 코드잼 문제가 매번 놀라울 정도로 다양한 스토리를 담고 있지만, 프로그램으로 옮기려고 문제를 분석해보면 유사한 형태의 문제들이 반복되는 것처럼 보인다[^1]. 대강 정리해보면 경우의 수(순열/조합), 경로 탐색 등의 알고리듬과 관련된 요소가 많은 듯하다. 코드잼의 여러 문제 중 그 중 경로 탐색을 재포장한 '다이아몬드 상속 판별하기'의 개인적 풀이를 소개한다. ### 문제 내용 물론 실제 문제는 좀 더 길고 구체적이지만 간단히 요약하면 다음과 같다. > 다중 상속이 가능한 언어에서 전체 클래스에 대한 클래스 다이어그램이 주어졌을 때, 다이아몬드 상속이 포함됐는지를 판별해보자. 더 자세한 내용이 궁금하면 [Codejam 2012 Round 1-C][codejam-src] 사이트를 참고한다. ### 접근 다음과 같은 다이아몬드 상속 관계를 살펴본 결과 몇몇 특징을 발견했다.  1. 우선 다이아몬드 상속 또한 미로 찾기 문제와 비슷하다고 볼 수 있다. 미로의 경우 벽이 없는 방향으로만 갈 수 있다. 클래스 다이어그램은 상속한 부모로만 진행이 가능한 미로와 같다. 2. 일반적으로, 자식 클래스 C에서 부모 클래스 P까지 상속을 거슬러 도달할 수 있는 경로가 2개 이상이면 다이아몬드 상속이다. 3. 다이아몬드 상속은 그림을 그리면 항상 닫힌 곡선을 만든다[^2]. 따라서 다이아몬드 상속을 위해서 모든 클래스를 연결해 볼 필요는 없으며, **부모가 2개 이상인 자식 클래스**와 **자식이 2개 이상인 부모 클래스**를 골라 이들의 연결 관계만 조사하면 된다. ### 목표 코드의 형태 경로의 진행은 자식에서 부모를 찾아가는 방향으로 이루어진다고 가정했다. #### 핵심 메서드의 모양(signature) 핵심 메서드인 pathFinder에 시작 클래스(자식)와 종료 클래스(부모)를 전달하면 접근 경로를 포함된 클래스의 List로 만들어 반환한다. 단, 경로가 2개 이상일 경우도 있으므로 최종 결과는 List의 List가 된다. def pathFinder(start: Claz, dest: Claz): List[List[Claz]] 여담으로 클래스 들의 상속 경로를 다음과 같이 ClazPath라 정의했다. type ClazPath = List[Claz] 이제 pathFinder 메서드는 다음과 같이 표현된다. def pathFinder(start: Claz, dest: Claz): List[ClazPath] #### 재귀 함수를 이용한 경로 탐색 경로 탐색 관련 알고리듬은 상당 수 존재한다. [위키피디아의 Tree Traversal][wiki-tt]을 참고하면 다수의 Graph/Tree 검색 알고리듬이 나온다. 여러가지 방법을 살펴보는 것은 물론 좋지만, 개인적으로 다른 알고리듬을 살펴보기 전에 문제를 충분히 고민해보길 권한다. 경로 찾기는 재귀 호출에 익숙하다면 비교적 쉽게 풀이를 생각할 수 있다. 갈림길이 있는 경로, 즉 부모가 두 개인 자식 클래스를 가정해보자.  갈림길 클래스 A에서 갈 수 있는 경로는 B와 C이다. 전체 경로는 B를 거쳐갈 수 있는 경로 + C를 거쳐갈 수 있는 경로의 합이다. List(A,B,D)를 A::List(B,D)과 같이 표현한다면[^3] 전체 경로는 다음과 같은 구문으로 표현된다. pathFinder(A,D) = List( A::pathFinder(B,D)(0), A::pathFinder(C,D)(0)) 같은 형태로 pathFinder를 재귀적으로 사용하면 전체 경로를 구할 수 있다. 목적지에 도달하지 못하고 끝난 경로는 최종 결과에서 제외시킨다. 참고로 만일 재귀가 성능의 저하 요인이 된다면 tail recursion이 가능한 형태로 변경할 계획이다. 문제를 재귀로 접근하는 사고 방법은 이전에 [순열 구하기][tistory-combination]를 통해 공유한 내용과 유사하다. ### pathFinder 1차 버전 작성한 pathFinder의 최초 버전은 다음과 같다. 리팩토링 여지가 다소 있지만 참고하기 바란다. 클래스의 상속관계 정보를 불러오면서 **부모가 2개 이상인 자식**을 출발점으로, **자식이 2개 이상인 부모**를 목적지로 하여 pathFinder를 이용해 경로를 구하고 2개 이상인지 조사하면 된다. type ClazPath = List[Claz] private def _pathFinder(start: Claz, dest: Claz): List[ClazPath] = { if (start.id == dest.id) return List(Nil) val parentIds: List[Int] = start.parentIds.toList parentIds match { case Nil => List(Nil) case list: List[Int] => { list.flatMap(id => { _pathFinder(clazzes(id), dest).map(clazzes(id):: _) }) } }} def pathFinder(start: Claz, dest: Claz): List[ClazPath] = { val paths:List[ClazPath] = _pathFinder(start,dest); paths.filter( (path) => path !=Nil && path.last.id == dest.id ) } ### 정리 개인적으로 알고리듬을 초반에 파악하고서도 손이 버벅대느라 시간을 낭비해서 아쉬움이 남는다. 간단하게 정리해보면 다음과 같다. * 코딩 수련을 제대로 하지 않았다. - 작은 코드만 작성하고, 책 내용만 보기에 급급했던 결과가 아닐까. - 시간 관리가 필요하다. - 코딩을 하며 손이 버벅되는 건 정말 반성 좀 해야겠다. * 문제 해결 능력은 약간 성장했을지도 모르겠다. - 높은 배점의 문제도 프로그래밍 가능한 형태로 분석하는 건 그렇게 오래 걸리지 않았다. - Scala 등의 몇몇 언어를 통해 프로그래밍 접근이 다양해졌다[^4]. [^1]: 하지만 **코드잼 대선배**인 [blmarket][blmarket-tweet]님은 내가 처음 참여했고 초반만 맛봐서 그렇다 하신다. 좀 더 다양한 문제가 있다는 격언을 남기셨다. [^2]: 주어진 그림에서 1-2-3-5-4-1을 연결하면 닫힌 곡선이 된다. [^3]: ::는 cons 연산자이다. [^4]: Scala는 여러 패러다임 언어들의 특징을 적절히 배합한 Hybrid 언어라 다양한 개념을 다루고 있다. 시간 제한으로 구현에 미치지 못한 내용이 많지만, 다양한 접근 방법을 고려하는데 도움이 됐다. [outsider]: http://blog.outsider.ne.kr [tistory-combination]: http://nephilim.tistory.com/135 [blmarket-tweet]: http://twitter.com/#!/blmarket [codejam]:http://code.google.com/codejam [codejam-src]:http://code.google.com/codejam/contest/1781488/dashboard [wiki-tt]:http://en.wikipedia.org/wiki/Tree_traversal