Note: 해당 알고리즘은 java로 풀이되었습니다.

문제 보기

문제 분석

D2의 난이도고 문제만 읽었을 때는 굉장히 쉬워보이지만 실제로 풀어보면 ‘어?’ 소리가 나는 문제입니다.
물론 간단하게 푸신 분들도 많고요.
푸는 방법은 여러가지가 있습니다. 저 같은 경우에는 DFS로 풀었습니다.
먼저 코드를 보겠습니다.

풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

	static int N, T, C;
	static int[][] Map;
	static boolean[][] isgo;

	public static void main(String args[]) throws Exception {

		System.setIn(new FileInputStream("res/달팽이_숫자.txt"));
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();

		for (int test_case = 1; test_case <= T; test_case++) {
			N = sc.nextInt();
			Map = new int[N][N];
			isgo = new boolean[N * 2][N * 2];
			C = N * N;
			Map[0][0] = 1;
			isgo[0][0] = true;
			Solution(0, 0, 2);
			System.out.println("#" + test_case);
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					System.out.print(Map[i][j] + " ");
				}
				System.out.println("");
			}
		}
	}

	private static void Solution(int r, int c, int cnt) {
		if (cnt > C)
			return;
		for (int i = 1; i <= N; i++) {
			if (c + i < N && isgo[r][c + i] == false) {
				Map[r][c + i] = cnt;
				isgo[r][c + i] = true;
				cnt++;
			} else {
				c = c + i - 1;
				break;
			}
		}
		for (int i = 1; i <= N; i++) {
			if (r + i < N && isgo[r + i][c] == false) {
				Map[r + i][c] = cnt;
				isgo[r + i][c] = true;
				cnt++;
			} else {
				r = r + i - 1;
				break;
			}
		}
		for (int i = 1; i <= N; i++) {
			if (c - i >= 0 && isgo[r][c - i] == false) {
				Map[r][c - i] = cnt;
				isgo[r][c - i] = true;
				cnt++;
			} else {
				c = c - i + 1;
				break;
			}
		}
		for (int i = 1; i <= N; i++) {
			if (r - i >= 0 && isgo[r - i][c] == false) {
				Map[r - i][c] = cnt;
				isgo[r - i][c] = true;
				cnt++;
			} else {
				r = r - i + 1;
				break;
			}
		}
		Solution(r, c, cnt);
	}

먼저 test case인 T와 map의 크기인 N, 최댓값인 C, 그리고 이미 간 곳인지 확인하는 boolean 배열, isgo를 선언합니다.
그리고 Solution이라는 이름의 DFS 재귀함수를 호출합니다.

private static void Solution(int r, int c, int cnt) {
	if (cnt > C)
		return;
	for (int i = 1; i <= N; i++) {
		if (c + i < N && isgo[r][c + i] == false) {
			Map[r][c + i] = cnt;
			isgo[r][c + i] = true;
			cnt++;
		} else {
			c = c + i - 1;
			break;
		}
	}
	for (int i = 1; i <= N; i++) {
		if (r + i < N && isgo[r + i][c] == false) {
			Map[r + i][c] = cnt;
			isgo[r + i][c] = true;
			cnt++;
		} else {
			r = r + i - 1;
			break;
		}
	}
	for (int i = 1; i <= N; i++) {
		if (c - i >= 0 && isgo[r][c - i] == false) {
			Map[r][c - i] = cnt;
			isgo[r][c - i] = true;
			cnt++;
		} else {
			c = c - i + 1;
			break;
		}
	}
	for (int i = 1; i <= N; i++) {
		if (r - i >= 0 && isgo[r - i][c] == false) {
			Map[r - i][c] = cnt;
			isgo[r - i][c] = true;
			cnt++;
		} else {
			r = r - i + 1;
			break;
		}
	}
	Solution(r, c, cnt);
}

재귀 함수를 탈출하는 기저 조건은 cnt값이 최댓값인 C보다 커지는 경우입니다.
그다음에는 사이클을 4가지로 잡았습니다.
먼저 오른쪽으로 끝까지 이동하는 것, 그 다음 아래 왼쪽 위 방향으로 순서대로 끝까지 이동하는 것입니다.
사이클을 다 돌면 다시 그 위치에서 재귀함수를 돌립니다.

후기

재귀함수를 제대로 알고 있다면 크게 어렵지는 않은 문제였습니다.
만약 이 문제가 어려웠다면 재귀함수를 다시 한번 학습해보세요.

만약 코드를 다운 받고 싶다면 공유한 깃허브에 접속해주세요.
오류 지적, 질문, 더 나은 풀이는 언제든지 메일이나 댓글로 부탁드립니다.
감사합니다.