[SWEA] 1954번 : 달팽이 숫자

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PobmqAPoDFAUq

SW Expert Academy

 

문제

달팽이는 1부터 N*N까지의 숫자가 시계방향으로 이루어져 있다.

다음과 같이 정수 N을 입력 받아 N크기의 달팽이를 출력하시오.

 

예제]
N이 3일 경우,

 

N이 4일 경우,

 

[제약사항]

달팽이의 크기 N은 1 이상 10 이하의 정수이다. (1 ≤ N ≤ 10)

 

입력

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

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

 

출력

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

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

 

---

소스코드

import java.io.*;

class Main {
    static int arr[][];
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            n = Integer.parseInt(br.readLine());
            arr = new int[n][n];
            dfs(0, 0, 1, 0);

            sb.append("#" + (i + 1) + "\n");
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    sb.append(arr[j][k] + " ");
                }
                sb.append("\n");
            }
        }
        System.out.println(sb);
    }

    // 우, 하, 좌, 상
    static int rx[] = {0, 1, 0, -1};
    static int ry[] = {1, 0, -1, 0};
    static void dfs(int x, int y, int num, int di) {
        arr[x][y] = num;

        int nx = x + rx[di];
        int ny = y + ry[di];
        // 계속 가던 방향으로 갈 수 있을 떄
        if (!(nx < 0 || ny < 0 || nx >= n || ny >= n) && arr[nx][ny] == 0) {
            dfs(nx, ny, num + 1, di);
        } else {
            // 방향전환
            di = (di + 1) % 4;

            nx = x + rx[di];
            ny = y + ry[di];

            // 범위 밖일 때 or 마지막 지점에 도착했을 때
            if ((nx < 0 || ny < 0 || nx >= n || ny >= n) || arr[nx][ny] != 0) return;
            dfs(nx, ny, num + 1, di);
        }
    }
}

 

해결 방법

1. DFS의 인자로 방향을 주어서 현재 이동 중인 방향을 알 수 있게 한다.
2. 계속 가던 방향으로 갈 수 있다면 가던 방향으로 DFS를 진행한다.
3. 계속 가던 방향으로 갈 수 없다면 방향전환을 한 뒤 DFS를 진행한다. (우 -> 하 -> 좌 -> 상)
4. 범위 밖일 때(N=1일 때) or 마지막 지점에 도착했을 때 return 하여 DFS를 종료한다.