[프로그래머스/Lv. 2] 행렬 테두리 회전하기 (JAVA)

🔺 문제

프로그래머스

 

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static int[] dx = {1,0,-1,0};    // 시계 방향 회전이지만 반시계 방향에서 값 가져올 것이므로 반시계 방향 선언 (남동북서)
    static int[] dy = {0,1,0,-1};
    
    static int rows, columns;
    static int[][] queries, arr;
    static int min;
    
    public int[] solution(int rows, int columns, int[][] queries) {
        this.rows = rows;
        this.columns = columns;
        this.queries = queries;
        
        int[] answer = new int[queries.length];
        
        // 배열 초기화
        arr = new int[rows][columns];
        int val = 1;
        for(int i = 0 ; i < rows ; i++) {
            for(int j = 0 ; j < columns ; j++) {
                arr[i][j] = val++;
            }
        }
        
        for(int i = 0 ; i < queries.length ; i++) {
            min = Integer.MAX_VALUE;
            answer[i] = simulate(queries[i]);
        }      
        
        return answer;
    }
    
    private static int simulate(int[] query) {
        int x1 = query[0] - 1;
        int y1 = query[1] - 1;
        int x2 = query[2] - 1;
        int y2 = query[3] - 1;
        
        int tmp = arr[x1][y1]; // 첫 번째 요소
        int dir = 0;    // 시작 방향
        
        int x = x1;
        int y = y1;
        
        while(dir < 4) { // 4방향 시계방향 회전 (=> 테두리만 회전)
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            
            if(nx < x1 || ny < y1 || nx > x2 || ny > y2) {  // 지정 범위 벗어나면, 회전 방향 번경
                dir++;
            }
            else {    // 범위 안 벗어나면, 정상 이동
                arr[x][y] = arr[nx][ny]; // 반시계 방향에서 값 끌어오기 ⭐
                min = Math.min(min, arr[x][y]); // 가져올 최솟값 갱신
                x = nx;
                y = ny;
            }
        }
        
        arr[x][y + 1] = tmp; // 배열 회전 시 마지막 요소를 첫 번째 요소로 이동시킴
        min = Math.min(min, arr[x][y + 1]);
        
        return min;       
    }
}

 

 

 

🧩  해결 아이디어

• 완전탐색 (구현)

- 시계 방향(동남서북 순서)로 회전하며 최솟값을 찾아 갱신한다.

  ┗ 값을 시계 방향 회전할 것이지만, 반시계 방향 위치의 값을 "끌어와" 가져올 것이므로 dx/dy 배열은 반시계 방향(남동북서)으로 선언해 활용한다.

- 테두리만 회전시키고자, 방향 배열 dx,dy의 길이만큼 (=한 바퀴 돌기 전까지)만 수행한다.

- 이동하다가 지정 범위를 벗어나면, 회전 방향을 변경한다.

- 이동하다가 지정 범위를 벗어나지 않으면, 정상적으로 이동하고, 최솟값을 갱신한다.

 

 

---

🔺 다른 풀이들

 - BFS를 활용하셨다.

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;
    }
}

 

 

- 테두리 줄마다 회전 단순 구현

velog

---

💬 느낀 점

달팽이 문제(?)라 어떻게 푸는지는 알았는데

시계방향 회전인데 dx dy 배열이 왜 저렇게 설정됐는지 이해가 잘...

 

복습을 해야겠찌...

 

1회독	2회독	3회독	4회독	5회독
V	240211

---

(참고)

✔ 풀이 참고

[프로그래머스] 행렬 테두리 회전하기 JAVA

 

 

 

✔ 비슷한 문제

16926번: 배열 돌리기 1