[SWEA] D2 1954 달팽이 숫자 자바(Java)

문제 링크

 

SW Expert Academy

 

풀이

DFS 알고리즘을 활용해서 풀었다. 범위가 넘어가거나 다음칸이 채워져있지 않는 경우 방향을 바꿔준다.

D2문제 이지만 어려웠던 문제였다.....

 

풀이 코드

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

public class Solution {
	public static int n;
	public static int arr[][];
	public static boolean visited[][];
	public static int dx[] = { 0, 1, 0, -1 };
	public static int dy[] = { 1, 0, -1, 0 };

	public static void main(String[] args) throws NumberFormatException, IOException {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();

		for (int test_case = 1; test_case <= T; test_case++) {
			n = sc.nextInt();
			arr = new int[n][n];
			visited = new boolean[n][n];

			for (int i = 0; i < n; i++) {
				Arrays.fill(visited[i], false);
			}

			dfs(0, 0, 0);

			System.out.println("#"+test_case);
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					System.out.print(arr[i][j] + " ");
				}
				System.out.println();
			}
		}
	}

	public static void dfs(int dir, int x, int y) {
		for (int i = 1; i <= n * n; i++) {
			arr[x][y] = i;
			visited[x][y] = true;

			int cx = x + dx[dir];
			int cy = y + dy[dir];

			// 범위 넘어가거나, 다음칸이 채워져 있는 경우
			if (cx < 0 || cy < 0 || cx >= n || cy >= n || visited[cx][cy]) {
				dir = (dir + 1) % 4; // 방향바꿈
			}

			// 다음칸 지정
			x = x + dx[dir]; 
			y = y + dy[dir];

		}
	}
}