[프로그래머스] 블록 이동하기

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/60063

문제 풀이

• 상세한 구현이 필요한 BFS 문제이다.
• 단순 상하 좌우 이동 외에 회전 이동이 있기 때문에 BFS에서 각 status를 다음과 같이 표시했다.

  Point (int x, int y, int d, int t)

  • x : 기준 x값, y: 기준 y값, d: 기준 방향값, t: 현재까지 걸린 시간
  • 가로 모양의 경우 왼쪽 블럭 좌표가 (x, y)일 경우 -> Point(x, y, 0, t)
  • 세로 모양의 경우 위쪽 블럭 좌표가 (x, y)일 경우 -> Point(x, y, 1, t)

• 각 status에 대해 4방향 수평이동, 4방향 회전이동을 구현하였다. (더 간단한 방법이 있을듯..)
• 방문체크는 chk[x][y][d] 형식으로 구현하였다.

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public class Point {
        int x, y, d, t;

        public Point (int x, int y, int d, int t) {
            this.x = x;
            this.y = y;
            this.d = d;
            this.t = t;
        }
    }

    public int N;
    public int[][] map;
    public boolean[][][] chk;

    //0:동, 1:남, 2:서, 3:북, 4:동남, 5:남서, 6:북서, 7:북동
    public int[] dx = {0, 1, 0, -1, 1, 1, -1, -1};
    public int[] dy = {1, 0, -1, 0, 1, -1, -1, 1};

    public boolean chkBoundAndBlock(int X1, int Y1, int X2, int Y2) {
        if (X1 < 0 || X2 < 0 || Y1 < 0 || Y2 < 0 ||
                X1 >= N || X2 >= N || Y1 >= N || Y2 >= N ||
                map[X1][Y1] == 1 || map[X2][Y2] == 1) return true;
        return false;
    }

    public int solution(int[][] board) {
        //초기화 
        N = board.length;
        map = board;
        chk = new boolean[N][N][2];

        //bfs 시작 
        Queue<Point> q = new ArrayDeque<>();
        chk[0][0][0] = true;
        q.add(new Point(0, 0, 0, 0));

        while(!q.isEmpty()) {
            Point cur = q.poll();
            //결과 리턴 
            if ((cur.x == N - 1 && cur.y == N - 1) || (cur.x + dx[cur.d] == N - 1 && cur.y + dy[cur.d] == N - 1))
                return cur.t;
            int X1, Y1, X2, Y2;
            //동서남북 이동 
            for (int d = 0; d < 4; d++) {
                X1 = cur.x + dx[d];
                Y1 = cur.y + dy[d];
                X2 = X1 + dx[cur.d];
                Y2 = Y1 + dy[cur.d];
                if (chkBoundAndBlock(X1, Y1, X2, Y2)) continue;
                if (chk[X1][Y1][cur.d]) continue;
                chk[X1][Y1][cur.d] = true;
                q.add(new Point(X1, Y1, cur.d, cur.t + 1));
            }

            //대각선 회전 이동 
            //가로 방향일 때 
            if (cur.d == 0) {
                for (int d = 4; d < 8; d++) {
                    int chkD;
                    //조건 확인 방향 
                    if (d == 4 || d == 5) chkD = 1;
                    else chkD = 3;
                    X1 = cur.x + dx[chkD];
                    Y1 = cur.y + dy[chkD];
                    X2 = X1 + dx[cur.d];
                    Y2 = Y1 + dy[cur.d];
                    if (chkBoundAndBlock(X1, Y1, X2, Y2)) continue;
                    if (d == 4) {
                        if (chk[cur.x + dx[cur.d]][cur.y + dy[cur.d]][1]) continue;
                        chk[cur.x + dx[cur.d]][cur.y + dy[cur.d]][1] = true;
                        q.add(new Point(cur.x + dx[cur.d], cur.y + dy[cur.d], 1, cur.t + 1));
                    } else if (d == 5) {
                        if (chk[cur.x][cur.y][1]) continue;
                        chk[cur.x][cur.y][1] = true;
                        q.add(new Point(cur.x, cur.y, 1, cur.t + 1));
                    } else if (d == 6) {
                        if (chk[X1][Y1][1]) continue;
                        chk[X1][Y1][1] = true;
                        q.add(new Point(X1, Y1, 1, cur.t + 1));
                    } else {
                        if (chk[X2][Y2][1]) continue;
                        chk[X2][Y2][1] = true;
                        q.add(new Point(X2, Y2, 1, cur.t + 1));
                    }
                }
            }
            //세로 방향일 때 
            else {
                for (int d = 4; d < 8; d++) {
                    int chkD;
                    //조건 확인 방향 
                    if (d == 4 || d == 7) chkD = 0;
                    else chkD = 2;
                    X1 = cur.x + dx[chkD];
                    Y1 = cur.y + dy[chkD];
                    X2 = X1 + dx[cur.d];
                    Y2 = Y1 + dy[cur.d];
                    if (chkBoundAndBlock(X1, Y1, X2, Y2)) continue;
                    if (d == 4) {
                        if (chk[cur.x + dx[cur.d]][cur.y + dy[cur.d]][0]) continue;
                        chk[cur.x + dx[cur.d]][cur.y + dy[cur.d]][0] = true;
                        q.add(new Point(cur.x + dx[cur.d], cur.y + dy[cur.d], 0, cur.t + 1));
                    } else if (d == 5) {
                        if (chk[X2][Y2][0]) continue;
                        chk[X2][Y2][0] = true;
                        q.add(new Point(X2, Y2, 0, cur.t + 1));
                    } else if (d == 6) {
                        if (chk[X1][Y1][0]) continue;
                        chk[X1][Y1][0] = true;
                        q.add(new Point(X1, Y1, 0, cur.t + 1));
                    } else {
                        if (chk[cur.x][cur.y][0]) continue;
                        chk[cur.x][cur.y][0] = true;
                        q.add(new Point(cur.x, cur.y, 0, cur.t + 1));
                    }
                }
            }
        }


        return 0;
    }
}