달팽이 배열 찍기

가끔 2차원 배열 구현 문제에서 달팽이 모양으로 방문순서를 좌표에 찍도록 하는 문제가 있다. 

이러한 문제유형에서 응용된 많은 문제들이 있는데 만날때마다 한숨부터 나왔다. 

 

4방향의 범위를 오차없이 생각해내는 것부터 헷갈리고 가끔 한끝차이로 오류가 날떄는 

그걸 찾느라 많은 시간을 보냈다. 어려운건 아니지만 실수를 많이 유발하는 유형이었다. 

 

그래서 구글링을 해봤고 그 중 가장 헷갈리지 않는 방법을 찾았다!!

 

 

 

2차원 배열의 가로 세로 크기 입력 -> 그 모양에 맞게 달팽이 배열 만들기 

 

내가 생각했을때 가장 쉬운 방법은 방향을 나타내는 배열을 이용하는 사방탐색의 방법을 응용하는것이다. 

이 아이디어는 다음과 같다. 

 

만약 아래 그림과 같이 방문순서대로 숫자를 배열에 입력후 출력해야 한다고 가정해보자. 

 

예시배열 (가로5, 세로5)

 

 

사방탐색의 아이디어를 이용해 다음 2차원 좌표를 각각 (int nexti = nowi + di[d],  int nextj = nowj + dj[d])

라고 선언하고 배열 범위내에 있는지 탐색을 한다. 초기값은 시작지점에서 지금 방향의 역방향으로 한칸 이동한 좌표 이다. 즉, 지금 같은 경우는 (0,0)에서부터 수를 입력할것이라면 (0,-1)에서 시작하고 (0, 0)을 탐색하는 것이다.

이를 그림으로 나타내면 다음과 같다. 

 

왼쪽에 있는 now와 next를 보자 초기값은 (시작지점 - 처음 이동방향의 역방향으로 1칸)이므로 now좌표는 (0, -1)이다.

next는 지금방향으로 한칸 이동했으므로 (0, 0)이다. 이 좌표는 범위내에도 있고 방문한적도없다. 

그럼 이 좌표위치에 숫자를 입력해주고 방문처리를 해준다.

 

 

이제 다음 좌표를 탐색해야하므로 next위치의 2차원 좌표를 now위치의 2차원 좌표 변수에 각각 입력해준다. 

그리고 next좌표는 방향을 유지한채 한칸 더 나아가 탐색을 한다. 이런식으로 한줄을 쭉 나아가게 된다. 

 

 

그럼 방향은 도대체 언제 바꿔야하는것일까?

next의 좌표 조건을 검사할때 1. 방문을 한적이 있는경우, 2. 좌표의 범위를 벗어나는경우 이렇게 2가지 경우가 있다. 

위 그림에서 오른쪽 now, next의 관계가 그 예라고 할수있는데 이런경우 next의 좌표를 now 좌표에 대입하지말고 

방향만 바꿔주어 now좌표는 유지한채 다른 곳의 next를 탐색해야한다. 

 

 

또 이렇게 쭉 탐색을 하다보면 이번엔 방문을 했던곳을 만나 오류를 발생시킨다. 다음그림을 보자.

다음과 같이 범위를 벗어날때마다 방향을 바꿔가며 숫자를 입력해오다가 위와같은 상황에서 오류가 발생한다. 

즉, 그림에서 (0,0)의 좌표는 처음으로 방문을 한곳이므로 next1의 위치에서 방문여부검사를 할때 조건을 통과하지 

못하는데 이때 또 방향을 바꾸는것이다. 따라서 next1의 위치는 넘어가고 방향을 바꿔 next2의 위치로 이동하게 되는것이다.

 

 

 

다음과 같이 총 2가지 조건을 통해 달팽이 배열을 찍을 수 있는데 코드로 확인해보자.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class 달팽이배열연습_좌표2개로 {
	static int[] di = {-1, 0, 1, 0};			//사방탐색에 쓰일 배열
	static int[] dj = {0, 1, 0, -1};
	
	static int sero; 							//입력으로 받을 가로 세로 변수
	static int garo; 
		
	static int[][] arr;							// 달팽이 모양으로 수를 입력할 배열
	static int[][] visit;						// 달팽이 모양으로 돌때 필요한 탐색처리 배열
	
	static boolean check(int i, int j) {				// 범위 체크 배열
		if(0<=i&&i<sero && 0<=j&&j<garo)return true;
		return false;
	}
	
	static void turn(int starti, int startj) {			// 달팽이 모양으로 찍는 함수 
		
		int nowi = starti; int nowj = startj;			// 2차원 시작좌표
		int cnt = 1;
		int d = 0;
		
		while(cnt<=sero*garo) {							// 순서대로 입력할 숫자 = cnt
			
			int ni = nowi+di[d];						// 지금 방향을 유지했을때 다음 좌표들 
			int nj = nowj+dj[d];
			
			if(check(ni, nj) && visit[ni][nj]==0) {		// 만약 지금 방향을 유지했을때 범위안에 있고 방문하지 않았다면~
				nowi = ni; nowj = nj;
				arr[nowi][nowj] = cnt++;
				visit[nowi][nowj] = 1;
			}else {										// 방문을 했거나 좌표범위를 벗어난다면 
				d = (d+1)%4;							// 탐색 방향을 바꿔줘라
			}
		}
	}
	
	public static void main(String[] args) throws Exception{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer ST =new StringTokenizer(br.readLine());
		
		sero = Integer.parseInt(ST.nextToken());
		garo = Integer.parseInt(ST.nextToken());					//가로 세로 입력 받기 
		
		arr = new int[sero][garo];
		visit = new int[sero][garo];
		for(int[] tmp: arr)System.out.println(Arrays.toString(tmp));
		System.out.println();
		
		turn(0, -1);												// 시작 좌표 
			
		for(int[] tmp: arr)System.out.println(Arrays.toString(tmp));
	}
}