Spiral Array

문제는 다음과 같다:

6 6

  0   1   2   3   4   5
 19  20  21  22  23   6
 18  31  32  33  24   7
 17  30  35  34  25   8
 16  29  28  27  26   9
 15  14  13  12  11  10

위처럼 6 6이라는 입력을 주면 6 X 6 매트릭스에 나선형 회전을 한 값을 출력해야 한다.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

45개의 풀이가 있습니다. 1 / 5 Page

파이썬3.4

되도록이면 if문이나 좌표값을 쓰지 않도록 노력했습니다.

from itertools import cycle

def spiral(m, n):
    """나선형 매트릭스를 일차원 배열형태로 반환
    >>>spiral(3, 3) #3x3
    [0, 1, 2, 7, 8, 3, 6, 5, 4]
    #[0, 1, 2,
    # 7, 8, 3,
    # 6, 5, 4]
    """
    size = m * n
    matrix = [''] * size #['', '', '', ... '']
    matrix[:m] = list(range(m)) #m=3인경우 [0, 1, 2, '', '', ... ]
    idx = m - 1; s = idx; p = idx
    pattern = [m, -1, -m, 1] #아래, 왼쪽, 위, 오른쪽
    for pat in cycle(pattern): #패턴을 반복
        while True:
            p += pat; s += 1
            if p < size and matrix[p] == '': #size를 넘지않고, 값이 비어있는경우
                matrix[p] = s
            else:
                p -= pat; s -= 1 #복원
                break #다음 패턴으로
        if '' not in matrix: #모두 숫자로 채워지면
            return matrix

def main(m, n):
    for i, a in enumerate(spiral(m, n), 1):
        print('{:2d}'.format(a), end=' ')
        if i % m == 0:
            print()

main(6, 6)
# 0  1  2  3  4  5 
#19 20 21 22 23  6 
#18 31 32 33 24  7 
#17 30 35 34 25  8 
#16 29 28 27 26  9 
#15 14 13 12 11 10

'''
3x3의 나선형 매트릭스 모양은,
0 1 2
7 8 3
6 5 4
위와 같다. 이것을 2차원 리스트로 표현하면,
[ [0, 1, 2],
  [7, 8, 3],
  [6, 5, 4] ]
위와 같다. 반면 일차원 리스트로 펼쳐보면,
인덱스:  0  1  2  3  4  5  6  7  8
리스트: [0, 1, 2, 7, 8, 3, 6, 5, 4]
위와 같다. 리스트의 값 순서대로 인덱스를 정렬해보면,
인덱스:  0  1  2  5  8  7  6  3  4 
리스트: [0, 1, 2, 3, 4, 5, 6, 7, 8] 이다.
0, 1, 2를 제외한 나머지의 인덱스 패턴을 보면,
(나선형 매트릭스는 오른쪽, 아래, 왼쪽, 위, 오른쪽, ... 주기가 있다)
2  5 (+3) 아래 
5  8 (+3) 아래
8  7 (-1) 왼쪽
7  6 (-1) 왼쪽
6  3 (-3) 위
3  4 (+1) 오른쪽
위를 토대로 spiral(3, 3)이 그리는 상황을 따라가보면,
['', '', '', '', '', '', '', '', ''] #matrix = [''] * size
[0, 1, 2, '', '' ,'', '', '', ''] #matrix[:m] = list(range(m))
[0, 1, 2, '', '', 3, '', '', ''] #pattern +3
[0, 1, 2, '', '', 3, '', '', 4] #pattern +3
[0, 1, 2, '', '', 3, '', 5, 4] #pattern -1
[0, 1, 2, '', '', 3, 6, 5, 4] #pattern -1
[0, 1, 2, 7, '', 3, 6, 5, 4] #pattern -3
[0, 1, 2, 7, 8, 3, 6, 5, 4] #pattern +1
'''
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

X,Y = 10,6

# 초기화
go = 1
x,y = 0,0
min_x, min_y, max_x, max_y = 0 , 0, X-1, Y-1
result = [[-1 for i in range(0,X)] for j in range(0,Y)]

