[코드트리/NOVICE MID] 빙빙 돌며 숫자 사각형 채우기 2 (JAVA)

🔺 문제

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

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {1,0,-1,0};   // 남동북서 (행과 열로 생각)
    static int[] dy = {0,1,0,-1};
 
    static int n, m;
    static int[][] map;
 
    static int x = 0 , y = 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[x][y] = 1;  // 초기 값 설정
 
        for(int i = 2 ; i <= n * m ; 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 < m);
    }
}

 

 

 

🧩  해결 아이디어

• dx/dy technique

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

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

 

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

- 회전하는 조건 ⭐

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

2) 이미 방문한 경우

 

 

 

---

💬 느낀 점

달팽이 문제 이해하고 나니 넘 재밌네....

 

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