[코드트리/NOVICE MID] 가운데에서 시작하여 빙빙 돌기 (JAVA)

🔺 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0, -1, 0, 1};   // 서북동남 (행과 열로 생각)
    static int[] dy = {-1, 0, 1, 0};
 
    static int N;
    static int[][] map;
    static int x,y;
    static int dir = 0;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
 
        x = N - 1;  y = N - 1;
        map[x][y] = N * N;
 
        for(int i = N * N - 1 ; i >= 1 ; i--) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
 
            if(!inRange(nx,ny) || map[nx][ny] != 0) {
                dir = (dir + 1) % 4;
            }
 
            x += dx[dir];
            y += dy[dir];
            map[x][y] = i;
        }
 
        // 출력하기
        StringBuilder sb = new StringBuilder();
        for(int[] i : map) {
            for(int j : i) {
                sb.append(j + " ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
 
    // 범위 판별 메소드
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < N && 0 <= y && y < N);
    }
}

 

 

 

🧩  해결 아이디어

• dx/dy technique

- 맨 오른쪽 아래 위치 (N - 1, N - 1)에서부터 시작해 바깥쪽에서부터 안쪽으로 들어가게 만든다.

방향 트는 순서는 시계 방향으로 90도니까 서-북 동-남.

이 순서대로 dx, dy 배열에 값을 저장한다.

 

- 방향 전환을 하고 싶으면 (현재 방향 번호  + 1) % 4를 하면 된다.

- map을 채울 i 값도 (N*N -1)부터 1까지 1씩 작아지며 들어가야 하므로

for문의 범위는 (N*N - 1) ~ 1까지다.

 

---

🔺 다른 풀이들

- 정가운데부터 시작하는 풀이

 

방향 이동 순서 : 오른쪽 - 위 - 왼쪽 - 아래

방향, 1씩 이동하다가 방향이 왼쪽(2) 또는 오른쪽(0)이 되면

동일한 방향에 대해 이동하는 거리가 1씩 늘어남

 

단, 마지막 끝나는부분은 다름!최종적으로 격자를 벗어나게 되는 경우 처리

import java.util.Scanner;
 
public class Main {
    public static final int MAX_N = 100;
    public static final int DIR_NUM = 4;
    
    public static int n;
    
    public static int currX, currY;
    public static int moveDir, moveNum;
    
    public static int[][] grid = new int[MAX_N][MAX_N];
       
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        
        currX = n / 2; currY = n / 2;    // 시작점
        moveDir = 0;
        moveNum = 1;
        
        int cnt = 1;
 
        while(!end()) {
            for(int i = 0; i < moveNum; i++) {
                grid[currX][currY] = cnt++;
                move();
 
                if(end())    // 이동하다 격자 벗어나면, 종료
                    break;
            }
            
            moveDir = (moveDir + 1) % 4;
 
            if(moveDir == 0 || moveDir == 2)    // 만약 현재 방향이 왼/오른쪽이 된 경우, 특정 방향으로 움직여야 할 횟수 + 1
                moveNum++;
        }
        
        // 출력
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++)
                System.out.print(grid[i][j] + " ");
            System.out.println();
        }
    }
 
    public static boolean inRange(int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < n;
    }
 
    // 한 칸 움직이는 메소드
    public static void move() {
        int[] dx = new int[]{0, -1, 0, 1};
        int[] dy = new int[]{1, 0, -1, 0};
    
        currX += dx[moveDir]; currY += dy[moveDir];
    }
    
    public static boolean end() {
        return !inRange(currX, currY);
    }
}

 

 

---

💬 느낀 점

안쪽에서 풀어보려고 하다가..저 반복 횟수 규칙을 뒤늦게 찾고..

for문으로 해결하려다가 포기하고

 

그냥 바깥쪽에서 안쪽으로 들어가는 방향으로 풀었다...

 

안쪽에서 바깥쪽으로 나가는 풀이 신박하다.... 

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 코드트리 dx dy technique