[백준(JAVA)] 1913번: 달팽이

문제

✔ 난이도 - Silver 3

설명1

N * N 개의 이차원 배열 만들고
[0][0] 부터 시작 -> N * N 수 부터 시작하면서 최종 1일때까지 -- 해나갈건데
아래 -> 오른쪽 -> 위 -> 왼쪽 방향순으로 반복

• 아래: index가 row는 +1, col은 그대로 -> 변화값: 1 0
• 오른쪽: index가 row는 그대로, col은 +1 -> 변화값: 0 1
• 위: index가 row는 -1, col은 그대로 -> 변화값: -1 0
• 왼쪽: index가 row는 그대로, col은 -1 -> 변화값: 0 -1

int[] dr = {1, 0, -1, 0}; //directionRow
int[] dc = {0, 1, 0, -1}; //directionCol

index가 0보다 작거나 N보다 크거나 값이0이 아니면 방향 전환

주어진 자연수 마주치면 좌표 저장

풀이1

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        int targetNum = Integer.parseInt(br.readLine());
        
        int[][] arr = new int[N][N];
        int[] dr = {1, 0, -1, 0}; //directionRow
        int[] dc = {0, 1, 0, -1}; //directionCol

        int num = N*N;

        int cr = 0; //currentRow
        int cc = 0; //currentCol
        int dir = 0;
        
        while (num > 0){
            if(targetNum == num){
                sb.append(cr+1).append(" ").append(cc+1);
            }

            arr[cr][cc] = num--;
            
            int nr = cr + dr[dir]; //nextRow
            int nc = cc + dc[dir]; //nextCol

            // 방향전환
            if (nr < 0 || nr > N-1 || nc < 0 || nc > N-1 || arr[nr][nc] != 0){
                dir = (dir + 1) % 4;
                nr = cr + dr[dir];
                nc = cc + dc[dir];
            }

            cr = nr;
            cc = nc;
        }

        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
        
        System.out.println(sb);
    }
}

---

설명2

숫자 1부터 시작
N * N 개의 이차원 배열 만들고오른쪽 -> 아래 -> 왼쪽 -> 위 방향으로 숫자 채워넣음
처음에는 2칸씩 연속으로 채워넣고 그다음은 4칸씩. 2의 배수씩 연속으로 채워넣는다.

1은 (N/2, N/2) 좌표
빙글 도는 시작은 위 좌표에서 한 칸 위로 올라간 좌표에서 시작.
-> 배열처럼 부터 시작한다고 가정하자. 나중에 좌표 위치 출력할때 +1 해서 출력하면 됨.

⚠️ 엣지케이스 주의
targetNum인지는 숫자 2부터 for루프 안에서 계산하고있음. 그럼 숫자 1이 targetNum일때는...? 판별해내지 못함. 따라서 target 숫자가 1일때도 고려하여 targetR과 targetC를 초기화해주자!

// target 숫자가 1일때도 고려하여 초기화
int targetR = currentR + 1;
int targetC = currentC + 1;

풀이2

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        int target = Integer.parseInt(br.readLine());

        int[][] arr = new int[N][N];
        int currentR = N/2;
        int currentC = N/2;
        arr[currentR][currentC] = 1;
        int num = 2;

        int[] dr = {0, 1, 0, -1};
        int[] dc = {1, 0, -1, 0};
        
        // target 숫자가 1일때도 고려하여 초기화
        int targetR = currentR + 1;
        int targetC = currentC + 1;
        for (int i = 0; i < N/2; i++){
            currentR = currentR-1;
            currentC = currentC-1;

            for (int k = 0; k < 4; k++){
                for (int j = 0; j < 2 * (i+1); j++){
                    arr[currentR+dr[k]][currentC+dc[k]] = num;
                    currentR = currentR+dr[k];
                    currentC = currentC+dc[k];

                    if (num == target){
                        targetR = currentR + 1;
                        targetC = currentC + 1;
                    }
                    num++;
                }
            }
        }
        // System.out.println(Arrays.deepToString(arr));
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                sb.append(arr[i][j]).append(" ");
            }
            sb.append("\n");
        }

        sb.append(targetR).append(" ").append(targetC);
        
        System.out.println(sb);
    }
}

⏰ 시간복잡도

O(N^2)
알고리즘의 시간 복잡도를 계산할 때는 단순히 루프의 개수만 세는 게 아니라, 가장 안쪽의 코드가 총 몇 번 실행되는가를 봐야함

• 바깥쪽 루프 ($i$): $0$부터 $N/2$까지 (약 $\frac{N}{2}$번)
• 중간 루프 ($k$): 항상 4번 (상수)
• 안쪽 루프 ($j$): $2, 4, 6, 8, \dots, N-1$까지 증가

이걸 다 더하면 결국 "표(배열)의 모든 칸을 채우는 횟수" 가 된다.
$N \times N$ 크기의 표에서 가운데 1을 제외한 나머지 칸들을 한 번씩만 방문해서 숫자를 채움 -> 가장 안쪽에 있는 arr[currentR][currentC] = num; 이 문장은 정확히 $N^2 - 1$번 실행된다.

1. 루프가 3개지만, 안쪽 루프들이 수행하는 총 횟수의 합이 $N^2$
2. 배열의 모든 칸($N \times N$)을 딱 한 번씩만 방문하므로 $O(N^2)$

💡 TIL

방향 회전 로직

방향 회전 로직에서 나머지 연산자(%) 를 활용하자!

📍 오른쪽으로 90도 회전 (시계 방향)

현재 방향 인덱스에 1을 더하고 4로 나눈 나머지 dir = (dir + 1) % 4

• 0 -> 1, 1 -> 2, 2 -> 3으로 가다가 3에서 1을 더하면 4가 되는데, 이때 4 % 4 를 하면 다시 0으로 돌아옴

📍 왼쪽으로 90도 회전 (반시계 방향)

(dir - 1) % 4 를 하면 음수 결과가 나올 수 있음
따라서 이렇게 해야함 -> dir = (dir + 3) % 4

• 왼쪽으로 1칸 = 시계 방향으로 3칸 -> 항상 양수로 유지
• dir = (dir - 1 + 4) % 4 -> 기존 값에 전체 개수를 더한 뒤 1을 빼주는 방식)

회전 방향	연산식	비고
오른쪽 (90°)	(dir + 1) % 4	다음 인덱스로 이동
왼쪽 (90°)	(dir + 3) % 4	음수 방지를 위해 +3 활용
반대 방향 (180°)	(dir + 2) % 4	마주 보는 방향으로 점프