[BOJ] 1913: 달팽이 (JAVA)

문제

https://www.acmicpc.net/problem/1913

 

여담

처음에 DFS 방식으로 문제를 풀었다. 메모리를 너무 많이 사용하길래 이 방식이 맞나싶어서 다른 풀이를 봤더니 그냥 순수 구현으로 풀 수 있는 문제였다.. 

 

순수 구현으로 푼 문제와 DFS 탐색을 통해 푼 문제의 메모리 차이가.. ㅎㅎ

 

풀이

이 문제는 "안 → 밖" 또는 "밖 → 안"의 순서대로 하나씩 칸을 채워나가면 된다. 나는 밖에서 안으로 채우는 방식을 사용했다. 다음 사진에서 알 수 있듯이 "아래 → 오른쪽 → 위 → 왼쪽" 방향이 반복된다.

 

따라서 (0, 0)에서 시작해서 한 방향으로 이동하다가, 다음에 이동할 지점이 범위를 벗어나거나 이미 값이 기록된 곳이라면 방향을 변경하면 된다. 

• 범위를 벗어난 경우
  • x + dx[i] < 0 || y + dy[i] < 0 || x + dx[i] >= n || y + dy[i] >= n
• 이미 값이 기록된 경우
  • map[x + dx[i]][y + dy[i]] != 0

 

코드

구현

import java.io.*;

public class Main {
    static int n, k, ansX, ansY;
    static int[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());
        map = new int[n][n];

        makeMap(0, 0);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sb.append(map[i][j]).append(" ");
            }
            sb.append("\n");
        }
        sb.append(ansX).append(" ").append(ansY);
        System.out.println(sb);
    }

    public static void makeMap(int x, int y) {
        int i = 0, num = n * n;
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        while (num > 0) {
            map[x][y] = num--;
            if (map[x][y] == k) {
                ansX = x + 1;
                ansY = y + 1;
            }

            if (x + dx[i] < 0 || y + dy[i] < 0 || x + dx[i] >= n || y + dy[i] >= n // 범위를 벗어나거나
                    || map[x + dx[i]][y + dy[i]] != 0) { // 이미 방문한 지점인 경우
                // 방향 바꾸기
                i = (i + 1) % 4;
            }

            x += dx[i];
            y += dy[i];
        }
    }
}

 

DFS 탐색

이 방법은 메모리를 너무 많이 잡아먹어서 최적의 답이 아니라고 생각한다. 그냥 기록용으로 남겨놓는다!

import java.io.*;

public class Main {
    static int n, k, m, num = 1;
    static int[][] map;
    static Pos pos;
    static int[] dx = {0, -1, 0, 1};
    static int[] dy = {1, 0, -1, 0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());
        map = new int[n][n];
        m = n / 2;
        map[m][m] = num++; // 중앙부터 시작
        if (map[m][m] == k) pos = new Pos(m + 1, m + 1);
        dfs(m - 1, m); // 중앙에서는 위로 이동해서 DFS 탐색 시작
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sb.append(map[i][j]).append(" ");
            }
            sb.append("\n");
        }
        sb.append(pos.x).append(" ").append(pos.y);
        System.out.println(sb);
    }

    public static void dfs(int x, int y) {
        if (num > n * n) return;
        map[x][y] = num++;
        if (map[x][y] == k) pos = new Pos(x + 1, y + 1);

        int start;
        if (x <= m) {
            if (y <= m) start = 0;
            else start = 3;
        } else {
            if (y <= m) start = 1;
            else start = 2;
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[(start + i) % 4];
            int ny = y + dy[(start + i) % 4];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            if (map[nx][ny] == 0) {
                dfs(nx, ny);
                return;
            }
        }
    }

    static class Pos {
        int x, y;

        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

---

참고

https://ming-jee.tistory.com/28