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 매트릭스에 나선형 회전을 한 값을 출력해야 한다.

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

132개의 풀이가 있습니다. 1 / 14 Page

X,Y = map(int,raw_input().split(' '))
lis = [[-1 for i in xrange(Y)] for j in xrange(X)]
x,y = 0,0
dx,dy = 0,1
count = 0
while lis[x][y] == -1:
    lis[x][y] = count
    count+=1
    x,y = x+dx,y+dy
    if x in [-1,X] or y in [-1,Y] or lis[x][y] != -1:
        x,y = x-dx,y-dy
        dx,dy = dy,-dx
        x,y = x+dx,y+dy
for L in lis:
    for val in L:
        print '%3d'%val,
    print
앗 빠르네요 감사합니다. - 양지훈, 2012/01/14 22:36 M D
코드 멋지네요! - 심재용, 2015/05/04 14:07 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

우선탐색을 하게하여 길을 찾게 하였습니다.

    Sub Main()
        '// 입력
        Dim input() As String = Console.ReadLine.Split(" ")

        Dim x As Integer = 0, y As Integer = 0

        Dim width As Integer = CInt(input(0)), height As Integer = CInt(input(1))
        Dim map(width - 1, height - 1) As Integer
        Dim cnt As Integer = 0, isUp As Boolean = False

        Do
            cnt += 1
            If x + 1 < width AndAlso map(x + 1, y) = 0 And Not isUp Then map(x + 1, y) = cnt : x += 1 : isUp = False : Continue Do
            If y + 1 < height AndAlso map(x, y + 1) = 0 Then map(x, y + 1) = cnt : y += 1 : isUp = False : Continue Do
            If x - 1 >= 0 AndAlso map(x - 1, y) = 0 Then map(x - 1, y) = cnt : x -= 1 : isUp = False : Continue Do
            If y - 1 >= 0 AndAlso map(x, y - 1) = 0 AndAlso x + y - 1 > 0 Then : map(x, y - 1) = cnt : y -= 1 : isUp = True : Continue Do : ElseIf cnt < width * height Then : isUp = False : cnt -= 1 : Continue Do : End If

            Exit Do
        Loop

        '// 출력
        For yy As Integer = 0 To width - 1
            For xx As Integer = 0 To height - 1
                Console.Write(map(xx, yy) & vbTab)
            Next
            Console.WriteLine()
        Next

        Console.ReadLine()
    End Sub
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
public enum Direction { // 방향을 나타내는 enum입니다~
    RIGHT(1), BOTTOM(2), LEFT(3), TOP(4);
    private int value;

    private Direction(int value) {
        this.value = value;
    }
}

public class Sprial {

public void sprialArray(int row, int col) {
        int[][] arr = new int[row][col];

        // -1로 초기화
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                arr[i][j] = -1;
            }
        }

        int num = 0; // 시작 숫자
        int rIdx = 0, cIdx = 0; // row, col에 대한 index
        Direction direction = Direction.RIGHT;

        while( num < row * col ) {
            arr[rIdx][cIdx] = num++;

            switch ( direction ) {
            case RIGHT:
                if( cIdx+1<col && arr[rIdx][cIdx+1] == -1 ){
                    cIdx++;
                }else {
                    direction = Direction.BOTTOM;
                    rIdx++;
                }
                break;
            case BOTTOM:
                if( rIdx+1<row && arr[rIdx+1][cIdx] == -1 ){
                    rIdx++;
                }else {
                    direction = Direction.LEFT;
                    cIdx--;
                }
                break;
            case LEFT:
                if( cIdx-1>=0 && arr[rIdx][cIdx-1] == -1 ){
                    cIdx--;
                }else {
                    direction = Direction.TOP;
                    rIdx--;
                }               
                break;
            case TOP:
                if( rIdx-1>=0 && arr[rIdx-1][cIdx] == -1 ){
                    rIdx--;
                }else {
                    direction = Direction.RIGHT;
                    cIdx++;
                }
                break;
            default:
                break;
            }
        }
    }
}

~_~ 전 이 문제 푸는데 되게 오래 걸렸어요.. 내공이 많이 부족함을 느낍니다 ㅠㅠ 분명 예~전에 처음 플그래밍 배울때 봤던 문제였떤 것 같은데, 그때 어렵다고 패스했던 것을 다시 공부하지 않은 탓인것 같네요..ㅜ

