[백준] 🥇 1938 통나무 옮기기

📌 난이도

🥇 Gold 2

📌 문제

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

📌 풀이

최근에 푼 골드 문제중에 가장 난이도가 높은 무려 골드 2짜리 문제였다.
처음 문제를 보자 든 생각은 BFS 로 풀 되 통나무 중심을 기준으로 가로, 세로를 나눠서 구현하자는 생각이였다.

그래서 통나무를 저장할 pos 라는 이름의 class를 만들고, 그 안에 r, c, isVertical 이라는 변수들을 넣어주었다.
그래고 field를 구성할 tile이라는 객체에 Vertical 값과, Horizontal 값을 저장할 변수를 만들어 주었다.

일반적인 BFS 와 다르게 이동하는 여러가지 방향과 현재 통나무가 세로, 가로인지에 따라서 이동 방식이 다르므로 DR, DC 를 제외하고, 여러가지 방향 상수배열을 만들어주었다.
이후 BFS 를 통해 구현한 코드이다.

📌 Code

package BOJ.BFS;

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

public class N1938 {
    static class pos {
        int r;
        int c;
        boolean isVertical;

        public pos(int r, int c, boolean isVertical) {
            this.r = r;
            this.c = c;
            this.isVertical = isVertical;
        }
    }

    static class tile {
        int Vertical;
        int Horizontal;

        public tile(int state) {
            this.Vertical = state;
            this.Horizontal = state;
        }
    }

    static Queue<pos> q;
    static tile[][] field;
    static final int startPoint = 0;
    static final int notvisited = 1000002;
    static final int tree = -3;

    static final int[] VLDR = {-1, 0, 1};
    static final int[] VLDC = {-1, -1, -1};
    static final int[] VUDR = {-2};
    static final int[] VUDC = {0};

    static final int[] HLDR = {0};
    static final int[] HLDC = {-2};
    static final int[] HUDR = {-1, -1, -1};
    static final int[] HUDC = {-1, 0, 1};

    static final int[] ALLDR = {-1, -1, 0, 1, 1, 1, 0, -1};
    static final int[] ALLDC = {0, 1, 1, 1, 0, -1, -1, -1};
    static int N;

