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

문제

programmers.co.kr/learn/courses/30/lessons/60063

코딩테스트 연습 - 블록 이동하기

문제해결방법

로봇이 가로로 있는 경우와 세로로 있는 경우를 다른 배열로 관리해서 문제를 풀었다.

1. 기존 방향을 유지하면서 이동하면 같은 방향의 배열에 기록해주고, 회전을 하면 다른 방향의 배열에 기록해준다.

2. 로봇을 이동할 때, 두 칸 중 하나라도 0이면 이동한다.

3. 위 두 가지 규칙을 지키면서 BFS를 돌며 N, N 칸에 도착하면 그 값을 출력해줬다.

코드

package Programmers;
 
import java.util.ArrayDeque;
import java.util.Queue;
 
public class Solution_블록이동하기 {
 
    public static int n;
    public static int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public static int[][] map;
    public static int[][][] count;
    
    public static boolean isMove(int x, int y) {
        if(x>=0 && x<n && y>=0 && y<n && map[x][y]==0) return true;
        return false;
    }
    
    public static int bfs(int i1, int j1, int i2, int j2, int k) {
        int second = 1;
        count[k][i1][j1] = second;
        count[k][i2][j2] = second;
        second++;
        Queue<int[]> q = new ArrayDeque<int[]>();
        q.add(new int[] {i1, j1, i2, j2, k});
        while(!q.isEmpty()) {
            int size = q.size();
            for(int s = 0; s<size; s++) {
                int[] cur = q.poll();
                int x1 = cur[0];
                int y1 = cur[1];
                int x2 = cur[2];
                int y2 = cur[3];
                for(int d=0; d<dir.length; d++) {
                    int xx1 = x1+dir[d][0];
                    int yy1 = y1+dir[d][1];
                    int xx2 = x2+dir[d][0];
                    int yy2 = y2+dir[d][1];
                    if(isMove(xx1, yy1) && isMove(xx2, yy2)) {
                        if(count[cur[4]][xx1][yy1]==0 || count[cur[4]][xx2][yy2]==0) {
                            count[cur[4]][xx1][yy1] = second;
                            count[cur[4]][xx2][yy2] = second;
                            q.add(new int[] {xx1, yy1, xx2, yy2, cur[4]});
                        }
                    }
                }
                if(cur[4]==0) {
                    if(isMove(x1-1, y1) && isMove(x1-1, y2)) {
                        if(count[1][x1-1][y1]==0) {
                            count[1][x1][y1]=second;
                            count[1][x1-1][y1]=second;
                            q.add(new int[] {x1, y1, x1-1, y1, 1});
                        }
                        if(count[1][x1-1][y2]==0) {
                            count[1][x1][y2]=second;
                            count[1][x1-1][y2]=second;
                            q.add(new int[] {x1, y2, x1-1, y2, 1});
                        }
                    }
                    if(isMove(x1+1, y1) && isMove(x1+1, y2)) {
                        if(count[1][x1+1][y1]==0) {
                            count[1][x1][y1]=second;
                            count[1][x1+1][y1]=second;
                            q.add(new int[] {x1, y1, x1+1, y1, 1});
                        }
                        if(count[1][x1+1][y2]==0) {
                            count[1][x1][y2]=second;
                            count[1][x1+1][y2]=second;
                            q.add(new int[] {x1, y2, x1+1, y2, 1});
                        }
                    }
                } else {    // 세로
                    if(isMove(x1, y1-1) && isMove(x2, y1-1)) {
                        if(count[0][x1][y1-1]==0) {
                            count[0][x1][y1]=second;
                            count[0][x1][y1-1]=second;
                            q.add(new int[] {x1, y1, x1, y1-1, 0});
                        }
                        if(count[0][x2][y1-1]==0) {
                            count[0][x2][y1]=second;
                            count[0][x2][y1-1]=second;
                            q.add(new int[] {x2, y1, x2, y1-1, 0});
                        }
                    }
                    if(isMove(x1, y1+1) && isMove(x2, y1+1)) {
                        if(count[0][x1][y1+1]==0) {
                            count[0][x1][y1]=second;
                            count[0][x1][y1+1]=second;
                            q.add(new int[] {x1, y1, x1, y1+1, 0});
                        }
                        if(count[0][x2][y1+1]==0) {
                            count[0][x2][y1]=second;
                            count[0][x2][y1+1]=second;
                            q.add(new int[] {x2, y1, x2, y1+1, 0});
                        }
                    }
                }
                if(count[0][n-1][n-1]!=0 || count[1][n-1][n-1]!=0) return second-1; 
            }
            second++;
        }
        return 0;
    }
    
    public static int solution(int[][] board) {
        int answer = 0;
        map = board;
        n = board.length;
        count = new int[2][n][n];
        answer = bfs(0, 0, 0, 1, 0);
        return answer;
    }
    
    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));
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.