[코드 트리] 2차원 바람 (JAVA)

[코드 트리] 2차원 바람 (JAVA)

🗒️알고리즘 분류

#시뮬레이션 #simulation

📌기억해야 할 포인트

이 문제는 프로그래머스의 행렬 테두리 회전하기 문제와 매우 유사하다.

이 문제의 가장 키 포인트는 직사각형 영역의 경계에 있는 숫자들을 시계 방향으로 한칸씩 shift 를 어떻게 하는 것에 있다.

나는 여기서 DX, DY 로 직사각형의 4 방향을 지정해두고, 직사각형의 맨 왼쪽 위의 꼭짓점 값을 temp = arr[R1][C1] 에 넣어준다. 그리고 해당 값 부터 시작해서 한칸씩 값을 바꿔나가기로 했다.

이때 주의할 점은 temp 는 while 문의 바깥쪽에, swapTemp 는 while 문의 안쪽에 선언하는 것이다. swapTemp 로 temp 값을 하나 더 지정해주어서 값을 하나씩 바꾸고, temp 에 swapTemp 를 다시 저장해주는 것이다. 저장해둔 temp 값을 다음 반복문에 다시 재사용하는 것이다.
그리고 직사각형의 경계선 즉, 직사각형의 4개의 각 꼭짓점에 도달하면 방향을 바꿔주는 turn() 메서드를 구현했다.

맨 왼쪽 위의 꼭짓점을 기준으로 처음에는 오른쪽 방향(0,1)➡️, 그 다음은 아래 방향(1,0)⬇️, 왼쪽 방향(0,-1)⬅️, 마지막으로 윗방향(-1,0)⬆️ 으로 방향을 바꿔주며(direction = turn(x, y, direction);)직사각형의 경계값을 돌아다니며 값을 한칸씩 옆으로 옮긴다.

private static int[] DX = {0,1,0,-1};
private static int[] DY = {1,0,-1,0};

private static void rotateClockwise(int[][] arr, int[] query) {
        R1 = query[0]-1;
        C1 = query[1]-1;
        R2 = query[2]-1;
        C2 = query[3]-1;

        int x = R1, y = C1, temp = arr[R1][C1], direction = 0;

        while (true) {
            int nx = x + DX[direction];
            int ny = y + DY[direction];

            int swapTemp = arr[nx][ny];
            arr[nx][ny] = temp;
            temp = swapTemp;
                
            x = nx;
            y = ny;
                
            direction = turn(x, y, direction);
                
            if (x == R1 && y == C1) {
                break;
            }
        }        
    }

    private static int turn(int x, int y, int direction) {
        // 오른쪽 위의 꼭짓점이면 아래 방향으로 방향 바꾸기
        if (x == R1 && y == C2) {
            return 1;
        // 오른쪽 아래의 꼭짓점이면 왼쪽 방향으로 방향 바꾸기
        } else if (x == R2 && y == C2) {
            return 2;
        // 왼쪽 아래의 꼭직점이면 위로 방향으로 방향 바꾸기
        } else if (x == R2 && y == C1) {
            return 3;
        }
        // 경계값이 아니라면 그대로 자기 자신의 값 반환
        return direction;
    }

해설에서는 내가 구현한 것을 거꾸로 구현했다.

먼저, 맨 왼쪽 위의 꼭짓점 값을 기준으로 temp 에 값을 저장하고,

1. 가장 왼쪽 열을 위로 한칸씩 옮기고⬆️
2. 가장 아래 행을 왼쪽으로 한칸씩 옮기고⬅️
3. 가장 오른쪽 열을 아래로 한칸씩 옮기고⬇️
4. 가장 위 열을 오른쪽으로 한칸씩 옮겨준다.➡️

마지막으로 temp 의 값을 맨 왼쪽 위 꼭짓점의 바로 한칸 오른쪽에 값을 넣어준다.