+1 switch case 에 enum 을 같이 쓰니 소스가 참 보기 좋네요 ^^ - 길가의풀, 2014/05/09 08:55 M D
1,2,3,4로 했었는데, 보다 암걸릴 것 같아서 enum 으로 바꿨어요^^ 이참에 활용 잘 해봐야겠어요~~ - 이 승효, 2014/05/09 13:11 M D
enum 처리 보기좋네요ㅎㅎ - 이재범, 2014/06/18 13:50 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

4일이나 걸렸어요... 매일 2시간씩 해서 했는데

이 코드는 아무래도 if문이 너무 많아서 반복문내에서 매 번 if문을 하나하나 다 검사한다는게

썩 좋진 않아보이네요. 실행속도가 현저히 느릴거 같아요... 그래도 완성해서 매우 기쁩니다!

/*
입력: 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 매트릭스에 나선형 회전을 한 값을 출력해야 한다.
*/

import java.util.Arrays;
import java.util.Scanner;

public class Spiral_Array
{
    public static void main(String[] args)
    {
        // 출력될 숫자
        int output_Number=0; 

        // 값을 두 개 입력받습니다.
        Scanner in = new Scanner(System.in);
        int n1 = in.nextInt();
        int n2 = in.nextInt();

        // 숫자가 들어갈 매트릭스를 생성합니다.
        int[][] Matrix = new int[n1][n2];

        // 배열 값들을 다 -1로 초기화 (2D)
        for (int[] row: Matrix)
            Arrays.fill(row, -1);

        //위치 선택용 변수
        int col=0, row=0, t_col=0, t_row=1, angle = 0;

        // row가 늘고 col가 늘고 row가 줄고 col가 줄고 row가 늘고 col가 늘고 ... 계속 반복함
        for(int i=0; i<(n1*n2); i++)
        {
            Matrix[col][row]=output_Number;
            output_Number++;
            row = row + t_row;
            col = col + t_col;

            if(row==n2){ // 1번째 코너
                row--;
                col++;
                t_col = t_row;
                t_row = 0;
            }
            if(col==n1){ // 2번째 코너
                col--;
                row--;
                t_row = -t_col;
                t_col = 0;
            }
            if(row<0){ // 3번째 코너
                row++;
                col--;
                t_col = t_row;
                t_row = 0;
            }

            if(Matrix[col][row] != -1)  // 다른 수가 있다면(3번째 이후 모서리 봉착)
            {
                angle++; 
                if(angle == 1)// ┌자 구간에 진입했을때
                {
                    row++;
                    col++;
                    t_col = 0;
                    t_row = 1;
                }
                else if(angle == 2) // ┐자 구간에 진입했을때
                {
                    col++;
                    row--;
                    t_col = 1;
                    t_row = 0; 
                }

                else if(angle == 3) // ┘자 구간에 진입했을때
                {
                    col--;
                    row--;
                    t_col = 0;
                    t_row = -1;
                }
                else if(angle == 4) // └자 구간에 진입했을때
                {
                    col--;
                    row++;
                    t_col = -1;
                    t_row = 0;

                    angle = 0; // 다시 초기화
                }
            }
        }

        // 출력
        for(int a=0; a<n1; a++){
            for(int b=0; b<n2; b++){
                System.out.print(Matrix[a][b] + "\t");
            }
            System.out.println();
        }
    } // main
} // class
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
#include <iostream>

using namespace std;
void getInput(int ** arr, int row, int column);