    static int flag;
    static final int CantGoGoal = 1000003;
    static boolean goalPoint;
    static int[] goalPointcoor;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        field = new tile[N][N];
        q = new LinkedList<>();
        boolean isVertical;
        int[][] start = new int[3][2];
        int[][] end = new int[3][2];
        int flag1 = 0;
        int flag2 = 0;
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < N; j++) {
                if (str.charAt(j) == '0') {
                    field[i][j] = new tile(notvisited);
                } else if (str.charAt(j) == '1') {
                    field[i][j] = new tile(tree);
                } else if (str.charAt(j) == 'B') {
                    start[flag1] = new int[]{i, j};
                    field[i][j] = new tile(notvisited);
                    flag1 += 1;
                } else {
                    end[flag2] = new int[]{i, j};
                    field[i][j] = new tile(notvisited);
                    flag2 += 1;
                }

            }
        }
        field[start[1][0]][start[1][1]] = new tile(startPoint);
        if (start[0][0] != start[2][0]) {
            q.add(new pos(start[1][0], start[1][1], true));
        } else {
            q.add(new pos(start[1][0], start[1][1], false));
        }
        goalPointcoor = new int[]{end[1][0], end[1][1]};
        if (end[0][0] != end[2][0]) {
            goalPoint = true;
        } else {
            goalPoint = false;
        }
        BFS();
    }

    static void BFS() {
        //ShowAll();
        flag = CantGoGoal;
        while (!q.isEmpty()) {
            pos cur = q.poll();
            if (cur.isVertical) {
                for (int i = 0; i < 5; i++) {
                    VerticalLog(cur, i);
                }
            } else {
                for (int i = 0; i < 5; i++) {
                    HorizonLog(cur, i);
                }
            }
            //ShowAll();
        }
        if (flag == CantGoGoal) {
            System.out.println(0);
        } else {
            System.out.println(flag);
        }
    }

    static void ShowAll() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i == goalPointcoor[0] && j == goalPointcoor[1]) {
                    System.out.print(">");
                } else {
                    System.out.print("|");
                }

                if (field[i][j].Horizontal == notvisited) {
                    System.out.printf("%2s.", "");
                } else {
                    System.out.printf("%3d", field[i][j].Horizontal);
                }

                if (field[i][j].Vertical == notvisited) {
                    System.out.printf("%2s.", "");
                } else {
                    System.out.printf("%3d", field[i][j].Vertical);
                }
            }
            System.out.println();
        }
        System.out.print("======================");
        System.out.println(flag);
    }

    static boolean VerticalLog(pos cur, int index) {
        switch (index) {
            case 0:
                // Vertical 좌로 이동
                for (int i = 0; i < VLDR.length; i++) {
                    int nextR = cur.r + VLDR[i];
                    int nextC = cur.c + VLDC[i];
                    if (nextR < 0 || nextR >= N || nextC < 0 || nextC >= N || field[nextR][nextC].Vertical == tree) {
                        return false;
                    }
                }
                if (cur.r == goalPointcoor[0] && cur.c - 1 == goalPointcoor[1] && goalPoint) {
                    flag = Math.min(flag, field[cur.r][cur.c].Vertical + 1);
                }
                if (field[cur.r][cur.c - 1].Vertical > field[cur.r][cur.c].Vertical + 1) {
                    field[cur.r][cur.c - 1].Vertical = field[cur.r][cur.c].Vertical + 1;
                    q.add(new pos(cur.r, cur.c - 1, true));
                }
                break;
            case 1:
                // Vertical 우로 이동
                for (int i = 0; i < VLDR.length; i++) {
                    int nextR = cur.r + VLDR[i];
                    int nextC = cur.c - VLDC[i];
                    if (nextR < 0 || nextR >= N || nextC < 0 || nextC >= N || field[nextR][nextC].Vertical == tree) {
                        return false;
                    }
                }
                if (cur.r == goalPointcoor[0] && cur.c + 1 == goalPointcoor[1] && goalPoint) {
                    flag = Math.min(flag, field[cur.r][cur.c].Vertical + 1);
                }
                if (field[cur.r][cur.c + 1].Vertical > field[cur.r][cur.c].Vertical + 1) {
                    field[cur.r][cur.c + 1].Vertical = field[cur.r][cur.c].Vertical + 1;
                    q.add(new pos(cur.r, cur.c + 1, true));
                }
                break;
            case 2:
                // Vertical 아래로 이동
                for (int i = 0; i < VUDR.length; i++) {
                    int nextR = cur.r - VUDR[i];
                    int nextC = cur.c + VUDC[i];
                    if (nextR < 0 || nextR >= N || nextC < 0 || nextC >= N || field[nextR][nextC].Vertical == tree) {
                        return false;
                    }
                }
                if (cur.r + 1 == goalPointcoor[0] && cur.c == goalPointcoor[1] && goalPoint) {
                    flag = Math.min(flag, field[cur.r][cur.c].Vertical + 1);
                }
                if (field[cur.r + 1][cur.c].Vertical > field[cur.r][cur.c].Vertical + 1) {
                    field[cur.r + 1][cur.c].Vertical = field[cur.r][cur.c].Vertical + 1;
                    q.add(new pos(cur.r + 1, cur.c, true));
                }
                break;
            case 3:
                // 위로 이동
                for (int i = 0; i < VUDR.length; i++) {
                    int nextR = cur.r + VUDR[i];
                    int nextC = cur.c + VUDC[i];
                    if (nextR < 0 || nextR >= N || nextC < 0 || nextC >= N || field[nextR][nextC].Vertical == tree) {
                        return false;
                    }
                }
                if (cur.r - 1 == goalPointcoor[0] && cur.c == goalPointcoor[1] && goalPoint) {
                    flag = Math.min(flag, field[cur.r][cur.c].Vertical + 1);
                }
                if (field[cur.r - 1][cur.c].Vertical > field[cur.r][cur.c].Vertical + 1) {
                    field[cur.r - 1][cur.c].Vertical = field[cur.r][cur.c].Vertical + 1;
                    q.add(new pos(cur.r - 1, cur.c, true));
                }
                break;
            case 4:
                // 회전
                for (int i = 0; i < ALLDC.length; i++) {
                    int nextR = cur.r + ALLDR[i];
                    int nextC = cur.c + ALLDC[i];
                    if (nextR < 0 || nextR >= N || nextC < 0 || nextC >= N || field[nextR][nextC].Vertical == tree) {
                        return false;
                    }
                }
                if (cur.r == goalPointcoor[0] && cur.c == goalPointcoor[1] && !goalPoint) {
                    flag = Math.min(flag, field[cur.r][cur.c].Vertical + 1);
                }
                if (field[cur.r][cur.c].Horizontal > field[cur.r][cur.c].Vertical + 1) {
                    field[cur.r][cur.c].Horizontal = field[cur.r][cur.c].Vertical + 1;
                    q.add(new pos(cur.r, cur.c, false));
                }
        }
        return true;
    }

    static boolean HorizonLog(pos cur, int index) {
        switch (index) {
            case 0:
                // Vertical 좌로 이동
                for (int i = 0; i < HLDR.length; i++) {
                    int nextR = cur.r + HLDR[i];
                    int nextC = cur.c + HLDC[i];
                    if (nextR < 0 || nextR >= N || nextC < 0 || nextC >= N || field[nextR][nextC].Horizontal == tree) {
                        return false;
                    }
                }
                if (cur.r == goalPointcoor[0] && cur.c - 1 == goalPointcoor[1] && !goalPoint) {
                    flag = Math.min(flag, field[cur.r][cur.c].Horizontal + 1);
                }
                if (field[cur.r][cur.c - 1].Horizontal > field[cur.r][cur.c].Horizontal + 1) {
                    field[cur.r][cur.c - 1].Horizontal = field[cur.r][cur.c].Horizontal + 1;
                    q.add(new pos(cur.r, cur.c - 1, false));
                }
                break;
            case 1:
                // Vertical 우로 이동
                for (int i = 0; i < HLDR.length; i++) {
                    int nextR = cur.r + HLDR[i];
                    int nextC = cur.c - HLDC[i];
                    if (nextR < 0 || nextR >= N || nextC < 0 || nextC >= N || field[nextR][nextC].Horizontal == tree) {
                        return false;
                    }
                }
                if (cur.r == goalPointcoor[0] && cur.c + 1 == goalPointcoor[1] && !goalPoint) {
                    flag = Math.min(flag, field[cur.r][cur.c].Horizontal + 1);
                }
                if (field[cur.r][cur.c + 1].Horizontal > field[cur.r][cur.c].Horizontal + 1) {
                    field[cur.r][cur.c + 1].Horizontal = field[cur.r][cur.c].Horizontal + 1;
                    q.add(new pos(cur.r, cur.c + 1, false));
                }
                break;
            case 2:
                // Vertical 아래로 이동
                for (int i = 0; i < HUDR.length; i++) {
                    int nextR = cur.r - HUDR[i];
                    int nextC = cur.c + HUDC[i];
                    if (nextR < 0 || nextR >= N || nextC < 0 || nextC >= N || field[nextR][nextC].Horizontal == tree) {
                        return false;
                    }
                }
                if (cur.r + 1 == goalPointcoor[0] && cur.c == goalPointcoor[1] && !goalPoint) {
                    flag = Math.min(flag, field[cur.r][cur.c].Horizontal + 1);
                }
                if (field[cur.r + 1][cur.c].Horizontal > field[cur.r][cur.c].Horizontal + 1) {
                    field[cur.r + 1][cur.c].Horizontal = field[cur.r][cur.c].Horizontal + 1;
                    q.add(new pos(cur.r + 1, cur.c, false));
                }
                break;
            case 3:
                // 위로 이동
                for (int i = 0; i < HUDR.length; i++) {
                    int nextR = cur.r + HUDR[i];
                    int nextC = cur.c + HUDC[i];
                    if (nextR < 0 || nextR >= N || nextC < 0 || nextC >= N || field[nextR][nextC].Horizontal == tree) {
                        return false;
                    }
                }
                if (cur.r - 1 == goalPointcoor[0] && cur.c == goalPointcoor[1] && !goalPoint) {
                    flag = Math.min(flag, field[cur.r][cur.c].Horizontal + 1);
                }
                if (field[cur.r - 1][cur.c].Horizontal > field[cur.r][cur.c].Horizontal + 1) {
                    field[cur.r - 1][cur.c].Horizontal = field[cur.r][cur.c].Horizontal + 1;
                    q.add(new pos(cur.r - 1, cur.c, false));
                }
                break;
            case 4:
                // 회전
                for (int i = 0; i < ALLDC.length; i++) {
                    int nextR = cur.r + ALLDR[i];
                    int nextC = cur.c + ALLDC[i];
                    if (nextR < 0 || nextR >= N || nextC < 0 || nextC >= N || field[nextR][nextC].Horizontal == tree) {
                        return false;
                    }
                }
                if (cur.r == goalPointcoor[0] && cur.c == goalPointcoor[1] && goalPoint) {
                    flag = Math.min(flag, field[cur.r][cur.c].Horizontal + 1);
                }
                if (field[cur.r][cur.c].Vertical > field[cur.r][cur.c].Horizontal + 1) {
                    field[cur.r][cur.c].Vertical = field[cur.r][cur.c].Horizontal + 1;
                    q.add(new pos(cur.r, cur.c, true));
                }
        }
        return true;
    }
}

package (이름); 를 때고, class 이름을 Main으로 변경하면 된다.

📌 추가 예제

[Input]
5
00011
BBB00
00011
00000
EEE00

[Output]
3

[Input]
7
0000000
0E00000
0E00BBB
0E01001
0000000
0000001
0100000

[Output]
5

[Input]
7
0000000
0E00000
0E00BBB
0E01001
0000000
0000001
0100000

[Output]
5

---

개인 공부 기록용 블로그입니다.
틀리거나 오류가 있을 경우 제보해주시면 감사하겠습니다.😁