https://www.acmicpc.net/problem/1913
풀이
규칙을 찾기 위해 위 그림과 같이 N=3, N=5인 경우 한 방향으로 이동할 때 이동하는 칸 수를 셌다.
ex)
1 -> 2 : 1
2 -> 3 : 1
3 -> 5 : 2
N = 3 : 1 1 2 2 2
N = 5 : 1 1 2 2 3 3 4 4 41 2번, 2 2번,..., (N-1) 3번이다.
위 규칙을 활용하여 문제를 풀었다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int k = Integer.parseInt(br.readLine());
int[][] arr = new int[n][n];
int i = n/2, j = n/2; //배열 인덱스
int dir = 0; //방향 인덱스
int num = 1; // 배열에 저장할 숫자
int cnt = 0; // 현재 line 으로 총 2번 이동했는지 카운트
int line = 1; // 이동해야 하는 칸 수
int move = 0; // 현재 이동한 칸 수
int xIdx = 0, yIdx = 0; //정답 인덱스
while(num <= n*n) {
move = 0;
while (move < line) {
arr[i][j] = num;
if (num == k) {
xIdx = i;
yIdx = j;
}
num++;
i += dx[dir];
j += dy[dir];
move++;
}
cnt++;
dir = (dir+1) % 4; // 방향 변환
// 이동하는 칸 수가 N-1일 경우 총 3번을 이동해야 하기 때문에 따로 처리
if (line == n-1) {
if (cnt == 3) {
break;
}
}
// 현재 line으로 2번 이동했으면 이동하는 칸 수 증가
else if (cnt >= 2) {
line++;
cnt = 0;
}
}
arr[0][0] = num;
xIdx++;
yIdx++;
StringBuilder sb = new StringBuilder();
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
sb.append(arr[i][j] + " ");
sb.append("\n");
}
sb.append(xIdx + " " + yIdx);
System.out.println(sb);
}
}- 방향 배열을 정의하여 행 인덱스
i에는dx[dir]을 더하고 열 인덱스j에는dy[dir]을 더한다.
주의
- 로직 순서: 배열에 숫자를 저장 -> 이동하기 때문에 마지막 숫자(n*n)를 배열에 따로 저장하는 코드가 있어야 한다.
arr[0][0] = num; xIdx,yIdx는 0부터 시작하므로 각각 1을 더해야 한다.
xIdx++;
yIdx++;- 위치를 찾고자 하는 자연수가 n*n일 수 있으므로
xIdx,yIdx모두 0으로 초기화한다.
다른 풀이 2
위 방법과 같이 안쪽에서 바깥쪽으로 배열을 채워나가며, 이동하는 칸의 횟수가 1 > 1 > 2 > 2 > 3 > 3> 4 > ... > n 씩 이동하는 것을 활용하여 구현한다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
int[][] arr = new int[n][n];
int i = n/2, j = n/2; //배열 인덱스
int num = 1; // 배열에 저장할 숫자
int line = 1; // 이동해야 하는 칸 수
int xIdx = 0, yIdx = 0; //정답 인덱스
while(true) {
for (int k = 0; k < line; k++) {
if (num == m) {
xIdx = i;
yIdx = j;
}
arr[i--][j] = num++;
}
// 배열을 다 채웠으면 이 때 num = n*n + 1
if (num > n*n)
break;
for (int k = 0; k < line; k++) {
if (num == m) {
xIdx = i;
yIdx = j;
}
arr[i][j++] = num++;
}
line++;
for (int k = 0; k < line; k++) {
if (num == m) {
xIdx = i;
yIdx = j;
}
arr[i++][j] = num++;
}
for (int k = 0; k < line; k++) {
if (num == m) {
xIdx = i;
yIdx = j;
}
arr[i][j--] = num++;
}
line++;
}
xIdx++;
yIdx++;
StringBuilder sb = new StringBuilder();
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
sb.append(arr[i][j] + " ");
sb.append("\n");
}
sb.append(xIdx + " " + yIdx);
System.out.println(sb);
}
}- 이동 방향은 모든 경우에 대해 항상 같으므로 방향 배열이 필요 없다.
- 두 번의 반복문을 수행하면 이동하는 칸의 횟수가 늘어나므로 두번째, 네번째 반복문 다음에
line++ arr[0][0]까지 배열을 다 채웠으면 이 때num = n*n + 1이 되므로 반복문을 종료해야 한다.
마지막 반복문 (N = 5)
num = 21 -> 22 -> 23 -> 24 -> 25 -> 참고: https://loosie.tistory.com/538
다른 풀이 3
위 방법들과 다르게 바깥쪽에서 안쪽으로 배열을 채워나간다.
import java.io.*;
import java.util.*;
public class Main {
static int[] dx = {1, 0, -1, 0};
static int[] dy = {0, 1, 0, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
int[][] arr = new int[n][n];
int i = 0, j = 0; // 배열 인덱스
int num = n * n; // 배열에 저장할 숫자
int dir = 0; // 방향 인덱스
int xIdx = 0, yIdx = 0; //정답 인덱스
while(num > 0) {
if (num == m) {
xIdx = i+1;
yIdx = j+1;
}
arr[i][j] = num--;
i += dx[dir];
j += dy[dir];
if (i < 0 || j < 0 || i >= n || j >= n || arr[i][j] != 0 ) {
// 이전 위치로 복구
i -= dx[dir];
j -= dy[dir];
dir = (dir + 1) % 4; // 뱡향 변환
// 바뀐 방향으로 이동
i += dx[dir];
j += dy[dir];
}
}
StringBuilder sb = new StringBuilder();
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
sb.append(arr[i][j] + " ");
sb.append("\n");
}
sb.append(xIdx + " " + yIdx);
System.out.println(sb);
}
}i < 0 || j < 0 || i >= n || j >= n || arr[i][j] != 0
이동한 위치가 배열의 인덱스 밖이거나, 이미 배열에 값이 채워져있다면 이전 위치로 복구한 다음 새로운 방향으로 이동한다.
참고: https://bbangson.tistory.com/110
- 바깥쪽에서 안쪽으로 배열을 채워나가는 3번째 방법이 제일 코드가 깔끔하고 가독성이 높다.
