[SWEA 1954] 달팽이 숫자

문제

• SWEA 1954번
• 문제의 저작권은 SW Expert Academy에 있습니다.

접근방식

처음엔 1210번과 마찬가지로 현재 좌표에서 우->하->좌->상을 모두 돌면서 다음 좌표가 범위 안에 있고 값이 비어있으면 이동하는식으로 구현하려고 했다. 그러나 이렇게 적용해버리면 여기서는 전체 방향을 모두 돌기때문에 나선형으로 돌다가 만약 ↑도 비어있고 →도 비어있는 경우에는 →방향이 먼저이므로 우측으로 가버리기 때문에 원하는 순서대로 숫자가 넣어지지 않는다.
따라서, 여기서는 방향을 아예 하나로 고정해버리고 모서리를 만나면 방향이 하나씩 증가하게끔 구현했다. 자세히 보면 모서리에 도착하면 방향이 우->좌->상->하 순서대로 반복되는 규칙이 있다는 것을 알 수 있다.
이를 적용해서 처음 방향은 우측이 되므로 방향변수 dir=0이다. 좌표는 0,0에서 시작해서 x좌표에 di[0], y좌표에 dj[0]만큼 움직인다. 그러다 만약 이동한 좌표가 범위 밖을 벗어났거나 이미 다른 값으로 채워져있다면 다시 이전 좌표로 돌아온 후, 방향을 바꿔서 다음 방향으로 이동한다. 이렇게 방문한 좌표값이 확정되면 숫자값을 넣어주고 다시 for문을 돌린다. 이렇게 숫자가 N*N이 될때까지 돌리면 숫자가 나선형으로 배열에 잘 들어가 있는 모습을 볼 수 있다.

코드

import java.io.*;
import java.util.Scanner;

public class Swea_1954 {
	static int N = 0;
	static int[][] map;
	static int[] di = { 0, 1, 0, -1 }; // 우, 하, 좌, 상
	static int[] dj = { 1, 0, -1, 0 };

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 0; tc < T; tc++) {
			N = sc.nextInt();
			map = new int[N][N];

			// 출발 (행, 열), 방향
			int r = 0, c = 0, dir = 0;
			map[0][0] = 1;
			// 맵에 들어갈 숫자 차례대로 1~N*N까지
			for (int i = 2; i <= N * N; i++) {
				// 현재좌표값을 다음 좌표값으로 변경
				r += di[dir];
				c += dj[dir];

				// 다음 좌표값이 범위를 넘고, 다른 값으로 이미 채워져있다면
				if (r < 0 || r >= N || c < 0 || c >= N || map[r][c] != 0) {
					//다시 이전 좌표로 돌아와서
					r -= di[dir];
					c -= dj[dir];
					// 다음 방향 결정: 3넘어가면 다시 0
					dir = (dir + 1) % 4; 
					r += di[dir];
					c += dj[dir];
				}
				map[r][c] = i;
			}
			System.out.println("#" + (tc + 1));
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					System.out.print(map[i][j] + "\t");
				}
				System.out.println();
			}
		}
	}

}