BOJ 1938 통나무 옮기기(Java)

문제 탐색하기

가로와 세로의 길이가 같은 평지에서 벌목을 한다. 그 지형은 0과 1로 나타나 있다. 1은 아직 잘려지지 않은 나무를 나타내고 0은 아무 것도 없음을 나타낸다.

B 0 0 1 1
B 0 0 0 0
B 0 0 0 0
1 1 0 0 0
E E E 0 0

위의 지형에서 길이 3인 통나무 BBB를 밀거나 회전시켜 EEE의 위치로 옮기는 작업을 한다. BBB, EEE의 위치는 임의로 주어진다.

• 문제에서 통나무의 길이는 항상 3이며 B의 개수와 E의 개수는 같다.
• 통나무를 움직이는 방법은 아래와 같이 상하좌우(Up, Down, Left, Right)와 회전(Turn)이 있다.

코드	의미
U	통나무를 위로 한 칸 옮긴다.
D	통나무를 아래로 한 칸 옮긴다.
L	통나무를 왼쪽으로 한 칸 옮긴다.
R	통나무를 오른쪽으로 한 칸 옮긴다.
T	중심점을 중심으로 90도 회전시킨다.

• 회전의 경우에서는 반드시 중심점을 중심으로 90도 회전을 해야 한다.
• 회전(Turn)이 가능하기 위해서는 그 통나무를 둘러싸고 있는 3*3 정사각형의 구역에 단 한 그루의 나무도 없어야만 한다.

통나무를 5개의 기본동작(U, D, L, R, T)만을 사용하여 처음위치(BBB)에서 최종위치(EEE)로 옮기는 프로그램을 작성하는 것이다. 단, 최소 횟수의 단위 동작을 사용해야 한다.

입력

첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50)

이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문자 사이에는 빈칸이 없다.

통나무와 최종 위치의 개수는 1개이다.

출력

첫째 줄에 최소 횟수의 단위 동작을 출력한다. 만약 통나무를 옮길 수 없는 경우에는 0을 출력한다.

예제 입력

5
B0011
B0000
B0000
11000
EEE00

예제 출력

9

코드 설계하기

구현 방법

• 너비 우선 탐색 (BFS) 사용:
  • 통나무를 시작 위치(BBB)에서 목표 위치(EEE)까지 옮기는 데 필요한 최소 이동 횟수(최단 경로)를 찾기 위해 BFS 알고리즘을 사용한다.
• 상태 정의:
  • 통나무의 상태는 Tree 클래스로 관리한다.
  • 이 클래스는 통나무를 구성하는 세 부분의 좌표(a, b, c), 현재까지의 이동 횟수(count), 그리고 통나무의 방향(isVertical, 세로면 true)을 저장한다.
• 방문 확인:
  • BFS 탐색 중 같은 상태를 중복해서 방문하는 것을 방지하기 위해 3차원 boolean 배열 visited[방향][y][x]를 사용한다.
  • 방향은 통나무가 세로(1)인지 가로(0)인지, y와 x는 통나무의 중심점(b)의 좌표(y=행, x=열)를 나타낸다.
• BFS 과정:
  • 시작 상태(starttree)를 큐에 넣고 방문 처리
  • 큐가 비어있지 않은 동안 다음 과정을 반복
    • 큐에서 현재 상태(cur)를 꺼냄
    • 현재 상태가 목표 상태(endtree)와 동일한지 확인
      • 동일하면 cur.count를 반환하고 종료
    • 5가지 이동(U, D, L, R, T)에 대해 executeMove 함수를 호출하여 다음 상태(nextState)를 얻는다.
      • executeMove 함수는 이동/회전 후의 좌표를 계산하고, 해당 이동이 유효한지 검사한다. (맵 경계, 장애물(‘1’), 회전 시 3x3 영역) 유효하지 않으면 null을 반환한다.
      • nextState가 null이 아니고 아직 방문하지 않은 상태라면, 해당 상태를 방문 처리하고 큐에 추가한다.
• 유효성 검사:
  • checkMap(x, y): 주어진 좌표가 맵 경계 내에 있고 장애물(‘1’)이 없는지 확인한다. (좌표 접근은 map[y][x] 방식 사용)
  • checkPoints(a, b, c): 통나무의 세 부분이 모두 유효한 위치에 있는지 checkMap을 이용해 확인한다.
  • checkRotate(center): 중심점을 기준으로 3x3 영역이 모두 checkMap 검사를 통과하는지 확인한다.
• 결과 처리:
  • BFS가 종료될 때까지 목표 상태에 도달하지 못하면 -1을 반환하고, main 함수에서 이를 0으로 변환하여 출력한다.

시간 복잡도

• BFS의 시간 복잡도는 일반적으로 O(V + E)이며, V는 상태(정점)의 수, E는 상태 간의 전이(간선)의 수이다.
• 상태(V)의 수: 상태는 통나무 중심점의 위치(y, x)와 방향(세로/가로)으로 정의된다. 맵의 크기가 N x N이므로, 중심점의 위치는 N * N 가지 경우가 있으며, 방향은 2가지이다. 따라서 총 상태의 수는 (O(N X N X 2) = O(N^2)) 이다.

• 전이(E)의 수: 각 상태에서 최대 5가지(U, D, L, R, T)의 이동을 시도할 수 있다. 각 이동의 유효성을 검사하고 다음 상태를 생성하는 데 걸리는 시간은 checkPoints, checkRotate 등 내부적으로 고정된 횟수의 연산(최대 9칸 검사)을 수행하므로 상수 시간, 즉 O(1)로 볼 수 있다. 따라서 총 전이의 수는 (O(V X 5) = O(N^2)) 이다.