for i in range(0,X*Y):
    result[y][x] = i

    # 방향 지정
    if x == max_x and go == 1 :
        go = 2
    elif y == max_y and go == 2 :
        go = 3
    elif x == min_x and go == 3:
        go = 4

        # 증가 범위 재설정
        min_y += 1
        min_x += 1
        max_x -= 1
        max_y -= 1
    elif y == min_y and go == 4:
        go = 1

    # 배열위치값 증감
    if go == 1:
        x += 1
    elif go == 2:
        y += 1
    elif go == 3:
        x -= 1
    elif go == 4:
        y -= 1

# 출력
for row in result:
    for chk in row:
        print '%3d'%chk,
    print


초기화와 출력은 다른분 소스를 참고하고 스파이럴 배열 입력부분은 각 끝자리의 위치값을 셋팅하고 한바퀴돌때마다 끝자리 위치값이 하나씩 줄어들면 가능하다고 보고 구현

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

파이선으로 변수선언 말고는 한줄코드 추가합니다.

w = 6
h = 9
Margin = lambda x, half: half - abs(half - x - 0.5) - 0.5
MinMargin = lambda x, y: min(Margin(x, w / 2.0), Margin(y, h / 2.0))
StartBase = lambda x: (w * h) - ((w - x * 2) * (h - x * 2))
Offset1 = lambda x, y, m:(x - m, y - m, w - m * 2, h - m * 2)
Offset2 = lambda x: x[0] + x[1] if x[1] == 0 or x[0] == (x[2] - 1) else (x[2] * 2 + x[3] * 2 - 4) - (x[0] + x[1])

print '\n'.join([''.join(['%4d' % m for m in [Offset2(Offset1(x, y, MinMargin(x, y))) + StartBase(MinMargin(x, y)) for y in range(h) for x in range(w)][n * w : (n + 1) * w]]) for n in range(h)])

python 2.7.6


저장하지않고 자리에 맞는 숫자를 한번에 출력합니다.

#include <algorithm>
#include <iomanip>

