[BOJ] 백준 1913번 달팽이 (Java)

#1913 달팽이

난이도 : 실버 5

유형 : 구현

1913번: 달팽이

▸ 문제

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

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

▸ 입력

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

▸ 출력

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

 

문제 풀이  

특정 알고리즘에 대한 지식보다는 단순 구현 능력이 중요한 문제이다. 달팽이를 바깥에서 안쪽으로 도는 방법과 안쪽에서 바깥쪽으로 도는 방법이 있다. 둘 다 구현해보니 홀수로만 이루어진 표는 안쪽에서 바깥쪽으로 도는 방법이 훨씬 간단했다.

탐색 방법

바깥쪽에서 안쪽으로

(0,0)은 항상 n*n의 값이 들어간다.  n > n-1 > n-1 > n-2로 겉면을 도는 것이 한 싸이클이고, 한 싸이클마다 둘러싸는 사각형의 크기가 n-2씩 줄어들기 떄문에 이에 맞게 값을 조정하여 탐색해주면 된다.

int[][] map = new int[n][n];
int value = n*n;
int x = 0,y = 0;
int time = 0;
int limit = n;
while(value>0) {
	x=time;
	for(int i=y; i<limit; i++) {
		map[i][x] = value--;
	}
	
	y=limit-1;
	for(int i=x+1; i<limit; i++) {
		map[y][i] = value--;
	}
	
	x=limit-1;
	for(int i=y-1; i>=time; i--) {
		map[i][x] = value--;
	}
	
	y=time;
	for(int i=x-1; i>time; i--) {
		map[y][i] = value--;
	}
	time++;
	limit--;
	y=time;
}

 

 

안쪽에서 바깥쪽으로

1이 들어가는 좌표는 항상 (2/n, 2/n)이다. 이를 이용하면 바깥쪽으로 돌면서 움직이는 칸의 횟수가 1 > 1 > 2 > 2 > 3 > 3> 4 > ... > n 씩 이동하는 것을 알 수 있다. 이를 반복문을 통해 구현해주면 된다.

int[][] map = new int[n][n];
int value =1;

int x = n/2, y=n/2;

int limit =1;
while(true) {
	for(int i=0; i<limit; i++) {
		map[y--][x] = value++;
	}
	if(value-1 == n*n) break;
	for(int i=0; i<limit; i++) {
		map[y][x++] = value++;
	}
	
	limit++;
	for(int i=0; i<limit; i++) {
		map[y++][x] = value++;
	}
	
	for(int i=0; i<limit; i++) {
		map[y][x--] = value++;
	}
	limit++;
}

 

풀이 코드 

import java.io.*;

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 t = Integer.parseInt(br.readLine());
		solve1(n,t); // 바깥쪽에서 안쪽
		solve2(n,t); // 안쪽에서 바깥쪽
		
	}

	// 바깥쪽에서 안쪽으로 돌기
	static void solve1(int n, int t) {
		int[][] map = new int[n][n];
		int value = n*n;
		int x=0,y=0;
		int time=0;
		int limit =n;
		while(value>0) {
			x=time;
			for(int i=y; i<limit; i++) {
				map[i][x] = value--;
			}
			
			y=limit-1;
			for(int i=x+1; i<limit; i++) {
				map[y][i] = value--;
			}
			
			x=limit-1;
			for(int i=y-1; i>=time; i--) {
				map[i][x] = value--;
			}
			
			y=time;
			for(int i=x-1; i>time; i--) {
				map[y][i] = value--;
			}
			time++;
			limit--;
			y=time;
		}
		
		StringBuilder sb = new StringBuilder();
		int tx=0, ty=0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(t==map[i][j]) {
					ty=i+1;
					tx=j+1;
				}
				sb.append(map[i][j] +" ");
			}
			sb.append("\n");
		}
		sb.append(ty+" "+tx);
		System.out.println(sb.toString());
	}

	// 안쪽에서 바깥쪽으로 돌기
	static void solve2(int n, int t){
		int[][] map = new int[n][n];
		int value =1;
		
		int x = n/2, y=n/2;
		
		int limit =1;
		while(true) {
			for(int i=0; i<limit; i++) {
				map[y--][x] = value++;
			}
			if(value-1 == n*n) break;
			for(int i=0; i<limit; i++) {
				map[y][x++] = value++;
			}
			
			limit++;
			for(int i=0; i<limit; i++) {
				map[y++][x] = value++;
			}
			
			for(int i=0; i<limit; i++) {
				map[y][x--] = value++;
			}
			limit++;
		}
		
		StringBuilder sb = new StringBuilder();
		int tx=0, ty=0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(t==map[i][j]) {
					ty=i+1;
					tx=j+1;
				}
				sb.append(map[i][j] +" ");
			}
			sb.append("\n");
		}
		sb.append(ty+" "+tx);
		System.out.println(sb.toString());
	}
	
}