// 직사각형의 경계에 있는 숫자들을 시계 방향으로 한 칸씩 회전해줍니다.
public static void rotate(int startRow, int startCol, int endRow, int endCol) {
        // Step1-1. 직사각형 가장 왼쪽 위 모서리 값을 temp에 저장합니다.
        int temp = a[startRow][startCol];
    
        // Step1-2. 직사각형 가장 왼쪽 열을 위로 한 칸씩 shift 합니다.
        for(int row = startRow; row < endRow; row++)
            a[row][startCol] = a[row + 1][startCol];
        
        // Step1-3. 직사각형 가장 아래 행을 왼쪽으로 한 칸씩 shift 합니다.
        for(int col = startCol; col < endCol; col++)
            a[endRow][col] = a[endRow][col + 1];
    
        // Step1-4. 직사각형 가장 오른쪽 열을 아래로 한 칸씩 shift 합니다.
        for(int row = endRow; row > startRow; row--)
            a[row][endCol] = a[row - 1][endCol];
        
        // Step1-5. 직사각형 가장 위 행을 오른쪽으로 한 칸씩 shift 합니다.
        for(int col = endCol; col > startCol; col--)
            a[startRow][col] = a[startRow][col - 1];
    
        // Step1-6. temp를 가장 왼쪽 위 모서리를 기준으로 바로 오른쪽 칸에 넣습니다. 
        a[startRow][startCol + 1] = temp;
}

📝풀이 코드(JAVA)

import java.util.*;

public class Main {
    private static int N = 0;
    private static int M = 0;
    private static int R1 = 0, C1 = 0, R2 = 0, C2 = 0;
    private static int[] DX = {0,1,0,-1};
    private static int[] DY = {1,0,-1,0};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();

        int[][] arr = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = sc.nextInt();
            }
        }

        int[][] queries = new int[q][4];
        for (int i = 0; i < q; i++) {
            for (int j = 0; j < 4; j++) {
                queries[i][j] = sc.nextInt();
            }
        }

        N = n;
        M = m;

        for (int[] query : queries) {
            rotateClockwise(arr, query);
            avg(arr, query);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
        return;
    }

    private static void rotateClockwise(int[][] arr, int[] query) {
        R1 = query[0]-1;
        C1 = query[1]-1;
        R2 = query[2]-1;
        C2 = query[3]-1;

        int x = R1, y = C1, temp = arr[R1][C1], direction = 0;

        while (true) {
            int nx = x + DX[direction];
            int ny = y + DY[direction];

            int swapTemp = arr[nx][ny];
            arr[nx][ny] = temp;
            temp = swapTemp;
                
            x = nx;
            y = ny;
                
            direction = turn(x, y, direction);
                
            if (x == R1 && y == C1) {
                break;
            }
        }        
    }

    private static int turn(int x, int y, int direction) {
        if (x == R1 && y == C2) {
            return 1;
        } else if (x == R2 && y == C2) {
            return 2;
        } else if (x == R2 && y == C1) {
            return 3;
        }
        return direction;
    }

    private static void avg(int[][] arr, int[] query) {
        R1 = query[0]-1;
        C1 = query[1]-1;
        R2 = query[2]-1;
        C2 = query[3]-1;

        List<Integer> avgs = new ArrayList<>();
        for (int i = R1; i <= R2; ++i) {
            for (int j = C1; j <= C2; ++j) {
                avgs.add(getAvg(arr, i, j));
            }
        }

        int index = 0;
         for (int i = R1; i <= R2; ++i) {
            for (int j = C1; j <= C2; ++j) {
                arr[i][j] = avgs.get(index++);
            }
        }
    }

    private static int getAvg(int[][] arr, int x, int y) {
        int[] nums = new int[4];
        nums[0] = isInRange(x-1, y) ? arr[x-1][y] : -1;
        nums[1] = isInRange(x+1, y) ? arr[x+1][y] : -1;
        nums[2] = isInRange(x, y-1) ? arr[x][y-1] : -1;
        nums[3] = isInRange(x, y+1) ? arr[x][y+1] : -1;

        int count = 5;
        for (int i = 0; i < 4; ++i) {
            if (nums[i] < 0) {
                --count;
                nums[i] = 0;
            }
        }

        return (arr[x][y] + nums[0] + nums[1] + nums[2] + nums[3]) / count;
    }

    private static boolean isInRange(int x, int y) {
        return 0 <= x && x < N && 0 <= y && y < M;
    }
}

⏰총 풀이시간

• 90분