[백준/JAVA] 1913번: 달팽이

🔺 문제

1913번: 달팽이

 

 

🧩  해결 아이디어

• 구현 (dx/dy technique)

• (0,0)에서 시작해 바깥쪽에서 안쪽으로 돌며 격자를 돌며 칸을 채운다.
• 이미 방문한 칸이거나 격자 범위를 벗어난 칸인 경우, 아래 → 오른쪽 → 위쪽 → 왼쪽 순으로 방향 전환하게 했다

 

 

💥 유의사항

• ArrayIndexOutOfBoundsException 주의,,
• 코드 앞뒤나 위아래 작성 순서에 따라 틀릴 수 있어서 순서를 잘 생각해야 함,,

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {1, 0, -1, 0};   // 회전 순서 : 아래쪽 (0) → 오른쪽 (1) → 위쪽 (2) → 왼쪽 (3)
    static int[] dy = {0, 1, 0, -1};
    
    static int N, findNum;
    static int[][] map;
    
    static int[] pos = {0, 0};      // 현재 좌표 위치
    static int[] ans = new int[2];  // 찾는 번호 좌표
    static int dir = 0;             // 방향 : 아래쪽(0)부터 시작
    
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        findNum = Integer.parseInt(br.readLine());
        
        map = new int[N][N];
        
        // 1. 달팽이 채우기
        fillSnail();
        
        // 2. 출력하기
        printSnail();
        sb.append(ans[0] + " " + ans[1]);
        
        System.out.println(sb);
    }
    
    // 회전하면서 달팽이 채우는 메소드
    private static void fillSnail() {
        map[0][0] = N * N;  // 초기값 설정
        
        for(int i = N * N - 1 ; i >= 1 ; 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;
        }        
    }
    
    // 격자 벗어나는지 판별용 메소드
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < N && 0 <= y && y < N);
    }
    
    // 달팽이 출력 메소드
    private static void printSnail() {
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < N ; j++) {
                sb.append(map[i][j] + " ");
                
                // 찾는 번호를 발견했다면, 해당 위치 값 저장
                if(map[i][j] == findNum) {
                    ans = new int[]{i + 1, j + 1};
                }
            }
            sb.append("\n");
        }
        
        return;
    }
}
 

---

🔺 다른 풀이들

- 안쪽에서 바깥쪽으로 푸는 풀이도.. 그리고 다들 while문 많이 사용하심

[BOJ] 백준 1913번 달팽이 (Java)

 

[백준] 1913: 달팽이 (Java)

---

💬 느낀 점

오랜만에 달팽이 문제 풀려니 까먹음...

복습만이 살 길이다,,

 

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

 

 

(+ 12.22 2회독)

코드 확인하기

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, findNum;
    static int[][] map;
    
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        
        findNum = Integer.parseInt(br.readLine());
        
        map = new int[N][N];
        map[0][0] = N * N;
        
        int dir = 0;
        
        int x = 0;
        int y = 0;
        
        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 = x + dx[dir];
            y = y + dy[dir];
            map[x][y] = i;
            
        }
        
        int[] pos = new int[2];
        
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < N ; j++) {
                sb.append(map[i][j] + " ");
                
                if(map[i][j] == findNum) {
                    pos[0] = i + 1;
                    pos[1] = j + 1;
                }                
            }
            sb.append("\n");
        }
        
        sb.append(pos[0] + " " + pos[1]);
        System.out.println(sb);
    }
    
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < N && 0 <= y && y < N);
    }
}
 

---

(참고)

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