[프로그래머스/구현] 77485 행렬 테투리 회전하기 - JAVA

문제

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

프로그래머스

 

풀이

구현은 어렵지 않다.

백준의 배열돌리기 문제를 풀 수 있다면 해당 문제도 쉽게 풀 수 있다.

단순 구현하면 다음과 같다. 

import java.util.*;

class Solution {
    static int[][] arr;
    public int[] solution(int rows, int columns, int[][] queries) {
        int[] answer = new int[queries.length];
        arr = new int[rows][columns];
        int cnt = 1;
        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < columns; j++) {
                arr[i][j] = cnt++;
            }
        }
        
        for(int a = 0; a < queries.length; a++) {
            answer[a] = turn(queries[a]);
        }
        
        return answer;
    }
    
    public static int turn(int[] q) {
        int y1 = q[0]-1;
        int x1 = q[1]-1;
        int y2 = q[2]-1;
        int x2 = q[3]-1;
        
        int ans = Integer.MAX_VALUE;
        
        // up
        int temp = arr[y1][x2];
        for(int i = x2; i > x1; i--) {
            arr[y1][i] = arr[y1][i-1];
            ans = Math.min(ans, arr[y1][i]);
        }
        
        // left
        for(int i = y1; i < y2; i++) {
            arr[i][x1] = arr[i+1][x1];
            ans = Math.min(ans, arr[i][x1]);
        }
        
        // bottom
        for(int i = x1; i < x2; i++) {
            arr[y2][i] = arr[y2][i+1];
            ans = Math.min(ans, arr[y2][i]);
        }
        
        //right
        for(int i = y2; i > y1 ; i--) {
            arr[i][x2] = arr[i-1][x2];
            ans = Math.min(ans, arr[i][x2]);
        }
        
        arr[y1+1][x2] = temp;
        ans = Math.min(ans, temp);
        return ans;
    }
}

 

그런데 다른 사람의 풀이를 보니 BFS로도 문제를 해결할 수 있는 것을 보았다. 

https://school.programmers.co.kr/learn/courses/30/lessons/77485/solution_groups?language=java 

해당 방법으로도 접근할 수 있음을 알게되었다..

import java.util.*;

class Solution {
    public int[] solution(int rows, int columns, int[][] queries) {

        int[] answer = new int[queries.length];
        int[][] arr = new int[rows+1][columns+1];
        int num = 1;
        for(int i=1; i<rows+1; i++){
            for(int j=1; j<columns+1; j++){
                arr[i][j] = num++;
            }
        }

        int[] dx = {1,0,-1,0};
        int[] dy = {0,1,0,-1};

        for(int i=0; i<queries.length; i++){
            int x1 = queries[i][0];
            int y1 = queries[i][1];
            int x2 = queries[i][2];
            int y2 = queries[i][3];

            int tmp = arr[x1][y1];
            int d = 0;

            Queue<int[]> q = new LinkedList<>();
            q.offer(new int[] {x1,y1});
            int min = Integer.MAX_VALUE;

            while(true) {
                int[] cur = q.poll();
                int x = cur[0];
                int y = cur[1];

                if(arr[x][y] < min) {
                    min = arr[x][y];
                    answer[i] = min;
                }

                int nx = x + dx[d];
                int ny = y + dy[d];


                if(nx>x2 || ny >y2 || nx < x1 || ny < y1) d++;                                            

                nx = x + dx[d];
                ny = y + dy[d];

                if(nx == x1 && ny == y1){
                    arr[x][y] = tmp;
                    break;
                }

                arr[x][y] = arr[nx][ny];
                q.offer(new int[] {nx, ny});
            }
        }


        return answer;
    }
}