[SWEA 1954] 달팽이 JAVA

SWEA 1954번 달팽이 JAVA

문제

SW Expert Academy

 

입력값

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.

각 테스트 케이스에는 N이 주어진다.

2    
3   
4

 

출력값

각 줄은 '#t'로 시작하고, 다음 줄부터 빈칸을 사이에 두고 달팽이 숫자를 출력한다.

(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

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

 

알고리즘

 

1. 일반적인 구현

 public static final int[] dr = {0, 1, 0, -1};
 public static final int[] dc = {1, 0, -1, 0};

그 이후에 달팽이는 (0, 0)의 위치에서 숫자를 0부터 찍으면서 출발한다. 만약 달팽이가 이동할 때 이동할 다음 좌표가 경계를 벗어나거나, 이동할 좌표의 요소가 0이 아니라면 (이미 전에 왔었다면) 방향을 바꾸어 이동한다. 이를 숫자가 N제곱이 배열에 저장될 때 까지 반복한다. 숫자는 1 부터 N의 제곱까지 배열에 들어간다. 중요한 것은 어떤 숫자가 들어가느냐가 아닌, 어느 위치에 들어가느냐이다. 일단 달팽이가 우 → 하 → 좌 → 상 방향으로 순차적으로 이동한다고 가정하고 델타를 설정한다.

 

2. 재귀 사용

1. 우 이동 : 4개
2. 하 이동 : 3개
3. 좌 이동 : 3개
4. 상 이동 : 2개
5. 우 이동 : 2개
6. 하 이동 : 1개
7. 좌 이동 : 1개

달팽이가 이동하는 방향과 방향을 바꾸지 않으면서 저장하는 숫자의 수를 정리하면 다음과 같다.

시작한 방향으로 N만큼 1번 움직이고 나머지는 1씩 빼주면서 2번씩 반복된다. 즉 N, N-1, N-1, N-2 ~ 1, 1 의 개수만큼 숫자를 배열에 저장하면서 방향을 바꿔주면 된다. 재귀로 구현하기 위해서 size와 dec 변수를 추가했다. size는 지금 달팽이의 진행 방향에서 찍어야 하는 숫자의 개수이고 dec는 방향을 전환할 때 size를 1 감소해야 하는지 판단하기 위해 사용했다.

 

코드

1. 일반적인 구현

import java.io.*;

public class Solution {
    public static final int[] dr = {0, 1, 0, -1};
    public static final int[] dc = {1, 0, -1, 0};

    public static int TC;
    public static int N;
    public static int[][] map;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        TC = Integer.parseInt(br.readLine());

        for (int tc = 0; tc < TC; tc++) {
            N = Integer.parseInt(br.readLine());
            map = new int[N][N];

            int dir = 0;
            int r = 0, c = -1;

            for (int i = 1; i <= N * N; i++) {
                int newR = r + dr[dir];
                int newC = c + dc[dir];

                if (0 <= newR && newR < N && 0 <= newC && newC < N && map[newR][newC] == 0) {
                    map[newR][newC] = i;
                    r = newR; c = newC;

                } else {
                    dir = (dir + 1) % 4;
                    i--;
                }
            }

            System.out.printf("#%d\n", tc + 1);
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    System.out.print(map[i][j] + " ");
                }
                System.out.println();
            }
        }
    }
}

 

2. 재귀

import java.io.*;

public class Solution {

    public static final int[] dr = {0, 1, 0, -1};
    public static final int[] dc = {1, 0, -1, 0};

    public static int TC;
    public static int N;
    public static int[][] map;
    public static int number = 1;
    public static int r, c;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        TC = Integer.parseInt(br.readLine());

        for (int tc = 0; tc < TC; tc++) {
            N = Integer.parseInt(br.readLine());

            int size = N;
            int dec = 1;
            int dir = 0;

            map = new int[N][N];
            number = 1;
            r = 0; c = -1;

            goDalpang(size, dec, dir);

            System.out.printf("#%d\n", tc + 1);
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    System.out.print(map[i][j] + " ");
                }
                System.out.println();
            }
        }
    }

    public static void goDalpang(int size, int dec, int dir) {
        if (size == 0) {
            return;
        } else {

            for (int i = 0; i < size; i++) {
                r += dr[dir]; c += dc[dir];
                map[r][c] = number++;
            }

            dec = (dec + 1) % 2;
            if (dec == 0) {
                size--;
            }
            dir = (dir + 1) % 4;

            goDalpang(size, dec, dir);
        }
    }
}