[BOJ] 1938 통나무 옮기기

문제 >> [BOJ] 1938. 통나무 옮기기

저는 기본적으로 통나무의 위치를 가운데 좌표와 모양(세로/가로)의 정보로 파악했습니다.

1. 출발 통나무와 도착 통나무의 위치를 저장.

2. bfs로 진행

** 4차원의 visit 배열

• 통나무 모양에 따라서

• 5가지 행위에 대해서

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
 
//BOJ :: 1938 통나무 옮기기     
public class Main1938_통나무옮기기2 {
    private static char[][] map;
    private static boolean[][][][] visit;
    private static int N;
    private static ArrayList<pair> nowLog;
    private static ArrayList<pair> destLog;
    private static log end;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        nowLog = new ArrayList<>();
        destLog = new ArrayList<>();
 
        map = new char[N][N];
        visit = new boolean[5][2][N][N];
 
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = str.charAt(j);
                if (map[i][j] == 'B')
                    nowLog.add(new pair(i, j));
                if (map[i][j] == 'E')
                    destLog.add(new pair(i, j));
 
            }
        } //// input
 
        Collections.sort(nowLog);
        Collections.sort(destLog);
        int type;
        if (nowLog.get(0).y == nowLog.get(1).y) type = 2; else type = 1;
        log start = new log(nowLog.get(1).y, nowLog.get(1).x, type, 0);
 
        if (destLog.get(0).y == destLog.get(1).y) type = 2; else type = 1;
        end = new log(destLog.get(1).y, destLog.get(1).x, type, 0);
        System.out.println(bfs(start));
    } // end of main
 
    static int[] dy = { -1, 1, 0, 0, -1, -1, 1, 1 };
    static int[] dx = { 0, 0, -1, 1, -1, 1, -1, 1 }; // 상하좌우//대각선
 
    public static int bfs(log start) {
 
        Queue<log> q = new LinkedList<>();
        q.add(start);
        // visit[][start.type-1][start.y][start.x] = true;
        while (!q.isEmpty()) {
            log now = q.poll();
            int y = now.y;
            int x = now.x; // 통나무의 mid 정보
            int type = now.type;
            int cnt = now.cnt;
            // 종료조건 확인
            if (y == end.y && x == end.x && type == end.type) {
                return cnt;
            }
 
            for (int i = 0; i < 5; i++) {
                if (i == 4) { // 회전
                    boolean isPossible = true;
                    // 회전할 수 있는 범위 확인.
                    for (int chk = 0; chk < 8; chk++) {
                        int ny = y + dy[chk];
                        int nx = x + dx[chk];
                        if (ny < 0 || ny > N - 1 || nx < 0 || nx > N - 1 || map[ny][nx] == '1') {
                            isPossible = false;
                            break;
                        }
                    }
                    if (!isPossible) continue;
                    int ntype;
                    if (type == 1) ntype = 2;
                    else ntype = 1;
                    if (!visit[i][type - 1][y][x]) {
                        q.add(new log(y, x, ntype, cnt + 1));
                        visit[i][type - 1][y][x] = true;
                    }
 
                } else if (i < 4) {// 상하좌우 이동
                    int ny = y + dy[i];
                    int nx = x + dx[i];
                    if (ny < 0 || ny > N - 1 || nx < 0 || nx > N - 1 || map[ny][nx] == '1'
                            || visit[i][type - 1][ny][nx])
                        continue;
                    if (type == 1) { // |
                        int topY = ny - 1;
                        int bottomY = ny + 1;
                        if (topY < 0 || bottomY > N - 1 || map[topY][nx] == '1' || map[bottomY][nx] == '1') continue;
                    } else { // -
                        int leftX = nx - 1;
                        int rightX = nx + 1;
                        if (leftX < 0 || rightX > N - 1 || map[ny][leftX] == '1' || map[ny][rightX] == '1') continue;
                    }
                    visit[i][type - 1][ny][nx] = true;
                    q.add(new log(ny, nx, type, cnt + 1));
                }
            }
        }
        return 0;
    }
 
    static class log {
        int y;
        int x;
        int type; // 1 : | // 2: -
        int cnt;
        public log(int y, int x, int type, int cnt) {
            super();
            this.y = y;
            this.x = x;
            this.type = type;
            this.cnt = cnt;
        }
    }
 
    static class pair implements Comparable<pair> {
        int y;
        int x;
        public pair(int y, int x) {
            super();
            this.y = y;
            this.x = x;
        }
        @Override
        public int compareTo(pair o) {
            if (o.x == this.x)
                return o.x - this.x;
            else if (o.y == this.y) {
                return o.y - this.y;
            }
            return -1;
        }
    }
}