[백준_1913번] 달팽이

https://www.acmicpc.net/problem/1913

1913번: 달팽이

[문제]

홀수인 자연수 N이 주어지면, 다음과 같이 1부터 N2까지의 자연수를 달팽이 모양으로 N×N의 표에 채울 수 있다.

9	2	3
8	1	4
7	6	5

 

25	10	11	12	13
24	9	2	3	14
23	8	1	4	15
22	7	6	5	16
21	20	19	18	17

 

 N이 주어졌을 때, 이러한 표를 출력하는 프로그램을 작성하시오. 또한 N2 이하의 자연수가 하나 주어졌을 때, 그 좌표도 함께 출력하시오. 예를 들어 N=5인 경우 6의 좌표는 (4,3)이다.

 

[입력 조건]

첫째 줄에 홀수인 자연수 N(3 ≤ N ≤ 999)이 주어진다. 둘째 줄에는 위치를 찾고자 하는 N2 이하의 자연수가 하나 주어진다.

 

[코드]

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

public class BaekJoon_1913 {
	// n*n 숫자는 시계 반대 방향으로 줄어든다.
	static int[] dx= {1,0,-1,0};
	static int[] dy= {0,1,0,-1};
	public static void main(String[] args) throws Exception {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		StringBuilder sb=new StringBuilder();
		
		int n=Integer.parseInt(st.nextToken());
		
		st=new StringTokenizer(br.readLine());
		int m=Integer.parseInt(st.nextToken());
		
		int[][] arr=new int[n][n];
		int num=n*n; // 배열의 (0,0)은 n*n 부터 시작
		int x=0,y=0,direction=0,px=0,py=0;
		
		while(num>0) {
			int nx=x+dx[direction]; // 다음 좌표 계산
			int ny=y+dy[direction];
			
			/*
			 * 방향이 바뀌는 지점은 배열의 범위를 벗어나거나 
			 * 배열에 이미 값이 들어있는 경우이다. 따라서 다음 좌표를 계산했을 때
			 * 해당 조건에 만족하면 방향을 변경하여 좌표를 계산해야 한다. 
			 */
			if(nx<0||nx>=n||ny>=n||ny<0||arr[nx][ny]!=0) {
				direction++; // 방향 변겅
				if(direction==4)
					direction=0;
				
				// 변경한 방향으로 다시 다음 좌표 계산
				nx=x+dx[direction]; 
				ny=y+dy[direction];
			}
			
			arr[x][y]=num--; // 숫자 저장
			x=nx; // 다음 좌표로 갱신
			y=ny;
		}
		
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++) {
				// m의 값을 갖는 행,열 찾기
				if(arr[i][j]==m) {
					px=i;
					py=j;
				}
				sb.append(arr[i][j]+" ");
			}
			/*
			 * m의 값을 갖는 행,열을 바로 출력하기 위해 
			 * 마지막 행은 줄바꿈을 하지 않는다.
			 */
			if(i==n-1)
				continue;
			sb.append('\n');
		}
		
		System.out.println(sb); // 배열 출력
		System.out.println((px+1)+" "+(py+1)); // m의 위치를 1행, 1열로 바꿔 출력(각 값에 +1하기)
	}

}

 

[고찰]

 이번 문제는 배열의 가운데부터 시계방향으로 숫자를 늘려 채워나가는 문제이다. 배열의 가운데부터 시작하려니 인덱스 계산이 어려워 배열의 (0,0) 부터 시작하였다. 배열의 (0,0)은 n*n 숫자부터 시계 반대방향으로 숫자가 줄어나가는 형태를 띈다.

 다음으로 중요한 것은 언제 방향이 바뀌느냐이다. 다음 좌표가 배열의 범위를 벗어나거나 이미 배열에 값이 저장되있는 경우 방향을 회전해야한다. 따라서 숫자를 저장 후 다음 좌표를 계산했을 때 배열 범위를 벗어나거나, 이미 배열에 값이 저장되 있다면 방향을 바꿔주고 다시 좌표 값을 계산해준다. 

 처음에는 Scanner를 사용하고, 배열 값을 2중 for문을 사용하여 출력해주었는데 시간초과를 받았다. 이를 해결하기 위해 BufferedReader와 StringBuilder를 사용했다.