• 전체 시간 복잡도: (O(V + E) = O(N^2 + N^2) = O(N^2)), 최대 50 * 50 * 5 = 12500번의 연산이 필요하다.
  • 시간 내에 충분히 수행이 가능하다.

정답 코드 (Java)

package gold;

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

public class b1938 {
    private static int N, cnt;
    private static char[][] map;
    private static boolean[][][] visited;

    static class Tree {
        int[] a;
        int[] b;
        int[] c;
        int count;
        boolean isVertical;

        public Tree(int[] a, int[] b, int[] c) {
            this.a = a;
            this.b = b;
            this.c = c;
            isVertical = isVertical();
            this.count = 0;
        }

        public Tree(int[] a, int[] b, int[] c, int count) {
            this.a = a;
            this.b = b;
            this.c = c;
            this.count = count;
            this.isVertical = isVertical();
        }

        // 세로 방향 판정
        private boolean isVertical() {
            return (this.a[1] == this.b[1]) && (this.b[1] == this.c[1]) && (this.a[1] == this.c[1]);
        }

        @Override
        public boolean equals(Object obj) {
            return Arrays.equals(this.a, ((Tree) obj).a)
                    && Arrays.equals(this.b, ((Tree) obj).b)
                    && Arrays.equals(this.c, ((Tree) obj).c);
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new char[N][N];
        visited = new boolean[2][N][N];

        ArrayList<int[]> start = new ArrayList<>();
        ArrayList<int[]> end = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = s.charAt(j);
                if (map[i][j] == 'B') {
                    start.add(new int[]{i, j});
                }
                if (map[i][j] == 'E') {
                    end.add(new int[]{i, j});
                }
            }
        }

        Tree starttree = new Tree(start.get(0), start.get(1), start.get(2));
        Tree endtree = new Tree(end.get(0), end.get(1), end.get(2));

        int res = BFS(starttree, endtree);

        System.out.println(res == -1 ? 0 : res);
    }

    private static int BFS(Tree starttree, Tree endtree) {
        if (starttree.equals(endtree)) {
            return 0;
        }
        Queue<Tree> queue = new LinkedList<>();
        queue.add(starttree);
        // 중앙 지점 기준 방문 여부 표시
        visited[starttree.isVertical ? 1 : 0][starttree.b[1]][starttree.b[0]] = true;
        while (!queue.isEmpty()) {
            Tree cur = queue.poll();

            // 목표 도달 확인
            if (isGoal(cur, endtree)) {
                return cur.count;
            }

            char[] commands = {'U', 'D', 'L', 'R', 'T'};
            for (char command : commands) {
                // 다음 상태 계산
                Tree nextState = executeMove(cur, command);

                if (nextState != null) {
                    // 방문 여부 확인 (visited 배열 사용)
                    int direction = nextState.isVertical ? 1 : 0;
                    if (!visited[direction][nextState.b[1]][nextState.b[0]]) {
                        // 방문 처리 및 큐에 추가
                        visited[direction][nextState.b[1]][nextState.b[0]] = true;
                        queue.add(nextState);
                    }
                }
            }
        }

        return -1;
    }

    private static boolean isGoal(Tree nextState, Tree endtree) {
        return nextState.equals(endtree);
    }

    private static boolean checkMap(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N && map[y][x] != '1';
    }

    private static boolean checkPoint(int[] p){
        return checkMap(p[0], p[1]);
    }

    private static boolean checkPoints(int[] a, int[] b, int[] c){
        return checkPoint(a) && checkPoint(b) && checkPoint(c);
    }

    // 회전 영역 검사 (중심점 center = {행, 열} 기준)
    private static boolean checkRotate(int[] center) {
        int cy = center[0]; // 중심 행
        int cx = center[1]; // 중심 열
        for (int i = cy - 1; i <= cy + 1; i++) { // 행 범위
            for (int j = cx - 1; j <= cx + 1; j++) { // 열 범위
                if (!checkMap(i, j)) {
                    return false;
                }
            }
        }
        return true;
    }

    private static Tree executeMove(Tree currentTree, char command) {
        // 이동/회전 후의 좌표 계산
        int[] nextA = Arrays.copyOf(currentTree.a, currentTree.a.length);
        int[] nextB = Arrays.copyOf(currentTree.b, currentTree.b.length);
        int[] nextC = Arrays.copyOf(currentTree.c, currentTree.c.length);

        switch (command) {
            case 'U': // 행 감소
                nextA[0]--; nextB[0]--; nextC[0]--;
                break;
            case 'D': // 행 증가
                nextA[0]++; nextB[0]++; nextC[0]++;
                break;
            case 'L': // 열 감소
                nextA[1]--; nextB[1]--; nextC[1]--;
                break;
            case 'R': // 열 증가
                nextA[1]++; nextB[1]++; nextC[1]++;
                break;
            case 'T': // 회전 로직 (기존 로직 유지)
                // 회전 가능 여부 먼저 확인 (현재 중심점 기준)
                if (!checkRotate(currentTree.b)) return null;

                if (currentTree.isVertical) { // 세로 -> 가로
                    nextA = new int[] { currentTree.b[0], currentTree.b[1] - 1 };
                    nextC = new int[] { currentTree.b[0], currentTree.b[1] + 1 };
                } else { // 가로 -> 세로
                    nextA = new int[] { currentTree.b[0] - 1, currentTree.b[1] };
                    nextC = new int[] { currentTree.b[0] + 1, currentTree.b[1] };
                }
                break;
        }

        // 최종 이동/회전 후 위치 유효성 검사 (경계 & 장애물)
        if (!checkPoints(nextA, nextB, nextC)) {
            return null;
        }

        // 새로운 Tree 객체 생성 및 반환
        return new Tree(nextA, nextB, nextC, currentTree.count + 1);
    }
}