int _tmain(int argc, _TCHAR* argv[])
{
    int iWidth = 6;
    int iHeight = 9;

    for (int ixPosY = 0; ixPosY < iHeight; ++ixPosY)
    {
        for (int ixPosX = 0; ixPosX < iWidth; ++ixPosX)
        {
            int iMinMargin = std::min(std::min(ixPosY, (iWidth - 1) - ixPosX), std::min((iHeight - 1) - ixPosY, ixPosX));
            int iInnerBoxIndex = iWidth * iHeight - ((iWidth - iMinMargin * 2) * (iHeight - iMinMargin * 2));
            int iInnerBoxWidth = iWidth - iMinMargin * 2;
            int iInnerBoxHeight = iHeight - iMinMargin * 2;

            int iNowNumber = 0;
            if (ixPosY == iMinMargin || ixPosX == (iInnerBoxWidth - 1) + iMinMargin)
            {
                iNowNumber = iInnerBoxIndex + ixPosX + ixPosY - iMinMargin * 2;
            }
            else
            {
                iNowNumber = iInnerBoxIndex + iInnerBoxWidth * 2 + iInnerBoxHeight * 2 - 4 - (ixPosX + ixPosY - iMinMargin * 2);
            }
            std::cout << std::setw(4) << iNowNumber;
        }
        std::cout << std::endl;
    }
    system("pause");
    return 0;
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

python

class Cursor:
    D = {
        "right":(0,1),
        "left":(0,-1),
        "up":(-1,0),
        "down":(1,0),
    }

    def __init__(self, row, col, direction):
        self.row = row
        self.col = col
        self.direction = direction

    def next(self):
        adder = self.D[self.direction]
        nr = self.row + adder[0]
        nc = self.col + adder[1]
        return Cursor(nr, nc, self.direction)

    def rotate(self):
        r = {
            "right":"down",
            "down":"left",
            "left":"up",
            "up":"right",
        }
        self.direction = r[self.direction]


class Map:
    def __init__(self, row_count, col_count):
        self.row_count = row_count
        self.col_count = col_count
        self.m = [[None for c in range(self.col_count)] 
            for r in range(self.row_count)]

        cursor = Cursor(0,0, "right")
        self.mark(cursor, 0)
        for i in range(1, self.row_count * self.col_count):
            next_cursor = cursor.next()
            if self.edge(next_cursor):
                cursor.rotate()
                cursor = cursor.next()
            else:
                cursor = next_cursor
            self.mark(cursor, i)

    def mark(self, cursor, v):
        self.m[cursor.row][cursor.col] = v

    def edge(self, pos):
        if pos.col < 0: return True
        if pos.row < 0: return True
        if pos.col >= self.col_count: return True
        if pos.row >= self.row_count: return True

        isMark = self.m[pos.row][pos.col] != None
        if isMark: return True
        return False


m = Map(6, 6)
for row in m.m: print row
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
r,c = map(int,raw_input().split(' '))

lst = list()
array = [[0 for x in range(c)] for x in range(r)]
row,col = r,c   # 나중에 array를 출력할때를 위해 r,c 백업
cnt = 0         # 현재 출력할 수
curr_point = (0,0)  # 현재 수를 출력할 좌표
curr_direct = 'RIGHT'   # 현재 방향

move = {        # 방향을 넣으면 움직여야할 좌표를 반환하는 dict
    'UP'    : (-1,0),
    'DOWN'  : (1,0),
    'LEFT'  : (0,-1),
    'RIGHT' : (0,1)
}

next_direct = {     # 현재 방향을 넣으면 다음방향을 반환하는 dict
    'UP'    : 'RIGHT',
    'RIGHT' : 'DOWN',
    'DOWN'  : 'LEFT',
    'LEFT'  : 'UP'
}

for i in range(r+c-1):  # 방향이 바뀔때 마다 움직여야할 거리를 순서대로 list에 담음
    if i % 2 is 0:
        lst.append(c)
        r = r - 1
    else:
        lst.append(r)
        c = c - 1

for i in lst:     # array에 차례로 숫자를 씀
    for j in range(i):
        array[curr_point[0]][curr_point[1]] = cnt
        cnt = cnt + 1
        if j is i-1:
            curr_direct = next_direct[curr_direct]
        curr_point = tuple(map(sum,zip(curr_point, move[curr_direct])))

for i in range(row):       # array 출력
    for j in range(col):
        print '%3d'%array[i][j],
    print ''

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

맨 바깥쪽 한바퀴 채우는걸 따로 함수로 만들고 한칸씩 안쪽으로 들어가는 식으로 구현했습니다.

def spiralone(l, n, a, b, c, d):
    hlen = d-b
    vlen = c-a
    if vlen < 1 or hlen < 1: return -1
    for i in range(0, hlen):
        l[a][b+i] = n
        n += 1
    if vlen > 1:
        for i in range(1, vlen):
            l[a+i][d-1] = n
            n += 1
        if hlen > 1:
            for i in range(1, hlen):
                l[c-1][d-1-i] = n
                n += 1
            if vlen > 2:
                for i in range(1, vlen-1):
                    l[c-1-i][b] = n
                    n += 1
    return n

def emptyarray(m, n):
    array = []
    for i in range(m):
        array.append([0 for y in range(n)])
    return array

def printarray(l, m, n):
    for i in range(m):
        for j in range(n):
            print("%3d" % l[i][j], end=" ")
        print("")

m, n = 16, 13
l = emptyarray(m, n)
value = 0
a, b, c, d = 0, 0, m, n
while value != -1:
    value = spiralone(l, value, a, b, c, d)
    a, b, c, d = a+1, b+1, c-1, d-1

printarray(l, m, n)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
w, h = map(int,input().split())
t = eval(repr([[0]*h]*w))
ds = [[1,0],[0,1],[-1,0],[0,-1]]
e=x=y=d=0
for i in range(w*h):
    t[x][y] = i
    if x+ds[d][0] in [e-1-(1 if d==3 else 0),w-e] or y+ds[d][1] in [e-1,h-e]:
        d = (d+1)%4
        e += d//3
    x, y = map(sum,zip(ds[d],[x,y]))
for i in range(w*h):
    print(("%%%dd" % (len(str(w*h-1))+1)) % t[i%w][i//w], end=('\n' if i%w==w-1 else ''))

22 47 입력시

    0    1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16   17   18   19   20   21
  133  134  135  136  137  138  139  140  141  142  143  144  145  146  147  148  149  150  151  152  153   22
  132  259  260  261  262  263  264  265  266  267  268  269  270  271  272  273  274  275  276  277  154   23
  131  258  377  378  379  380  381  382  383  384  385  386  387  388  389  390  391  392  393  278  155   24
  130  257  376  487  488  489  490  491  492  493  494  495  496  497  498  499  500  501  394  279  156   25
  129  256  375  486  589  590  591  592  593  594  595  596  597  598  599  600  601  502  395  280  157   26
  128  255  374  485  588  683  684  685  686  687  688  689  690  691  692  693  602  503  396  281  158   27
  127  254  373  484  587  682  769  770  771  772  773  774  775  776  777  694  603  504  397  282  159   28
  126  253  372  483  586  681  768  847  848  849  850  851  852  853  778  695  604  505  398  283  160   29
  125  252  371  482  585  680  767  846  917  918  919  920  921  854  779  696  605  506  399  284  161   30
  124  251  370  481  584  679  766  845  916  979  980  981  922  855  780  697  606  507  400  285  162   31
  123  250  369  480  583  678  765  844  915  978 1033  982  923  856  781  698  607  508  401  286  163   32
  122  249  368  479  582  677  764  843  914  977 1032  983  924  857  782  699  608  509  402  287  164   33
  121  248  367  478  581  676  763  842  913  976 1031  984  925  858  783  700  609  510  403  288  165   34
  120  247  366  477  580  675  762  841  912  975 1030  985  926  859  784  701  610  511  404  289  166   35
  119  246  365  476  579  674  761  840  911  974 1029  986  927  860  785  702  611  512  405  290  167   36
  118  245  364  475  578  673  760  839  910  973 1028  987  928  861  786  703  612  513  406  291  168   37
  117  244  363  474  577  672  759  838  909  972 1027  988  929  862  787  704  613  514  407  292  169   38
  116  243  362  473  576  671  758  837  908  971 1026  989  930  863  788  705  614  515  408  293  170   39
  115  242  361  472  575  670  757  836  907  970 1025  990  931  864  789  706  615  516  409  294  171   40
  114  241  360  471  574  669  756  835  906  969 1024  991  932  865  790  707  616  517  410  295  172   41
  113  240  359  470  573  668  755  834  905  968 1023  992  933  866  791  708  617  518  411  296  173   42
  112  239  358  469  572  667  754  833  904  967 1022  993  934  867  792  709  618  519  412  297  174   43
  111  238  357  468  571  666  753  832  903  966 1021  994  935  868  793  710  619  520  413  298  175   44
  110  237  356  467  570  665  752  831  902  965 1020  995  936  869  794  711  620  521  414  299  176   45
  109  236  355  466  569  664  751  830  901  964 1019  996  937  870  795  712  621  522  415  300  177   46
  108  235  354  465  568  663  750  829  900  963 1018  997  938  871  796  713  622  523  416  301  178   47
  107  234  353  464  567  662  749  828  899  962 1017  998  939  872  797  714  623  524  417  302  179   48
  106  233  352  463  566  661  748  827  898  961 1016  999  940  873  798  715  624  525  418  303  180   49
  105  232  351  462  565  660  747  826  897  960 1015 1000  941  874  799  716  625  526  419  304  181   50
  104  231  350  461  564  659  746  825  896  959 1014 1001  942  875  800  717  626  527  420  305  182   51
  103  230  349  460  563  658  745  824  895  958 1013 1002  943  876  801  718  627  528  421  306  183   52
  102  229  348  459  562  657  744  823  894  957 1012 1003  944  877  802  719  628  529  422  307  184   53
  101  228  347  458  561  656  743  822  893  956 1011 1004  945  878  803  720  629  530  423  308  185   54
  100  227  346  457  560  655  742  821  892  955 1010 1005  946  879  804  721  630  531  424  309  186   55
   99  226  345  456  559  654  741  820  891  954 1009 1006  947  880  805  722  631  532  425  310  187   56
   98  225  344  455  558  653  740  819  890  953 1008 1007  948  881  806  723  632  533  426  311  188   57
   97  224  343  454  557  652  739  818  889  952  951  950  949  882  807  724  633  534  427  312  189   58
   96  223  342  453  556  651  738  817  888  887  886  885  884  883  808  725  634  535  428  313  190   59
   95  222  341  452  555  650  737  816  815  814  813  812  811  810  809  726  635  536  429  314  191   60
   94  221  340  451  554  649  736  735  734  733  732  731  730  729  728  727  636  537  430  315  192   61
   93  220  339  450  553  648  647  646  645  644  643  642  641  640  639  638  637  538  431  316  193   62
   92  219  338  449  552  551  550  549  548  547  546  545  544  543  542  541  540  539  432  317  194   63
   91  218  337  448  447  446  445  444  443  442  441  440  439  438  437  436  435  434  433  318  195   64
   90  217  336  335  334  333  332  331  330  329  328  327  326  325  324  323  322  321  320  319  196   65
   89  216  215  214  213  212  211  210  209  208  207  206  205  204  203  202  201  200  199  198  197   66
   88   87   86   85   84   83   82   81   80   79   78   77   76   75   74   73   72   71   70   69   68   67
아하 저는 계속 계산해서 구하도록 했는데, ds 변수를 사용하는 것도 매력적이네요^^ - Shin Kyosoo, 2015/03/01 02:10 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

파이썬 3.4 입니다. 앞에 분들에 비하면 부족하지만, 올려 봅니다.

def spiral_array(x_max,y_max):
    matrix = [[0 for i in range(x_max)] for j in range(y_max)]    
    x,y = 0,0
    num=0

    for i in range(x_max-1):
        x += 1
        num += 1
        matrix[y][x] = num

    while x_max > 0 and y_max > 0:

        for i in range(y_max-1):
            y += 1
            num += 1
            matrix[y][x] = num
        y_max -= 1

        for i in range(x_max-1):
            x -= 1
            num += 1            
            matrix[y][x] = num
        x_max -= 1

        for i in range(y_max-1):
            y -=1
            num += 1
            matrix[y][x] = num
        y_max -= 1

        for i in range(x_max-1):
            x += 1
            num += 1
            matrix[y][x] = num
        x_max -= 1

    return matrix


x_max, y_max = map(int,input().split())
result = spiral_array(x_max,y_max)
for y in range(y_max):
    for x in range(x_max):
        print ('%3d'%result[y][x], end=" ")
    print('')
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
from operator import add
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

n, m = map(int, raw_input().split(" "))
mat = [[-1 for x in xrange(0, m)] for y in xrange(0, n)]

count = 0
cur_dir = 0
cur_pos = (0, 0)

while count < n * m - 1:
    mat[cur_pos[0]][cur_pos[1]] = count
    next_pos = tuple(map(add, cur_pos, directions[cur_dir]))
    while next_pos[0] < 0 or next_pos[0] >= n or next_pos[1] < 0 or next_pos[1] >= m or mat[next_pos[0]][next_pos[1]] != -1:
        cur_dir = (cur_dir + 1) % len(directions)
        next_pos = tuple(map(add, cur_pos, directions[cur_dir]))
    count += 1
    cur_pos = next_pos

mat[cur_pos[0]][cur_pos[1]] = count


for i in xrange(len(mat)):
    print mat[i]

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
raw = '6 6'
width, height = map(int, raw.split(' '))

matrix = [0]*(width*height)

deltas = [1, width, -1, -width]
direction = 0

go_x = width
go_y = height-1

count, index = 0, -1

while go_x >= 0 and go_y >= 0:
  delta = deltas[direction]
  if direction%2 == 0:
    go = go_x
    go_x -= 1
  else:
    go = go_y
    go_y -= 1
  if go > 0:
    for i in range(0, go):
      index += delta
      matrix[index] = count
      count += 1
  direction = (direction + 1) % 4

maxnum = width*height-1
digits = len(str(maxnum))

for y in range(0, height):
  padded = [str(x).rjust(digits) for x in matrix[y*width:(y+1)*width]]
  print(' '.join(padded))

빈 배열을 만들고 달팽이처럼 돌아가면서 채웠습니다.

매 루프마다 인덱스를 1, width, -1, -width, ... 만큼 더해주면서..

다른 코드들을 보니 출력하는 부분도 깔끔하고 그렇더군요.. 공부를 더 해야겠습니다.

한시간 정도 걸렸는데 일부러 더 다듬지 않고 걍 올립니다.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.


언어별 풀이 현황
전 체 x 146
기 타 x 17
java x 31
cpp x 35
python x 45
lisp x 2
ruby x 2
cs x 6
scala x 3
clojure x 1
objectivec x 1
go x 1
delphi x 1
javascript x 1