Snake Traverse 문제

2006년도에 Microsoft 본사 면접을 봤을 때 두번째로 면접볼때 풀었던 문제다. 화이트보드에 직접 코드를 작성하기란 여간 까다로운게 아니어서 15분만에 풀었어야 하는 문제를 30분정도 걸렸던것 같다. 다행히도 면접을 봤던 Diago(현재는 구글 Japan에 근무)가 친절하게 기다려줘서 clear했던 문제. 그런데 이 문제가 구글이나 MS와 같은 IT 기업의 문제 은행으로 등록되어 있다니. 그땐 사전에 미리 공부도 하지 못해서 "뭐 이런 문제를 내지?"라고 생각했었는데, 오늘 우연히 발견하게 되어서 간단하게 풀어보았다. 머리도 식힐겸~

문제의 요구 사항은 NxN 배열이 있을 때 해당 배열의 각 항목을 뱀 꼬리를 잡듯이 하나씩 출력하는 문제다.

영어로 설명하자면, 이렇다.

Given a 2-d array, write code to print it out in a snake pattern. For example, if the array is this:
1, 2, 3
4, 5, 6
7, 8, 9
the routine prints this:
1,2,3,6,9,8,7,4,5

The array is an NxN array.

편의상 Python으로 작성했다. 주석이나 이런저런 코드를 빼면 20줄 내외로 작성 가능하다. 생각한 방안은 진행 방향을 고려해서 x와 y의 증가(또는 증감)을 자동으로 계산되도록 한다. 그리고 이 순환이 끝날 수 있도록 min과 max 값을 잘 조절하는게 핵심. 더 좋은 방법이 있을 수 있고, 이게 최선은 아닐 수도 있습니다.

# -*- coding: utf-8 -*-

class SnakeTraverse:
    def __init__(self, dim, tables):
        self.dim = dim
        self.tables = tables

    def traverse(self):
        # 스네이크 traverse를 하기 위해서는 x와 y 좌표를 통해 방향을 지정한다.
        # 0 --> 오른쪽으로, 1 --> 아래로, 2 --> 왼쪽으로, 3 --> 위쪽으로
        switch = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        switch_type = 0

        # 한번의 traverse가 끝나면 다음 시작 좌표를 조절한다.
        adjust_to_next_point = [[-1, 1], [-1, -1], [1, -1], [1, 1]]

        x = 0
        y = 0
        min_x = 0
        max_x = self.dim - 1
        min_y = 0
        max_y = self.dim - 1

        while True:
            # x와 y의 최소값과 최대값을 변경하여 해당 좌표안에서만 탐색하도록 한다.
            while ((min_x <= x <= max_x) and (min_y <= y <= max_y)):
                # 현재 좌표의 값을 찍고
                print str(x) + ", " + str(y) + " ==> " + str(self.tables[y][x])

                # 다음 좌표로 이동
                x = x + switch[switch_type][0]
                y = y + switch[switch_type][1]

            # 모든 위치가 탐색될 때 끝난다.
            if min_x > max_x or min_y > max_y:
                break;

            # 다음 순환을 위해 좌표를 보정한다.
            x = x + adjust_to_next_point[switch_type][0]
            y = y + adjust_to_next_point[switch_type][1]

            # 방향에 따라서 x와 y 값의 최대값과 최소값을 변경한다.
            if switch_type is 0:
                min_y = min_y + 1
            elif switch_type is 1:
                max_x = max_x - 1
            elif switch_type is 2:
                max_y = max_y - 1
            else:
                min_x = min_x + 1

            # 방향을 바꾼다.
            switch_type = (switch_type + 1) % 4

if __name__ == "__main__":
    tables_3 = [[0,1,2], [3,4,5], [6,7,8]]
    tables_4 = [[0,1,2,3],[4,5,6,7],[8,9,10,11],[12,13,14,15]]

    traverse = SnakeTraverse(3, tables_3)
    traverse.traverse()

    traverse = SnakeTraverse(4, tables_4)
    traverse.traverse()