[백준] 1385번 벌집

문제 설명

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

문제 풀이

• 벌집을 구현하는 것이 조금 어려운 BFS이다. (bfs알고리즘은 단순)

1. 벌집 구현 하기
   • 벌집은 2차원 행렬로 표현이 가능하다.
   • 벌집을 구현하기 위한 메모리 크기 고려
     - 6가지 방향 중 한 방향을 잡고 수열을 살펴보면 공차가 6인 계차수열이 나온다.
     - 최대 1,000,000까지 표현하기 위해서 한 방향으로 최대 몇번 확장해야하는지 보자
     • 계차 수열의 일반항 6 x n x (n + 1) = 1,000,000의 해는 약 570정도가 되므로 넉넉히 1500x1500 2차원 행렬로 표현이 가능하다.
   • (750, 750) 좌표를 1로 두고 규칙에 따라 벌집을 그려나간다. (코드 참조)
2. BFS로 경로 찾기
   • BFS는 간단하다. 경로를 찾기 위해 BFS 역추적을 해야하므로 방문탐색을 위한 chk 배열에 이전 좌표의 방 번호를 대신 입력한다.
   • 결과 위치에 도달하면 chk배열을 참조하여 stack을 활용해 역추적 후 출력 해준다.

소스 코드 (JAVA)

import java.io.*;
import java.util.*;

public class Main {
    public static BufferedReader br;
    public static BufferedWriter bw;
    public static int S, T, sx, sy;
    public static int[][] map = new int[1500][1500];
    public static int[][] chk = new int[1500][1500];
    public static int[] dx = {-1, 0, 1, 1, 0, -1};
    public static int[] dy = {0, 1, 1, 0, -1, -1};

    public static class Point {
        int x, y;

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

    public static void solve() throws IOException {
        Queue<Point> q = new ArrayDeque<>();
        q.add(new Point(sx, sy));
        chk[sx][sy] = -1;
        while(!q.isEmpty()) {
            Point cur = q.poll();
            //결과 출력
            if (map[cur.x][cur.y] == T) {
                int x = cur.x;
                int y = cur.y;
                Stack<Integer> st = new Stack<>();
                while(true) {
                    st.push(map[x][y]);
                    if (chk[x][y] == -1) break;
                    for (int d = 0; d < 6; d++) {
                        int X = x + dx[d];
                        int Y = y + dy[d];
                        if (map[X][Y] == chk[x][y]) {
                            x = X;
                            y = Y;
                            break;
                        }
                    }
                }
                while(!st.isEmpty()) {
                    bw.write(st.pop() + " ");
                }
                bw.write("\n");
                bw.flush();
                System.exit(0);
            }
            for (int d = 0; d < 6; d++) {
                int X = cur.x + dx[d];
                int Y = cur.y + dy[d];
                if (map[X][Y] == 0 || chk[X][Y] != 0) continue;
                chk[X][Y] = map[cur.x][cur.y];
                q.add(new Point(X, Y));
            }
        }
    }

    //벌집 맵을 그려줌
    public static void draw() {
        int x = 750;
        int y = 750;
        int N = 1;
        int K = 1; //확장값
        map[x][y] = 1;
        while(true) {
            for (int d = 0; d < 6; d++) {
                for (int k = 0; k < (d == 1 ? K-1 : K); k++) {
                    int X = x + dx[d];
                    int Y = y + dy[d];
                    map[X][Y] = ++N;
                    //시작 숫자이면
                    if (N == S) {
                        sx = X;
                        sy = Y;
                    }
                    //최대 숫자이면
                    if (N == 1000000) return;
                    x = X;
                    y = Y;
                }
            }
            K++;
        }
    }

    public static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        S = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        input();
        draw();
        solve();
        bw.flush();
        bw.close();
        bw.close();
    }
}