https://swexpertacademy.com/main/solvingProblem/solvingProblem.do
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
델타 탐색을 이용하여 풀어본다.
숫자가 시계방향으로 이루어져 있으므로,
탐색 방향은 (오른쪽, 아래, 왼쪽, 위) 순서대로 반복될 것이다.
아래 N = 4일 경우, 달팽이의 모습을 보자.
| 1 | 2 | 3 | 4 |
| 12 | 13 | 14 | 5 |
| 11 | 16 | 15 | 6 |
| 10 | 9 | 8 | 7 |
N*N의 2차원 배열에서 원소 1이 존재하는 위치를 기준으로 탐색해나가면서 숫자를 입력해줘야 하는데,
중요하게 생각할 포인트는 "언제 방향을 바꾸는가" 이다.
처음 위치부터 생각해보자. 처음 위치(배열의 [0][0] 위치)에 1을 지정하고 시작하도록 한다.
처음위치에서는 아래 화살표 방향과 같이 오른쪽으로 탐색해 나가면서 숫자를 1씩 더해 입력한다.
그런데, 아래와 같이 4까지 입력하고 나면, 5를 입력하기 위해서는 탐색 방향을 오른쪽이 아닌 아래 방향으로 바꾸어야 한다.
일단 어떤 조건을 통해 방향을 바꾸었다고 가정하고, 진행해보면서 어느 지점에서 방향이 바뀌어야 하는지 살펴보면,
1. 같은 방향으로 탐색시 다음 차례에서 배열의 범위를 벗어날 때,
2. 같은 방향으로 탐색시 다음 차례에 숫자가 존재할 때, (다음 차례에 숫자가 존재한다는 것을 어떻게 처리?)
이제, 각 조건에 대해 어떻게 코드를 작성할지 살펴보자.
1번 조건에 대해서는 다음 탐색 위치(인덱스)가 0이상이고 N-1을 초과하면 안되므로, 인덱스 값이 N보다 작아야 한다는 조건을 이용하도록 한다.
2번 조건에 대해서는 다음 탐색 위치에 숫자가 존재한다는 조건을 달기 위해 그 위치의 값이 0이면 방향을 바꾸어야 한다는 조건을 이용한다.(왜냐하면 int배열을 생성하면 기본적으로 원소들이 0이기 때문이다)
아래 코드와 주석을 살펴보자.
|
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
|
import java.util.Scanner;
public 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[][] snail = new int[N][N];
int[] dr = { 0, 1, 0, -1 };
int[] dc = { 1, 0, -1, 0 }; // 우 하 좌 상
int n = 0; // dr, dc의 index 역할
int row = 0; // 현재 행 인덱스
int col = 0; // 현재 열 인덱쇼
snail[0][0] = 1; // 처음 위치 값 1 지정
int w = 1;
//총 N-1번 탐색
while (w < N * N) {
int nr = row + dr[n]; //이동 후 행 인덱스
int nc = col + dc[n]; //이동 후 열 인덱스
//nr, nc가 0이상 N-1이하여야 인덱스 범위 초과하지 않고,
//다음 위치에 0이 존재해야 방향을 유지한다.
if (nr >= 0 && nr < N && nc < N && nc >= 0 && snail[nr][nc] == 0) {
snail[nr][nc] = ++w; //이전의 w값보다 하나 증가된 w를 대입하고, w 자신도 1증가
row = nr;
col = nc;
} else {
n = (n + 1) % 4; //4가지의 방향이 있으므로 4로 나눈 나머지를 이용해 돌린다.
}
}
System.out.println("#" + tc);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(snail[i][j] + " ");
}
System.out.println();
}
}
}
}
|
cs |
'알고리즘 및 코테 > SWEA' 카테고리의 다른 글
| SWEA 11315. 오목 판정(Java) (0) | 2023.01.12 |
|---|---|
| SWEA 2805. 농작물 수확하기(Java) (0) | 2023.01.12 |
| SWEA 1204. [S/W 문제해결 기본] 1일차 - 최빈수 구하기 - Java (0) | 2023.01.10 |
| SWEA 1984. 중간 평균값 구하기(Java) (2) | 2023.01.10 |
| SWEA 1966. 숫자를 정렬하자(Java) (2) | 2023.01.10 |