알고리즘 (6월 13일) - (3)

1. 문제 (코딩도장, 나선형 배열의 거리)

https://codingdojang.com/scode/679

코딩도장

---

2. 생각

 

숫자 N(1 <= N <= 109)을 입력받아서 1부터 N까지 가는 최단거리를 계산하는 프로그램을 작성하세요. (상, 하, 좌, 우로만 움직일 수 있고 대각선으로는 움직일 수 없다.)

 

1. 배열의 사이즈(m:row, n:column) 입력 받기
2. m by n 사이즈 배열 생성
3. while문과 switch-case문을 이용하여 나선형 형태로 배열의 원소값 대입
4. 알고 싶은 자연수 N값을 입력 받기
5. 배열의 (1, 1)을 기준으로 1의 위치값(x, y)과 N의 위치값(x,y) 찾기
6. Math.abs(N의 위치값(x,y) - 1의 위치값(x, y) 의 결과값) = 1부터 N까지 가는 최단거리
7. 1부터 N까지 가는 최단거리 결과 출력

 

---

3. 풀이 및 코드 분석

import java.util.Scanner;

public class test {
	public static void paintingArray(int[][] result, int m, int n) {
		for(int i=0; i<m; i++) {
			for(int j=0; j<n; j++) {
				System.out.printf("%3d", result[i][j]);
			}
			System.out.println();
		}
	}
	
	public static int[] findPosition(int[][] result, int Number) {
		int[] position = new int[2];
		
		for(int i=0; i<result.length; i++) {
			for(int j=0; j<result[0].length; j++) {
				if(result[i][j]==Number) {
					position[0] = j;
					position[1] = i;
				}
			}
		}
		
		return position;
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		// 배열 사이즈 입력
		System.out.print("배열의 사이즈를 입력(m:row, n:column):");
		int m = scan.nextInt();
		int n = scan.nextInt();
		
		// 배열 초기화
		int result[][] = new int[m][n];
		
		// 배열 원소 압력
		int element = m*n, direction=0, row=0, column=0;
		
		while(element>0) {
			switch(direction) {
			case 0:
				for(int j=column; j<n-1-column; j++) {
					result[row][j] = element;
					element--;
				}
				direction++;
				break;
			case 1:
				for(int i=row; i<m-1-row; i++) {
					result[i][n-1-column] = element;
					element--;
				}
				direction++;
				break;
			case 2:
				for(int j=n-1-column; j>column; j--) {
					result[m-1-row][j] = element;
					element--;
				}
				direction++;
				break;
			case 3:
				for(int i=m-1-row; i>row; i--) {
					result[i][column] = element;
					element--;
				}
				direction=0;
				column++;
				row++;
				break;
			}
		}
		
		// 결과 출력
		paintingArray(result, m, n);	

		// position of zero
		int[] zeroPosition = findPosition(result, 1);
		
		// 자연수 N 입력
		System.out.print("\n최단거리를 계산하고 싶은 N을 입력:");
		int N = scan.nextInt();
		
		// position of N
		int[] NPosition = findPosition(result, N);
		
		//distance 계산
		int distance = 0;
		for(int i=0; i<2; i++) {
			distance += Math.abs(zeroPosition[i] - NPosition[i]);
		}
		System.out.printf("1부터 %d까지 가는 최단거리 : %d", N, distance);
	}
}