백준 - 달팽이

문제 출처:www.acmicpc.net/problem/1913

1913번: 달팽이

 

아래와 같은 모양을 구현하기 위해 규칙성을 찾아보기로 하였다. 

 

1. 우선 상 후 하 좌 로 이동.

2. 1칸 채우고 방향 이동 -> 1칸 채우고 방향 이동 -> 2칸 채우고 방향이동 -> 2칸 채우고 방향이동 -> 3칸 채우고 방향이동... 이런식으로 채우는 칸수가 증가

 

규칙을 찾고 의사코드를 만들어보니, 아래와 같이 나오게 되었다.

for(N번)                                                                               ->1

     if(N번째 이전까지)                                                       ->2

           for(가장 외곽의 for문의 인덱스만큼 실행)       ->3

     else(N번쨰)                                                                  ->4

           for(N-1만큼 실행)                                                  ->5

 

3번을 실행하면서 좌표에 값을 넣어주고 현재 좌표값(행, 열)을 갱신한다. 그리고 해당 좌표가 구할려는 값이면 해당 좌표값을 저장한다.

 

 

마지막은 N-1번 만큼 숫자를 증가하면서 같은 방향으로 입력해주면 된다.

 

 

 

전체코드는 아래와 같다.

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


public class B1913_달팽이 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int K = Integer.parseInt(br.readLine());
        int map[][] = new int[N][N];
        int r = N / 2;
        int c = r;

        int dr[] = {-1, 0, 1, 0};
        int dc[] = {0, 1, 0, -1};
        int idx = 1;
        int x = 0;
        int y = 0;
        map[r][c] = idx++;
        int k = 0;//숫자가 넣어지는 방향
        //outer for문은 N번 실행
        for (int i = 1; i <= N; i++) {
            if (i < N) {
                for (int m = 0; m < 2; m++) { //매 idx마다 두번씩 돈다.
                    for (int j = 0; j < i; j++) { //i칸만큼만 이동
                        r = r + dr[k];
                        c = c + dc[k];
                        map[r][c] = idx++;
                        if (map[r][c] == K) {
                            x = r + 1;
                            y = c + 1;
                        }
                    }
                    k++;
                    if (k == 4)
                        k = 0;
                }
            } else {
                for (int j = 0; j < N - 1; j++) {
                    r = r + dr[k];
                    c = c + dc[k];
                    map[r][c] = idx++;
                    if (map[r][c] == K) {
                        x = r + 1;
                        y = c + 1;
                    }
                }
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println(x + " " + y);
    }
}