int main() {

    int row=0, column=0;

    cin >> row >> column;

    int ** arr = new int *[row];
    for(int i=0; i<row; i++) {
        arr[i] = new int [column];
    }

    getInput(arr, row, column);

    for(int i=0; i<row; i++) {
        for(int j=0; j<column; j++) {
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

void getInput(int ** arr, int row, int column) {
    int inputValue =-1;
    int start_i = 0, start_j = 0;
    int last_i = row-1, last_j = column-1;
    int finalValue = (row*column)-1;

    while(inputValue!=finalValue){
        for(int j=start_j; j<=last_j; j++) {
            inputValue+=1;
            arr[start_i][j] = inputValue;
        }
        if(inputValue==finalValue) break;
        for(int i=start_i+1; i<=last_i; i++) {
            inputValue+=1;
            arr[i][last_j] = inputValue;
        }
        if(inputValue==finalValue) break;
        for(int j=last_j-1; j>=start_j; j--) {
            inputValue+=1;
            arr[last_i][j] = inputValue;
        }
        if(inputValue==finalValue) break;
        for(int i=last_i-1; i>=start_i+1; i--) {
            inputValue+=1;
            arr[i][start_j] = inputValue;
        }
        if(inputValue==finalValue) break;
        start_i+=1; start_j+=1; last_i-=1; last_j-=1;
    }
}

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

int main(){
    int x=100, y=90, x_=0, y_=0; 
    // x, y : 사용자 입력(행,렬) 
    // x_,y_ 결과표시를 위한 임시저장 변수 
    int a=0, b=0, c=0, i=0, j=0;
    // a, b : 각각 행,열 좌표조정을 위한 변수
    // c : 테두리 직선의 count 수
    // i, j : 반복문을 위한 임시변수 

    int current = 0; // 대입할 값
    int **arr;

    scanf("%d %d", &x, &y);
    x_ = x;
    y_ = y;

    arr = (int**) malloc (sizeof(int*)*x);
    for(i=0; i<x; i++) arr[i]=(int*)malloc(sizeof(int)*y);

    // a, b의 증가또는 감소로 arr의 인덱스(좌표 a,b) 방향을 조절하고
    // 하나의 라인이 끝날 때마다 x_, y_ 값을 점점 줄여나가면서
    // 나선방향으로 차례대로 값을 대입한다.

    for(c=1; current<x*y; c++){
        int temp = (c/2)%2; 
        // temp : arr의 인덱스를 표시하는 a 또는 b의 증감(방향)을 판별하기위한 변수
        // 행의 경우 temp의 값이 1인경우 a가 증가하는방향, 아닌경우 감소하는 방향
        // 열의 경우 temp의 값이 0인경우 b가 증가하는방향, 아닌경우 감소하는 방향

        // 행, 열, 행, 열 순서대로 대입하므로 
        // 하나의 라인을 count하는 c가 홀수인경우 열, 짝수인경우 행
        if(c%2 == 1){ // 열
            for(i=0; i<y_; i++){
                if(i != 0){
                    if(temp == 0) b++;
                    else b--;
                }
                //printf("(%d, %d) = %d\n", a, b, current);
                arr[a][b] = current;
                current++;
            }
            y_--;
        }
        else{ // 행
            for(i=0; i<x_-1; i++){
                if(temp == 1) a++;
                else a--;
                //printf("(%d, %d) = %d\n", a, b, current);
                arr[a][b] = current;
                current++;
            }
            if(temp == 0) b++;
            else b--;
            x_--;
        }
    }

    for(i=0; i<x; i++){
        for(j=0; j<y; j++)
            printf("%d ", arr[i][j]);
        printf("\n");
    }

    return 0;
}

C언어로 작성. 풀이방법은 주석참고.

아..2차원 배열 동적 할당 방법에 대해서 새로이 배우네요.. 좋은 풀이 감사합니다~ - Jeon Jihyeon, 2016/10/04 00:26 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

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

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;
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

음.. 아이디어가 없어서 최대한 이해하기 쉽게 했는데, 저장공간이 필요해서 에러네요.

오늘 처음 온 곳인데, 깔끔하고 좋습니다. 많이 활성화 되었으면 좋겠습니다.

using namespace std;

int main(int argc, char *argv[])
{
    int w = 0;
    int h = 6;

    cout << "width: ";
    cin >> w;
    cout << "height: ";
    cin >> h;

    int **arr = new int *[w];
    for(int i = 0; i < w; i++)
    {
        arr[i] = new int[h];
    }

    for(int round = 0, i = 0; i < w * h; round++)
    {
        // top
        for(int x = round; x < w - round && i < w * h; x++)
        {
            arr[x][round] = i;
            i++;
        }

        // right
        for(int y = round + 1; y < h - round && i < w * h; y++)
        {
            arr[w - round - 1][y] = i;
            i++;
        }

        // bottom
        for(int x = w - round - 2; x >= round && i < w * h; x--)
        {
            arr[x][h - round - 1] = i;
            i++;
        }

        // left
        for(int y = h - round - 2; y > round && i < w * h; y--)
        {
            arr[round][y] = i;
            i++;
        }
    }

    for(int y = 0; y < h; y++)
    {
        for(int x = 0; x < w; x++)
        {
            printf("%3d ", arr[x][y]);
        }

        cout << endl;
    }

    for(int i = 0; i < w; i++)
        delete[] arr[i];
    delete[] arr;

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

안녕하세요. C로 짰는데 언어선택에 C가 없어서 C++로 선택했습니다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Given a 2-dimensional array, make it a spiral array.
 * Spiral array is like below.
 *  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
 *
 * array: pointer of 2-dimensional array
 * row: the number of rows
 * col: the number of columns
 * start: the start value which is the leftmost-top value of array
 */
void spiral_array(int **array, int row, int col, int start)
{
  int i;
  int idx = 0;
  int val = start;

  while (row > 0 && col > 0) {
    // left-top to right-top
    for (i = idx; i < idx + col; i++) {
      array[idx][i] = val++;
    }

    // right-top to right-bottom
    for (i = idx + 1; i < idx + row; i++) {
      array[i][idx + col - 1] = val++;
    }

    // right-bottom to left-bottom
    if (row > 1) {
      for (i = idx + col - 2; i >= idx; i--) {
        array[idx + row - 1][i] = val++;
      }
    }

    // left-bottom to left-top
    if (col > 1) {
      for (i = idx + row - 2; i > idx; i--) {
        array[i][idx] = val++;
      }
    }

    idx++;
    row -= 2;
    col -= 2;
  }
}

/* print matrix(2-dimensional array)
 * matrix: pointer of matrix
 * row: the number of rows
 * col: the number of columns
 * space: the minimum number of characters for a value to be printed */
void print_matrix(int **matrix, int row, int col, int space)
{
  int i, j;
  for (i = 0; i < row; i++) {
    for (j = 0; j < col; j++) {
      printf("%*d ", space, matrix[i][j]);
    }
    printf("\n");
  }
}

int **malloc_2d(int row, int col)
{
  int i;
  int **p = (int **)malloc(sizeof (int *) * row);
  if (p == NULL) return NULL;

  for (i = 0; i < row; i++) {
    p[i] = (int *)malloc(sizeof (int) * col);

    if (p[i] == NULL) {
      int j;
      for (j = 0; j < i; j++)
        free(p[j]);
      free(p);
      return NULL;
    }
  }

  return p;
}

void free_2d(int **p, int row)
{
  int i;
  for (i = 0; i < row; i++)
    free(p[i]);
  free(p);
}

int main(int argc, char *argv[])
{
  int row, col;
  printf("row: ");
  scanf("%d", &row);
  printf("col: ");
  scanf("%d", &col);
  int **mat = malloc_2d(row, col);
  spiral_array(mat, row, col, 0);
  print_matrix(mat, row, col, 2);
  free_2d(mat, row);
  return 0;
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Clojure 로 작성하였습니다.

accumulator 형태의 재귀함수입니다.

(defn spiral
  [x y]
  (let [vs (range (* x y))
        walk {:right [1 0]
              :down  [0 1]
              :left  [-1 0]
              :up    [0 -1]}
        turn {:right :down
              :down  :left
              :left  :up
              :up    :right}
        vertical? #{:up :down}
        table (into
                {}
                (loop [v (first vs)
                       vs (rest vs)
                       loc [0 0]
                       way :right
                       to-go (dec x)
                       cols (dec x)
                       rows (- y 2)
                       acc []]
                  (cond (empty? vs) (conj acc [loc v])
                        (zero? to-go) (recur (first vs)
                                             (rest vs)
                                             (map + loc (walk (turn way)))
                                             (turn way)
                                             (if (vertical? way) cols rows)
                                             (if (vertical? way) cols (dec cols))
                                             (if (vertical? way) (dec rows) rows)
                                             (conj acc {loc v}))
                        true (recur (first vs)
                                    (rest vs)
                                    (map + loc (walk way))
                                    way
                                    (dec to-go)
                                    cols
                                    rows
                                    (conj acc [loc v])))))]
    (doseq [y (range y)]
      (doseq [x (range x)]
        (print (format "%4d" (table [x y]))))
      (println))))
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

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

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


언어별 풀이 현황
전 체 x 132
기 타 x 12
java x 27
cpp x 34
python x 41
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