백준 1913 달팽이 (구현에서의 발상 전환, 반복변수 값은 해당 반복변수를 이용하는 반복문에서만 건들게 설계)

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

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
//6:15
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 n = Integer.parseInt(br.readLine());
        int[] ans = new int[2];
        int[][] matrix = new int[N][N];
        int[][] d = new int[][] {{-1,0}, {0,1},{1,0},{0,-1}};
        int[] loc = new int[] {N/2, N/2};
        matrix[loc[0]][loc[1]] = 1;
        int dIndex=0;
        int i=2;
        int num=2;
        while(num<=N*N) {
            //방향은 d[0][i%2]
            //(i%2)+1 만큼
            for (int j = 1; j <= (i / 2) ; j++) {
                loc[0] = loc[0] + d[(dIndex) % 4][0];
                loc[1] = loc[1] + d[dIndex% 4][1];
                if(isIn(loc[0],loc[1],N)){
                    matrix[loc[0]][loc[1]] = num++;
                }
            }
            i++;
            dIndex++;
        }

        for(int j=0;j<N;j++){
            for(int k=0;k<N;k++){
                if(matrix[j][k]==n){
                    ans[0] = j;
                    ans[1] = k;
                }
                System.out.print(matrix[j][k]+" ");
            }
            System.out.println();
        }
        System.out.println((ans[0]+1)+" "+(ans[1]+1));

    }
    public static boolean isIn(int loc1, int loc2,int N) {
        if(loc1>=0 && loc1<N && loc2>=0 && loc2<N) {
            return true;
        }
        return false;
    }
}

무지막지하게 푼 느낌이다. 딱봐도 이렇게 무지성으로 풀면 안된다.

 

안쪽에서 바깥쪽으로 나가는 방향으로 풀었다.

 

구현에서는 보이는대로 하기보다는 항상 규칙을 찾는 것이 중요하다.

Step By Step으로 보인다하더라도 생각의 전환도 필요하다. 예를 들면 문제에서 1단계 이후 2단계, 3단계... 이렇게 단계별로 진행하는 문제이지만 (1,2)단계 , (3,4)단계... 이런식으로 한번에 처리가 간단하다면 이렇게 가야된다.

 

 

내 풀이도 곧이곧대로  서로 독립적으로 돌아가는 채울 숫자(num) , 위치 , 방향을 전부 변수로 잡아서 하다보니 복잡해졌고 디버깅 또한 불가능했다.

 

이때 발상의 전환으로 방향을 묶어보는 것이 어떨까?

기존에 파란색처럼 하나씩 하던걸 빨간색으로 이동 횟수가 같은것끼리 묶으면 훨씬 수월하게 풀릴 수 있다는 것이다.

하지만 다르게 묶어보면 한번의 사이클은 위 , 오른쪽, 아래, 왼쪽으로 이동하는 것이라서 더 쉽게 풀릴 수 있을 것이다.

 

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++;
}

 이렇게 말이다.

 

명심하자.

반복을 돌때는 해당 반복문 안에서만 반복변수를 변화시키게 설계해야지 중첩 반복문에서 함부로 건들면 오답의 지름길이다.