[JAVA] BOJ 백준 1938번 - 통나무 옮기기

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

1938번: 통나무 옮기기

---

2. 내가 푼 방법

DFS 알고리즘을 이용했고, 전에 방문했을 때보다 더 적은 동작 횟수로 방문할 경우에만 재탐색할 수 있도록 가지치기했다. 방문한 경로임을 확인하기 위해 통나무의 중심(가운데 값)을 기준으로 동작 횟수를 저장했다. 또한, 현재 위치의 통나무 모양이 가로, 세로인지에 따라 달라진다.

 

먼저 회전 동작을 수행하는데, canTurn() 함수는 통나무의 중심을 기준으로 상하좌우, 대각선에 나무가 존재하지 않는지 확인한다. 만약 존재하지 않는다면 turn() 함수를 통해 회전을 하고, isVisit() 함수를 통해 방문할 수 있는지 확인을 받는다.

 

다음으로 이동 동작을 수행하기 위해 canMove() 함수로 범위를 벗어나는지 혹은 나무가 존재하는지 확인한다. 만약 이러한 검사가 통과되었다면 move() 함수를 통해 이동을 하고, isVisit() 함수를 통해 방문할 수 있는지를 확인받는다.

 

public static void solution() {
    int shape = (Math.abs(stick[0][0] - stick[1][0]) == 1) ? 0 : 1;

    visit[shape][stick[1][0]][stick[1][1]] = 1;
    dfs(shape, 1);
}

public static void dfs(int shape, int move) {
    if (checkCorrect()) {
        result = move - 1;
        return;
    }

    // 회전
    if (canTurn()) {
        turn();

        int nextShape = (shape + 1) % 2;
        if (!isVisit(nextShape, move + 1)) {
            dfs(nextShape, move + 1);
        }

        turn();
    }

    for (int d = 0; d < 4; d++) {
        if (canMove(d)) {
            move(d);

            if (!isVisit(shape, move + 1)) {
                dfs(shape, move + 1);
            }

            move((d + 2) % 4);
        }
    }
}

public static void move(int d) {
    for (int s = 0; s < len; s++) {
        stick[s][0] = stick[s][0] + dx[d];
        stick[s][1] = stick[s][1] + dy[d];
    }
}

public static boolean canMove(int d) {
    for (int s = 0; s < len; s++) {
        int nx = stick[s][0] + dx[d];
        int ny = stick[s][1] + dy[d];

        if (nx < 0 || ny < 0 || nx >= N || ny >= N) return false;
        if (arr[nx][ny] == '1') return false;
    }

    return true;
}

public static boolean checkCorrect() {
    for (int s = 0; s < len; s++) {
        if (arr[stick[s][0]][stick[s][1]] != 'E') {
            return false;
        }
    }
    return true;
}

public static boolean isVisit(int shape, int movement) {
    int standard = visit[shape][stick[1][0]][stick[1][1]];

    if (standard != 0 && standard <= movement) return true;

    visit[shape][stick[1][0]][stick[1][1]] = movement;
    return false;
}

public static void turn() {
    if (stick[0][0] == stick[1][0]) {
        stick[0][1] = stick[2][1] = stick[1][1];
        stick[0][0] = stick[1][0] - 1;
        stick[2][0] = stick[1][0] + 1;
    }
    else {
        stick[0][0] = stick[2][0] = stick[1][0];
        stick[0][1] = stick[1][1] - 1;
        stick[2][1] = stick[1][1] + 1;
    }
}

