[코드트리/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, M;
    static int[][] map; // 정답 저장 겸 방문 기록 배열
 
    static int[] pos = new int[] {0,0}; // 현재 위치 (x, y). 시작점은 (0,0)
    static int dir = 0;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        // 입력받기
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        map = new int[N][M];
        map[0][0] = 1;  // 시작점은 1로 설정
 
        // 달팽이 모양으로 채우기
        for(int i = 2 ; i <= N * M ; i++) {
            int nx = pos[0] + dx[dir];
            int ny = pos[1] + dy[dir];
 
            // 격자를 벗어나거나, 이미 방문한 칸이라면 방향 전환
            if(!inRange(nx, ny) || (map[nx][ny] != 0)) {
                dir = (dir + 1) % 4;
            }
 
            // 이동하고 칸에 값 채워넣기
            pos[0] += dx[dir];
            pos[1] += dy[dir];
            map[pos[0]][pos[1]] = i;
        }
 
        // 출력하기
        StringBuilder sb = new StringBuilder();
        for(int[] i : map) {
            for(int j : i) {
                sb.append(j + " ");
            }
            sb.append("\n");
        }
 
        System.out.println(sb.toString());
    }
 
    // 범위 확인용 메소드
    private static boolean inRange(int x, int y) {
        return (x >= 0 && x < N && y >= 0 && y < M);
    }
}

 

 

 

🧩  해결 아이디어

• dx/dy technique) 빙빙 돌며 숫자 적기 

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

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

 

 

- 초기값을 1로 설정하고, N*M만큼 값을 증가하며 2차원 배열을 채운다.

- 시계 방향으로 90도 회전하는 조건 ⭐

1) 다음 위치가 격자를 벗어나는 경우

2) 이미 방문한 경우

 

 

 

---

💬 느낀 점

달팽이 문제 이렇게 푸는 것이었구만.............

진짜 코드트리 짱이다.....

왜 진작 안했니.....ㅠ

 

 

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

---

(참고)

✔ 코드트리 dx/dy techinque) 빙빙 돌며 숫자 적기