[SWEA] 1954. 달팽이 숫자

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

SW Expert Academy

문제 풀이 :

방법 1) 달팽이 행렬의 패턴은 시계방향으로 90도 만큼 계속 꺾인다. ( ㄱ,ㄴ,ㄱ,ㄴ,... )

그렇기 때문에 변수 turn을 1이거나 -1 일 때로 설정하여 좌표 x와 y가 방향 전환이 되도록 한다. 

ex)

turn = 1,  n=4 일 때 (0,0)(0,1)(0,2)(0,3)

turn = 1,  n=3 일 때 (1,3)(2,3)(3,3) 

turn = -1, n=3 일 때 (3,2)(3,1)(3,0) // 방향 전환

turn = -1, n=2 일 때(2,0)(1,0)

turn = 1,  n=2 일 때 (1,1)(1,2) // 방향전환

turn = 1,  n=1 일 때 (2,2) 

turn = -1, n=0 일 때(2,1) // 방향 전환

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

class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for (int tc = 1; tc <= t; tc++) {
			
			int n = sc.nextInt();
			int[][] map = new int[n][n];
			int turn = 1, x = 0, y = -1,number = 0;

			while(true) {
				for (int i = 0; i < n; i++) {
					y = y+turn;
					map[x][y] = ++number;
				}
				n--;
				for (int i = 0; i <  n; i++) {
					x = x+turn;
					map[x][y] = ++number;
				}
				turn*=-1;
				
				
				if(n==0) break;
			}
			System.out.println("#"+tc+" ");
			for (int i = 0; i < map.length; i++) {
				for (int j = 0; j < map.length; j++) {
					System.out.print(map[i][j] +" ");
				}
				System.out.println();
			}
		} 
	}

}

방법 2) dfs

import java.util.Scanner;

class Solution {
	static int n,number;
	static int[][] dir = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
	static int[][] map;
	static boolean[][] visited;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for (int tc = 1; tc <= t; tc++) {
			number = 1;
			n = sc.nextInt();
			map = new int[n][n];
			visited = new boolean[n][n];

			dfs(0, 0, 0);

			System.out.println("#"+tc+" ");
			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 dfs(int x, int y, int d) {
		map[x][y] = number++;
		visited[x][y] = true;

		for (int k = d; k < d+4; k++) {
			int nx = x + dir[k % 4][0];
			int ny = y + dir[k % 4][1];
			if (isInside(nx, ny) && !visited[nx][ny]) {
				dfs(nx, ny, k);
			}
		}
	}

	public static boolean isInside(int x, int y) {
		return x >= 0 && x < n && y >= 0 && y < n;
	}
}​