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

생각보다 LV.3에 구현 문제가 대부분이다.

구현 문제여도 난이도가 높을 수 있다는 걸 깨달음과 동시에 dfs, bfs를 까먹어가고 있음을 느낀다...

여러 조건을 따져야 하는 문제였지만, 차근차근 풀다 보면 해결할 수 있었던 문제였다!

 

바보같이 조건 잘못 달아놓고 다른 데서 원인 찾고 있다가 틀림...

import java.util.ArrayDeque;
import java.util.Queue;

public class Solution {

    public static class Position {
        int r1, c1, r2, c2, cnt;

        public Position(int r1, int c1, int r2, int c2, int cnt) {
            this.r1 = r1;
            this.c1 = c1;
            this.r2 = r2;
            this.c2 = c2;
            this.cnt = cnt;
        }

    }

    public static void main(String[] args) {
        int[][] board = {{0, 0, 0, 1, 1}, {0, 0, 0, 1, 0}, {0, 1, 0, 1, 1}, {1, 1, 0, 0, 1}, {0, 0, 0, 0, 0}};
        System.out.println(solution(board));
    }

    public static int solution(int[][] board) {
        int n = board.length;
        int m = board[0].length;
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};
        boolean[][][][] visited = new boolean[n][m][n][m];
        Position start = new Position(0, 0, 0, 1, 0);

        Queue<Position> q = new ArrayDeque<>();
        visited[0][0][0][1] = true;
        q.add(start);

        while(!q.isEmpty()) {
            Position p = q.poll();

            if((p.r1 == n - 1 && p.c1 == n - 1) || (p.r2 == n - 1 && p.c2 == n - 1)) return p.cnt;

            for(int d = 0; d < 4; d++) {
                int nr1 = p.r1 + dr[d];
                int nr2 = p.r2 + dr[d];
                int nc1 = p.c1 + dc[d];
                int nc2 = p.c2 + dc[d];
                if(check(nr1, nr2, nc1, nc2, n, m) && board[nr1][nc1] == 0 && board[nr2][nc2] == 0
                        &&!visited[nr1][nc1][nr2][nc2]) {
                    q.add(new Position(nr1, nc1, nr2, nc2, p.cnt + 1));
                    visited[nr1][nc1][nr2][nc2] = true;
                }
            }

            // 세로인 경우
            if(p.c1 == p.c2) {
                if(p.c1 > 0 && board[p.r1][p.c1 - 1] == 0 && board[p.r2][p.c2 - 1] == 0) {
                   if(!visited[p.r1][p.c1][p.r1][p.c1 - 1]) {
                       q.add(new Position(p.r1, p.c1, p.r1, p.c1 - 1, p.cnt + 1));
                       visited[p.r1][p.c1][p.r1][p.c1 - 1] = true;
                   }

                   if(!visited[p.r2][p.c2 - 1][p.r2][p.c2]) {
                       q.add(new Position(p.r2, p.c2 - 1, p.r2, p.c2, p.cnt + 1));
                       visited[p.r2][p.c2 - 1][p.r2][p.c2] = true;
                   }
                }

                if(p.c1 < m - 1 && board[p.r1][p.c1 + 1] == 0 && board[p.r2][p.c2 + 1] == 0) {
                    if(!visited[p.r1][p.c1][p.r1][p.c1 + 1]) {
                        q.add(new Position(p.r1, p.c1, p.r1, p.c1 + 1, p.cnt + 1));
                        visited[p.r1][p.c1][p.r1][p.c1 + 1] = true;
                    }

                    if(!visited[p.r2][p.c2 + 1][p.r2][p.c2]) {
                        q.add(new Position(p.r2, p.c2 + 1, p.r2, p.c2, p.cnt + 1));
                        visited[p.r2][p.c2 + 1][p.r2][p.c2] = true;
                    }
                }
            }

            // 가로인 경우
            if(p.r1 == p.r2) {
                if(p.r1 > 0 && board[p.r1 - 1][p.c1] == 0 && board[p.r2 - 1][p.c2] == 0) {
                    if(!visited[p.r2 - 1][p.c2][p.r2][p.c2]) {
                        q.add(new Position(p.r2 - 1, p.c2, p.r2, p.c2, p.cnt + 1));
                        visited[p.r2 - 1][p.c2][p.r2][p.c2] = true;
                    }

                    if(!visited[p.r1][p.c1][p.r1 - 1][p.c1]) {
                        q.add(new Position(p.r1, p.c1, p.r1 - 1, p.c1, p.cnt + 1));
                        visited[p.r1][p.c1][p.r1 - 1][p.c1] = true;
                    }
                }

                if(p.r1 < n - 1 && board[p.r1 + 1][p.c1] == 0 && board[p.r2 + 1][p.c2] == 0) {
                    if(!visited[p.r2 + 1][p.c2][p.r2][p.c2]) {
                        q.add(new Position(p.r2 + 1, p.c2, p.r2, p.c2, p.cnt + 1));
                        visited[p.r2 + 1][p.c2][p.r2][p.c2] = true;
                    }

                    if(!visited[p.r1][p.c1][p.r1 + 1][p.c1]) {
                        q.add(new Position(p.r1, p.c1, p.r1 + 1, p.c1, p.cnt + 1));
                        visited[p.r1][p.c1][p.r1 + 1][p.c1] = true;
                    }
                }
            }

        }
        return -1;
    }

    public static boolean check(int r1, int r2, int c1, int c2, int n, int m) {
        if(0 <= r1 && r1 < n && 0 <= r2 && r2 < n
                && 0 <= c1 && c1 < m && 0 <= c2 && c2 < m) return true;
        return false;
    }

}