public static boolean canTurn() {
    for (int d = 0; d < dx.length; d++) {
        int nx = stick[1][0] + dx[d];
        int ny = stick[1][1] + dy[d];

        if (nx < 0 || ny < 0 || nx >= N || ny >= N || arr[nx][ny] == '1') {
            return false;
        }
    }

    return true;
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B1938.java

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

class Main {
    static int N, len;
    static char[][] arr;
    static int[][][] visit; // 가운데 통나무 기준
    static int[][] stick;
    static int[] dx = {-1, 0, 1, 0, -1, -1, 1, 1};
    static int[] dy = {0, -1, 0, 1, -1, 1, -1, 1};
    static int result;

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

    public static void solution() {
        int shape = (Math.abs(stick[0][0] - stick[1][0]) == 1) ? 0 : 1;

        visit[shape][stick[1][0]][stick[1][1]] = 1;
        dfs(shape, 1);
    }

    public static void dfs(int shape, int move) {
        if (checkCorrect()) {
            result = move - 1;
            return;
        }

        // 회전
        if (canTurn()) {
            turn();

            int nextShape = (shape + 1) % 2;
            if (!isVisit(nextShape, move + 1)) {
                dfs(nextShape, move + 1);
            }

            turn();
        }

        for (int d = 0; d < 4; d++) {
            if (canMove(d)) {
                move(d);

                if (!isVisit(shape, move + 1)) {
                    dfs(shape, move + 1);
                }

                move((d + 2) % 4);
            }
        }
    }

    public static void move(int d) {
        for (int s = 0; s < len; s++) {
            stick[s][0] = stick[s][0] + dx[d];
            stick[s][1] = stick[s][1] + dy[d];
        }
    }

    public static boolean canMove(int d) {
        for (int s = 0; s < len; s++) {
            int nx = stick[s][0] + dx[d];
            int ny = stick[s][1] + dy[d];

            if (nx < 0 || ny < 0 || nx >= N || ny >= N) return false;
            if (arr[nx][ny] == '1') return false;
        }

        return true;
    }

    public static boolean checkCorrect() {
        for (int s = 0; s < len; s++) {
            if (arr[stick[s][0]][stick[s][1]] != 'E') {
                return false;
            }
        }
        return true;
    }

    public static boolean isVisit(int shape, int movement) {
        int standard = visit[shape][stick[1][0]][stick[1][1]];

        if (standard != 0 && standard <= movement) return true;

        visit[shape][stick[1][0]][stick[1][1]] = movement;
        return false;
    }

    public static void turn() {
        if (stick[0][0] == stick[1][0]) {
            stick[0][1] = stick[2][1] = stick[1][1];
            stick[0][0] = stick[1][0] - 1;
            stick[2][0] = stick[1][0] + 1;
        }
        else {
            stick[0][0] = stick[2][0] = stick[1][0];
            stick[0][1] = stick[1][1] - 1;
            stick[2][1] = stick[1][1] + 1;
        }
    }

    public static boolean canTurn() {
        for (int d = 0; d < dx.length; d++) {
            int nx = stick[1][0] + dx[d];
            int ny = stick[1][1] + dy[d];

            if (nx < 0 || ny < 0 || nx >= N || ny >= N || arr[nx][ny] == '1') {
                return false;
            }
        }

        return true;
    }

    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result+"");

        bw.flush();
        bw.close();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        len = 3;
        arr = new char[N][N];
        visit = new int[2][N][N];
        stick = new int[len][2];

        for (int s = 0; s < len; s++) {
            stick[s][0] = -1;
        }

        for (int i = 0; i < N; i++) {
            String line = br.readLine();

            for (int j = 0; j < N; j++) {
                arr[i][j] = line.charAt(j);

                if (arr[i][j] == 'B') {
                    for (int s = 0; s < len; s++) {
                        if (stick[s][0] == -1) {
                            stick[s][0] = i;
                            stick[s][1] = j;
                            break;
                        }
                    }
                }
            }
        }

        br.close();
    }
}

---

4. 결과 및 회고

이 문제는 세 칸이 고정이어서 다행이지,, 막대 모양이 아니었다면 어떻게 풀어야 할지 까마득한 문제인 것 같다. 아닌가 똑같이 key가 되는 위치 고르고, 그 위치만 기억하면 될 것 같다. 물론 회전이나 이동을 위한 구현은 훨씬 더 어려워지겠지.. ㅎㅎ