[BaekJoon] 1938 통나무 옮기기 (Java)

1.  문제 링크

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

2.  문제

요약

• 가로와 세로의 길이가 같은 평지에서 벌목을 하는데, 지형은 0과 1로 나타나있고, 1은 아직 잘려지지 않은 나무를 나타내고 0은 아무 것도 없음을 나타냅니다.
• 지형에서 길이 3인 통나무 BBB를 밀거나 회전시켜 EEE의 위치로 옮기는 작업을 하려고 합니다.
• 통나무를 움직이는 방법은 상하좌우와 회전이 있습니다.

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

• 통나무가 움직일 위치에 다른 나무, 즉 1이 없어야만 움직일 수 있고, 움직임은 한 번에 한 칸씩만 움직입니다.
• 움직이는 통나무는 어떤 경우이든지 중간단계에서 한 행이나 한 열에만 놓일 수 있습니다.
• 회전의 경우는 반드시 중심점을 중심으로 90도 회전합니다.(항상 통나무의 길이가 3이므로 중심점이 존재합니다)
• 회전이 가능하기 위해서는 통나무를 둘러싸고 있는 3 * 3 정사각형의 구역에 단 한 그루의 나무도 없어야만 합니다. 즉, 1이 없어야만 합니다.
• 통나무를 5개의 기본동작만을 사용하여 처음 위치에서 최종 위치로 옮길 때 최소 동작 횟수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 4보다 크거나 같고 50보다 작거나 같은 평지의 한 변의 길이 N이 주어지고 두 번째 줄부터 N개의 줄에 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어집니다. 한 줄에 입력되는 문자열의 길이는 N이며, 통나무와 최종 위치의 개수는 1개입니다.
• 출력: 첫 번째 줄에 최소 동작 횟수를 출력합니다. 이동이 불가능하다면 0을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static char[][] map;
    static int[][] treeLoc, endLoc;
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        map = new char[N][N];
        treeLoc = new int[3][2];
        endLoc = new int[3][2];

        int treeIdx = 0, endIdx = 0;

        for(int row = 0; row < N; row++) {
            String info = scanner.nextLine();

            for(int col = 0; col < N; col++) {
                map[row][col] = info.charAt(col);

                if(map[row][col] == 'B') {
                    treeLoc[treeIdx][0] = row;
                    treeLoc[treeIdx][1] = col;
                    treeIdx++;
                }

                if (map[row][col] == 'E') {
                    endLoc[endIdx][0] = row;
                    endLoc[endIdx][1] = col;
                    endIdx++;
                }
            }
        }
    }

    static void solution() {
        System.out.println(bfs());
    }

    static int bfs() {
        Queue<Tree> queue = new LinkedList<>();
        boolean[][][] visited = new boolean[2][N][N];
        int answer = 0;

        int direction = -1;
        if(treeLoc[0][1] + 1 == treeLoc[1][1]) direction = 0;
        else direction = 1;

        queue.offer(new Tree(treeLoc[1][0], treeLoc[1][1], direction, 0));
        visited[direction][treeLoc[1][0]][treeLoc[1][1]] = true;

        while(!queue.isEmpty()) {
            Tree cur = queue.poll();

            if(cur.x == endLoc[1][0] && cur.y == endLoc[1][1]) {
                if(cur.direction == 0) {
                    if(map[cur.x][cur.y - 1] == 'E' && map[cur.x][cur.y + 1] == 'E') {
                        answer = cur.moveNum;
                        break;
                    }
                } else if(cur.direction == 1) {
                    if(map[cur.x - 1][cur.y] == 'E' && map[cur.x + 1][cur.y] == 'E') {
                        answer = cur.moveNum;
                        break;
                    }
                }
            }

            for(int dir = 0; dir < 4; dir++) {
                int cx = cur.x + dx[dir], cy = cur.y + dy[dir];

                if(isInMap(cx, cy, cur.direction, dir)) {
                    if(!visited[cur.direction][cx][cy]) {
                        visited[cur.direction][cx][cy] = true;
                        queue.offer(new Tree(cx, cy, cur.direction, cur.moveNum + 1));
                    }
                }
            }

            if(canRotate(cur.x, cur.y)) {
                if(cur.direction == 0) {
                    if(!visited[1][cur.x][cur.y]) {
                        visited[1][cur.x][cur.y] = true;
                        queue.offer(new Tree(cur.x, cur.y, 1, cur.moveNum + 1));
                    }
                } else if(cur.direction == 1) {
                    if(!visited[0][cur.x][cur.y]) {
                        visited[0][cur.x][cur.y] = true;
                        queue.offer(new Tree(cur.x, cur.y, 0, cur.moveNum + 1));
                    }
                }
            }
        }

        return answer;
    }

    static boolean canRotate(int x, int y) {
        for(int row = x - 1; row <= x + 1; row++) {
            for(int col = y - 1; col <= y + 1; col++) {
                if(row < 0 || row >= N || col < 0 || col >= N) return false;
                if(map[row][col] == '1') return false;
            }
        }

        return true;
    }

    static boolean isInMap(int x, int y, int direction, int dir) {
        if(x < 0 || x >= N || y < 0 || y >= N) return false;

        if(direction == 0) {
            if(dir >= 2)
                if(y - 1 < 0 || y + 1 >= N) return false;

            if(map[x][y] == '1' || map[x][y - 1] == '1' || map[x][y + 1] == '1')
                return false;
        } else if(direction == 1) {
            if(dir < 2)
                if(x - 1 < 0 || x + 1 >= N) return false;

            if(map[x][y] == '1' || map[x - 1][y] == '1' || map[x + 1][y] == '1')
                return false;
        }

        return true;
    }

    static class Tree {
        int x, y, direction, moveNum;

        public Tree(int x, int y, int direction, int moveNum) {
            this.x = x;
            this.y = y;
            this.direction = direction;
            this.moveNum = moveNum;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }

            return str;
        }
    }
}