[백준 1022번] 소용돌이 예쁘게 출력하기

문제 링크: 1022번 소용돌이 예쁘게 출력하기

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

 

r1, c1, r2, c2의 범위를 고려하면 일단 10001 * 10001개, 즉 대략 1억 개를 배열에 채워넣는 것으로서 시간복잡도에서는 문제가 없습니다. 다만 제출해보니 메모리 초과가 뜨는데요, 여기서 불필요한 메모리는 실제로 출력되지 않아도 될 부분입니다.

일단 배열을 채울 텐데요, 가상 배열의 (5000, 5000)이 문제 배열의 (0, 0)에 해당합니다. 즉 코드에서 r, c는 가상 배열 좌표인데요, 이를 문제 배열 좌표로 바꿀 때에는 5000을 빼면 됩니다.

(5000, 5000)에서 출발해서 소용돌이 모양으로 가상 배열을 순회하되, 문제 배열 좌표가 (r₁, c₁)과 (r₂, c₂) 사이에 있을 때에는 출력 배열에 저장합니다. 출력 배열은 문제 배열의 일부의 좌상단을 (0, 0)으로 맞춘 것이므로 r1, c1을 빼주면 됩니다.

말로 하면 헷갈리는데 그림으로 보면 쉽습니다.

 

아래는 -3 ≤ r1, c1, r2, c2 ≤ 3이고 r1 = -1, c1 = -2, r2 = 2, c2 = 0일 때 좌표가 변환되는 모습을 그려본 것입니다. 전체 배열의 일부를 표시할 때, 문제 배열과 달리 가상 배열은 값의 범위에 따라서 달라집니다. 왜냐하면 -5000 ≤ r1, c1, r2, c2 ≤ 5000일 때에는 1이 아래에서와 같이 (3, 3)에 있는 것이 아니라, (5000, 5000)에 있을 테니까요.

 

 

import java.io.*;
import java.util.*;
import static java.lang.Math.max;
import static java.lang.Math.log10;

public class Main {
    static int[] dr = {0, -1, 0, 1};
    static int[] dc = {1, 0, -1, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int r1 = Integer.parseInt(st.nextToken());
        int c1 = Integer.parseInt(st.nextToken());
        int r2 = Integer.parseInt(st.nextToken());
        int c2 = Integer.parseInt(st.nextToken());

        int[][] b = new int[r2 - r1 + 1][c2 - c1 + 1];
        int r = 5000; int c = 5000;
        int n = 1;
        int s = 1;
        int d = 0;

        int ml = 0;

        outer:
        while (true) {
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < s; j++) {
                    if (r1 <= r - 5000 && r - 5000 <= r2 && c1 <= c - 5000 && c - 5000 <= c2) {
                        b[r - 5000 - r1][c - 5000 - c1] = n;
                        ml = max(ml, (int)log10(n) + 1);
                    }
                    n++;
                    if (n > 100020001) break outer;
                    r += dr[d]; c += dc[d];
                }
                d = (d + 1) % 4;
            }
            s++;
        }

        for (int i = 0; i < r2 - r1 + 1; i++) {
            for (int j = 0; j < c2 - c1 + 1; j++) {
                System.out.printf("%" + ml + "d ", b[i][j]);
            }
            System.out.println();
        }
    }
}