[Implementation] boj 1913 달뱅이 - 백준 자바

달팽이 성공

 

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

128 MB

6708

3059

2405

53.184%

문제

홀수인 자연수 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 이하의 자연수가 하나 주어진다.

출력

N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 출력한다.

예제 입력 1 복사

7 35

예제 출력 1 복사

49 26 27 28 29 30 31 48 25 10 11 12 13 32 47 24 9 2 3 14 33 46 23 8 1 4 15 34 45 22 7 6 5 16 35 44 21 20 19 18 17 36 43 42 41 40 39 38 37 5 7

 

[문제풀이 생각]

이 문제는 1부터 N까지의 수를 달팽이 방향(반시계방향)으로 돌려가며 맵을 채워간다.

어떻게 이동을 해 줘야할 까 생각하다, 벽을 타고 이동한다고 생각을 했다.

현재 위치(첫 위치) 1은 맵의 중심부터 시작하며, 방향은 직진 아니면, 오른쪽 꺽는 2가지만 생각한다.

1. 먼저 직진한다. (북 방향)

2. 직진한 후 현재 방향에서 오른쪽이 비어있으면 (0)이면 오른쪽으로 방향을 꺽는다.

3. 오른쪽이 채워져있으면, 그 방향 그대로 직진한다.

4. 방향은 직진을 기준으로(처음을 기준으로) 반시계 방향 [ 북, 동, 남, 서] 로 이동한다.

 

1~4번까지 number 가 n에 도달할때까지 반복한다.

 

package implementation;

import java.io.BufferedReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//직진 아니면 오른쪽 회전 ^ > 
//처음에 직진 -> if(오른쪽 칸이 비어있으면) 방향 오른쪽 회전
public class boj1913_달팽이 {
	
	static int n;
	static int number;
	static int map[][];
	
	//북 동 남 서
	static int dx[] = {-1,0,1,0};
	static int dy[] = {0,1,0,-1};
	static int direction = 0;
	static int result[] = new int[2];
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		n = Integer.parseInt(br.readLine());
		number = Integer.parseInt(br.readLine());
		map = new int[n][n];
		
		//1의 좌표
		int x = n/2;
		int y = n/2;
		
		int now =1;
		map[x][y] = now++;
		
		if(number == 1) {
			result[0] = x+1;
			result[1] = y+1;
		}
		while(now != (n*n)+1) {
			//직진
			x = x+dx[direction];
			y = y+dy[direction];
			
			if(now == number) {
				result[0] = x+1;
				result[1] = y+1;
			}
			map[x][y] = now++;
			
			//오른쪽 비어있는지 확인 -> 방향 전환
			int tdirection = direction+1>3 ? 0 : direction+1;
			
			int tx = x+dx[tdirection];
			int ty = y+dy[tdirection];
			if(map[tx][ty]==0) {
				direction+=1;
				if(direction>3)
					direction=0;
			}
			
		}
		
		//output
		for(int i=0;i<n;i++) {
			for(int j=0;j<n-1;j++) {
				sb.append(map[i][j]+" ");
			}
			sb.append(map[i][n-1]+"\n");
		}
		
		sb.append(result[0]+" "+result[1]);
		
		System.out.print(sb.toString());
	}

}