[BOJ/Java] 1938. 통나무 옮기기

[BOJ/Java] 1938. 통나무 옮기기

1938번: 통나무 옮기기

---

문제 해석

NxN 크기의 격자에서 통나무를 이동시켜야 하는 최소 횟수를 구하는 문제다. 통나무는 'B'로, 목표 위치는 'E'로 표현된다. 통나무는 3개의 연속된 칸을 차지하며, 수직이나 수평 방향으로만 움직일 수 있다. 또한, 통나무는 중심을 기준으로 90도 회전할 수 있으며, 각 격자 칸은 비어 있거나('0'), 장애물('1')이 있거나, 통나무의 시작 위치('B'), 혹은 목표 위치('E')일 수 있다.

풀이 과정

통나무의 이동 및 회전 구현을 위해 BFS 알고리즘을 적용하였다. 위치와 방향에 따른 방문 상태를 3차원 배열 v[N][N][2]을 사용하여 관리한다. 이 배열은 수평, 수직 상태를 각각 체크한다. 방문하지 않은 상태이며 이동이 가능할 경우, 해당 상태를 큐에 추가하고 방문 처리한다. 목표 위치에 통나무가 위치할 경우, 움직인 횟수를 반환한다. 또한, 회전이 가능한 상태를 검사하여 가능할 경우 회전 후의 상태를 큐에 추가한다.

코드

package edu.ssafy.im.BOJ.Gold.G2.No1938;

import java.io.*;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
    private static int N;
    private static int[][] map;
    private static boolean[][][] v;
    private static Queue<Point> q; // 큐 선언을 ArrayDeque에서 Queue로 변경하여 추상화 적용
    private static final int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine()); // 입력받은 N 값을 파싱
        map = new int[N][N];
        v = new boolean[N][N][2];
        q = new ArrayDeque<>(); // 큐 초기화
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            String row = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = row.charAt(j); // map 초기화
                if (map[i][j] == 'B') {
                    cnt++;
                    if (cnt != 2) continue;
                    if (1 <= j && map[i][j - 1] == 'B') {
                        v[i][j][0] = true; // 수평 방향 처리
                        q.offer(new Point(i, j, 0));
                    } else {
                        v[i][j][1] = true; // 수직 방향 처리
                        q.offer(new Point(i, j, 1));
                    }
                }
            }
        }

        sb.append(bfs()); // BFS 실행 및 결과 출력
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static int bfs() {
        int cnt = 0;

        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Point p = q.poll(); // 큐에서 포인트 추출
                if (checkDestination(p.x, p.y, p.d)) return cnt; // 도착 지점 체크

                for (int[] d : direction) {
                    int nx = p.x + d[0];
                    int ny = p.y + d[1];

                    if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue; // 맵 범위 체크

                    if (checkMove(nx, ny, p.d)) {
                        q.offer(new Point(nx, ny, p.d)); // 이동 가능한 경우 큐에 추가
                        v[nx][ny][p.d] = true; // 방문 처리
                    }
                }

                int nd = p.d == 1 ? 0 : 1; // 방향 전환
                if (checkRotate(p.x, p.y, nd)) {
                    q.offer(new Point(p.x, p.y, nd)); // 회전 가능한 경우 큐에 추가
                    v[p.x][p.y][nd] = true; // 방문 처리
                }
            }
            cnt++;
        }
        return 0; // 목표 도달 불가 시 0 반환
    }

    private static boolean checkDestination(int x, int y, int d) {
        // 목적지 도달 조건 검사
        if (d == 1) {
            for (int nx = x - 1; nx <= x + 1; nx++) {
                if (nx < 0 || nx >= N) return false; // 범위 밖 검사
                if (map[nx][y] != 'E') return false; // 목적지가 아닌 경우
            }
        } else {
            for (int ny = y - 1; ny <= y + 1; ny++) {
                if (ny < 0 || ny >= N) return false;
                if (map[x][ny] != 'E') return false;
            }
        }
        return true;
    }

    private static boolean checkMove(int x, int y, int d) {
        // 이동 가능 조건 검사
        if (v[x][y][d]) return false; // 이미 방문한 경우
        if (d == 1) {
            if (x == 0 || x == N - 1) return false; // 가장자리 검사
            for (int nx = x - 1; nx <= x + 1; nx++) {
                if (map[nx][y] == '1') return false; // 장애물 검사
            }
        } else {
            if (y == 0 || y == N - 1) return false;
            for (int ny = y - 1; ny <= y + 1; ny++) {
                if (map[x][ny] == '1') return false;
            }
        }
        return true;
    }

    private static boolean checkRotate(int x, int y, int d) {
        // 회전 가능 조건 검사
        if (v[x][y][d]) return false; // 이미 방문한 경우
        for (int nx = x - 1; nx <= x + 1; nx++) {
            for (int ny = y - 1; ny <= y + 1; ny++) {
                if (nx < 0 || nx >= N || ny < 0 || ny >= N) return false; // 범위 밖 검사
                if (map[nx][ny] == '1') return false; // 장애물 검사
            }
        }
        return true;
    }

    static class Point {
        int x, y, d;

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

시간 복잡도 분석

시간 복잡도는 O(N^2)로 추정된다. 격자 내 모든 칸에 대해 이동과 회전을 검사할 수 있기 때문에, 최악의 경우 모든 칸을 방문하면서 연산을 수행할 수 있다.

느낀점

이 문제를 통해 BFS를 사용하여 그리드 기반의 문제에서 객체의 이동 및 회전을 어떻게 처리할 수 있는지 학습할 수 있었다. 특히, 회전 연산을 구현하면서 객체 중심의 동작을 이해하는 데 도움이 되었다.