[BOJ] 달팽이(1913), 나선형 배열_Java

문제 설명

문제 접근

문제는 중앙부터 시작해서 나선형으로 배열을 순회하면서 작성하는 것

저는 왼쪽 위(0, 0) 지점에서 시작하는게 편해서 숫자를 거꾸로 돌렸습니다.

숫자판

이런 숫자 배열을 만들어야한다고 하면

시작

빨간 지점 즉, (-1, 0) 에서 시작한다고 가정합니다.

이동

아래 방향으로 3번

오른쪽 방향으로 2번

윗 방향으로 2번

왼쪽 방향으로 1번

다시 아래방향으로 1번

이러한 과정을 거쳐서 좌표가 이동하게 됩니다.

여기서 패턴을 찾아보면 첫 1회를 제외하고 같은 이동 횟수는 2번씩 나타납니다.

한번 이동할땐 좌표는 y 혹은 x가 1씩 증가 감소 하게 됩니다.

// 초기 좌표를 (-1, 0) 이라고 가정하면 (col, row)
for(int i = 0; i<이동횟수; i++) {
	col += 1;
}

이러한 반복문을 사용하게 됩니다.

이제 고려해야 할것은

이동 횟수 | 좌표에 더해지는 수 | for문이 반복될 횟수

이렇게 3가지가 됩니다.

문제 풀이

이동

다시 그림을 보게되면

증감의 변화는 1, 2 변화 3, 4 변화 ....

이런식으로 양수와 음수가 번갈아 나옵니다.

이동 횟수의 변화는 1 변화 2 3 변화 4 5 .....

첫 1회를 제외하고 2회마다 번갈아 나옵니다.

이를 토대로 구현을 해보게 되면

// 가로 길이를 3 이라 가정
// 초기 좌표를 (-1, 0) 이라고 가정하면 (col, row)

// 달팽이 배열
int[][] 달팽이배열 = new int[3][3];
// 초기 좌표 설정
int col = -1;
int row = 0;
// 그외 변수 설정
변화량 = 1;
이동횟수 = 3;
그려질숫자 = 가로길이*가로길이;

// ============= 반복되는 블럭 ==================

for(int i = 0; i<이동횟수; i++) {
	col += 변화량;
    달팽이배열[col][row] = 그려질숫자;
    그려질숫자--;
}

이동횟수 -= 1;

for(int i = 0; i<이동횟수; i++) {
	row += 변화량;
    달팽이배열[col][row] = 그려질숫자;
    그려질숫자--;
}

변화량 = -변화량;

// =============================================

이런 형식을 그려볼 수 있습니다.

이동 횟수 | 좌표에 더해지는 수 | for문이 반복될 횟수

이제 for문이 반복될 횟수 만 남았습니다.

일단 예측하기 쉽지 않습니다. 그래서 while문을 써야할거 같아요.

근데 종료조건은 확실해요. [그려질 숫자]가 0이 되면 끝나야 하죠.

여기서 의문점은 2개의 for문 사이에서 끝날 수 있지 않나... 하는 의문이 들수도 있습니다.

하지만 몇번 손으로 그려보다보면 무조건 [이동횟수]가 0 이되면 달팽이 배열은 다 그려진 상태가 됩니다.

또한 [이동횟수]가 0 이란것은 for문에 돌지 않는다는 것을 의미합니다.

이 생각을 구현하면

// 가로 길이를 3 이라 가정
// 초기 좌표를 (-1, 0) 이라고 가정하면 (col, row)

// 달팽이 배열
int[][] 달팽이배열 = new int[3][3];
// 초기 좌표 설정
int col = -1;
int row = 0;
// 그외 변수 설정
변화량 = 1;
이동횟수 = 3;
그려질숫자 = 가로길이*가로길이;

while(그려질숫자 != 0) {
    for(int i = 0; i<이동횟수; i++) {
        col += 변화량;
        달팽이배열[col][row] = 그려질숫자;
        그려질숫자--;
    }

    이동횟수 -= 1;

    for(int i = 0; i<이동횟수; i++) {
        row += 변화량;
        달팽이배열[col][row] = 그려질숫자;
        그려질숫자--;
    }

    변화량 = -변화량;
}

이런 코드가 구현됩니다.

그럼 저희는

달팽이배열

배열을 완성 했습니다.

문제에서는 배열 전체를 출력하고, 특정 숫자의 위치를 찾아달라고 합니다.

그럼 탐색하는건데 결국 2중 for문을 통해 출력을 할거면

해당 숫자가 나올때 그 좌표값을 저장해두고 배열 출력이 끝나면 좌표를 출력하면 됩니다.

// 가로 길이를 3 이라 가정
// 초기 좌표를 (-1, 0) 이라고 가정하면 (col, row)

// 달팽이 배열
int[][] 달팽이배열 = new int[3][3];
// 초기 좌표 설정
int col = -1;
int row = 0;
// 그외 변수 설정
변화량 = 1;
이동횟수 = 3;
그려질숫자 = 가로길이*가로길이;

while(그려질숫자 != 0) {
    for(int i = 0; i<이동횟수; i++) {
        col += 변화량;
        달팽이배열[col][row] = 그려질숫자;
        그려질숫자--;
    }

    이동횟수 -= 1;

    for(int i = 0; i<이동횟수; i++) {
        row += 변화량;
        달팽이배열[col][row] = 그려질숫자;
        그려질숫자--;
    }

    변화량 = -변화량;
}
// 출력하며 타겟숫자 찾기
int ty, tx;
for(int i = 0; i<3; i++) {
	for(int j = 0; j<3; j++) {
    	System.out.print(달팽이배열[i][j] + " ");
    	if (달팽이배열[i][j] == 타겟숫자) {
        	ty = i;
            tx = j;
        }
    }
    System.out.println();
}
System.out.println(ty + " " + tx);

이렇게 코드를 작성하면 해당 문제는 해결이 됩니다.

하지만.... 시간초과 납니다.

버퍼리더 및 버퍼라이터 써야합니다.....

현재까지의 코드만 이해해도 괜찮습니다. 논리를 이해하고 구현할 수 있다는게 중요니까!!

 

해답 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 시간초과 이슈로 버퍼리더 라이터 사용
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int target = Integer.parseInt(br.readLine());

        // 배열을 그릴 공배열 생성
        int[][] nail = new int[n][n];
        int cnt = n * n, move = n;
        // 방향에 더하고 빼줄 상수이자 변수
        int d = 1;
        // 초기 위치
        int y = -1, x = 0;
        // 0이면 끝나게
        while (cnt != 0) {
            // 2번마다 이동 횟수가 바뀌니까 배열 2개를 두었습니다.
            for (int i = 0; i < move; i++) {
                // 좌표 이동
                y += d;
                nail[y][x] = cnt;
                cnt--;
            }
            // 이동횟수 빼기
            move--;
            // 위 for문과 동일
            for (int i = 0; i < move; i++) {
                x += d;
                nail[y][x] = cnt;
                cnt--;
            }
            // 방향의 결 자체가 달라짐
            d = -d;
        }
        // 타겟 위치를 기록
        int ty = 1, tx = 1;

        for (int col = 0; col < n; col++) {
            for (int row = 0; row < n; row++) {
                // 타겟 위치 찾기
                if (nail[col][row] == target) {
                    ty = col + 1;
                    tx = row + 1;
                }
                bw.write(nail[col][row] + " ");
            }
            bw.newLine();
        }
        bw.write(ty + " " + tx);
        bw.flush();
        bw.close();
    }
}