[코드트리/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;    // ASCII 코드 활용
    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] = (int)'A';  // 초기 값 설정
 
        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 % 26 + 'A' - 1;
 
            if((char)map[x][y] =='@') { // 'Z'가 '@'로 나와서 이렇게 만듦.
                map[x][y] = (int)'Z';
            }
        }
 
        // 출력하기
        StringBuilder sb = new StringBuilder();
        for(int[] i : map) {
            for(int j : i) {
                sb.append((char)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 배열에 값을 저장한다.

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

 

- 2차원 int형 배열을 선언해 알파벳의 ASCII 코드 숫자형 값과 방문 여부를 동시에 표현한다.

 

- 초기값을 char형인 A로 설정하고 싶은데 int형 배열을 선언했으니  숫자형으로 변환한 후 값을 넣는다. → (int)'A'

2부터 N*M만큼 값을 증가하며 2차원 배열을 채운다. 

 

- 값을 채울 때, ASCII 코드를 활용하고, Z가 끝나면 다시 A에서부터 시작하게 해야 하므로

현재 숫자값 (i % 26) + 'A' - 1을 해 int형으로 값을 저장한다.

 

그런데 이 때 Z가 나와야할 때 @가 나온다. ㄴㅇㄱ

그래서 @를 Z로 바꿔주는 처리도 추가적으로 했다.

(만일 @ 처리를 안 하고 싶다면,

반복문의 범위를 1부터 N*M -1까지 설정한다.

그리고 map[x][y] = i % 26 + 'A'하면 된다.)

 

- 회전하는 조건 ⭐

1) 다음 위치가 격자를 벗어나는 경우 (!inRange(nx, ny))

2) 이미 방문한 경우 (map[x][y] != 0)

 

 

 

---

🔺 다른 풀이들

- 2차원 char형 배열과 2차원 boolean형 방문 배열을 따로 만들어 풀 수도 있다.

import java.util.Scanner;
 
public class Main {
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};   
    
    static char[][] answer = new char[100][100]; // 알파벳 저장 배열
    static boolean[][] visited = new boolean[100][100];    // 방문 여부 배열
    static int n, m;
 
    static int currX = 0, currY = 0; // 시작점 (0,0)
    static int dir = 0;    // 0: 오른쪽, 1: 아래쪽, 2: 왼쪽, 3: 위쪽
    
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        m = sc.nextInt();
 
        // 시작점 처리
        answer[currX][currY] = 'A';  
        visited[currX][currY] = true;
 
        for(int i = 1; i < n * m; i++) { // 🔔 i번째 문자 어디에 적을지 결정 (범위 조심!!)
            int nx = currX + dx[dir];
            int ny = currY + dy[dir];
 
            if(canGo(n, m, nx, ny)) {    // 나아갈 수 있는 경우, 값 넣고 나아가기
                currX = nx;
                currY = ny;
                visited[currX][currY] = true;
                
                answer[currX][currY] = (char)(i % 26 + 'A');    // ⭐ 값 넣기
            }
            else { // 나아갈 수 없다면, 시계방향으로 90도 회전
               dir = (dir + 1) % 4;
            }
        }
        
        // 출력
        for(int i = 0 ; i < n; i++) {
            for(int j = 0;  j < m; j++) 
                System.out.print(answer[i][j] + " ");
            System.out.println();
        }
    }
    
    // 격자 범위 안에 있고, 방문한 적 없다면 새롭게 방문 가능
    public static boolean canGo(int n, int m, int newX, int newY){
        return (0 <= newX && newX < n && 0 <= newY && newY < m && visited[newX][newY] == false);
    }
}

 

 

---

💬 느낀 점

달팽이 문제 재밌당,,,히히

 

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

---

(참고)

✔ 코드트리 dx/dy technique

✔  ASCII 코드

[Java] ASCII (아스키코드)/ 문자 ↔ 숫자