코드트리 [자바 java] 빙빙 돌며 숫자 적기

https://www.codetree.ai/missions/5/problems/snail-number-square/introduction

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

1	2	3	4
12	13	14	5
11	16	15	6
10	9	8	7

이 문제는 위와 같은 방식으로 숫자 n이 주어지면 시계 반대방향으로 돌면서 숫자를 채워야 한다.

 

이는 dx,dy테크닉을 이용하면 쉽게 풀 수 있다. 

위 그림과 같이 동,서,남,북에 숫자를 적고, 벽을 만날 때마다 방향을 하나씩 더해주도록 하였다. 벽을 만나는 것은 현재 위치에다가 해당하는 dx,dy 배열을 더했을 때, 값이 격자를 넘어가는 것을 뜻한다.

 

import java.io.*;
import java.util.*;
import java.math.*;


public class Main {
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] arr = new int[n][m];

        int num = 1;

        int x = 0;
        int y = 0;
        int d = 0;
        arr[x][y] = 1;

        int[] dy = {1,0,-1,0};
        int[] dx = {0,1,0,-1};


        while(num != n*m){
            if(x + dx[d] < 0 || x + dx[d] >= n || y + dy[d] < 0 || y + dy[d] >= m ||
               arr[x + dx[d]][y + dy[d]] != 0){

                d = (d +1) % 4;
               }
               num++;  

              x += dx[d]; 
              y += dy[d];

               arr[x][y] = num;
               

        }

        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                System.out.printf("%d ",arr[i][j]);
            }
            System.out.println();
        }

        


    }
}