[BAEKJOON] 16926배열돌리기 1 (Java/C++)

[ 문제 ]

크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다.

A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] ↓ ↓ ↑ ↑ A[3][1] A[3][2] → A[3][3] → A[3][4] A[3][5] ↓ ↑ A[4][1] → A[4][2] → A[4][3] → A[4][4] → A[4][5]

예를 들어, 아래와 같은 배열을 2번 회전시키면 다음과 같이 변하게 된다.

1 2 3 4 2 3 4 8 3 4 8 6 5 6 7 8 1 7 7 6 2 7 8 2 9 8 7 6 → 5 6 8 2 → 1 7 6 3 5 4 3 2 9 5 4 3 5 9 5 4 <시작> <회전1> <회전2>

배열과 정수 R이 주어졌을 때, 배열을 R번 회전시킨 결과를 구해보자.

입력

첫째 줄에 배열의 크기 N, M과 수행해야 하는 회전의 수 R이 주어진다.

둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어진다.

출력

입력으로 주어진 배열을 R번 회전시킨 결과를 출력한다.

제한

• 2 ≤ N, M ≤ 300
• 1 ≤ R ≤ 1,000
• min(N, M) mod 2 = 0
• 1 ≤ Aij ≤ 108

[ 핵심풀이 ]

오랜만에풀어봤다. BFS, DFS로 방향을 회전하면서 풀어주어도된다. 예전의 나도 그렇게 풀었다.

하지만 for문에서 index를 돌리는 방법으로 충분히 구현이 가능하다는것을 많이 접했다.

 

0) 시작지점은 (0,0), (1,1), (2,2) 등 좌측상단을 시작꼭짓점으로 생각한다

1) 시작지점의 범위는 [● min(N, M) mod 2 = 0] 문제에서 주어진 제한을따른다

2) 시작지점을 임의변수 temp에 넣고 배열돌리기를 시작한다

3) 방향은 사용자의 마음이나, 나는 가로→ 세로↓ 가로← 세로↑ 순으로 앞배열값을 뒤배열값에 옮겻다.

index = index+1

4) 위 4방향에 대해서 범위밖으로 가지않기위해

첫 2개의 가로세로는 최대범위까지, 후자 2개의 가로세로는 최소범위까지 돌아야한다.

5) 시작지점이 (0,0)일땐 전체배열과 같은 사각형이므로 범위는 순서대로 M N 0 0 이다.

6) 시작지점이 (1,1)일땐 전체배열에서 1만큼 작아진 사각형이므로 범위는 순서대로 M-1 N-1 0+1 0+1 이다.

7) 시작지점이 (idx, idx)일땐 전체배열에서 idx만큼 작아진 사각형이므로

범위는 순서대로 M-idx N-idx 0+idx 0+idx 이다

8) 위대로 구현한 루프를 주어진 회전수 R만큼 더 돌리면된다.

 

*)  3의 조건에의해 풀이에서 첫 2개의 가로세로진행시 최대범위 -1을 해주었다

[ Java / play with index ]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class _16926_배열돌리기_1 {
    static int N, M, R;
    static int ary[][];

    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        ary = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++)
                ary[i][j] = Integer.parseInt(st.nextToken());
        }
    }
    static void solve() {
        // idx = startpoint
        for (int cycle = 0; cycle < R; cycle++) {
            for (int idx = 0; idx < Math.min(N, M) / 2; idx++) {
                int temp = ary[idx][idx];
                int i = idx, j = idx;
                // 가로 <
                for (; j < M - idx - 1; j++)
                    ary[i][j] = ary[i][j + 1];
                // 세로 v
                for (; i < N - idx - 1; i++)
                    ary[i][j] = ary[i + 1][j];
                // 가로 >
                for (; j > 0 + idx; j--)
                    ary[i][j] = ary[i][j - 1];
                // 세로 ^
                for (; i > 1 + idx; i--)
                    ary[i][j] = ary[i - 1][j];
                ary[i][j] = temp;
            }
        }
    }
    static void view() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++)
                System.out.print(ary[i][j] + " ");
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) throws IOException {
        init();
        solve();
        view();
    }
}

[ C++ / BFS ]

#ifdef _DEBUG
#include "bits_stdc++.h"
#else
#include "bits/stdc++.h"
#endif
#pragma warning(disable:4996)
using namespace std;

int h, w, r;
int height, weight;
int yY[4] = { 0,1,0,-1 };
int xX[4] = { -1,0,1,0 };
bool direction;
#define MAX 301
int cube[MAX][MAX];
bool visit[MAX][MAX];
typedef struct data {
    int y;
    int x;
}Data;
bool check(int y, int x) {
    if (y<0 || x<0 || y>height - 1 || x>weight - 1 || visit[y][x])
        return false;
    else
        return true;
}
void view() {
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++)
            printf("%d ", cube[i][j]);
        cout << endl;
    }
    cout << endl;
}
void roll() {
    Data start = { 0, w-1 };
    height = h, weight = w;
    int temp = 0, temp2 = 0;
    while (1) {
        int dir = 0;
        if (!visit[start.y][start.x]) {
            int y = start.y, x = start.x;
            temp = cube[y][x];
            while (1) {
                int ny = y + yY[dir], nx = x+ xX[dir];
                if (check(ny, nx)) {
                    visit[ny][nx] = true;
                    swap(temp, cube[ny][nx]);
                    y = ny, x = nx;
                    if (ny == start.y && nx == start.x)
                        break;
                }
                else 
                    dir = dir + 1 > 3 ? 0 : dir + 1;
            }
        }
        else
            break;
        start.y++, start.x--, height--, weight--;
    }
}
int main() {
#ifdef _CONSOLE
    freopen("input.txt", "r", stdin);
#endif
    scanf("%d %d %d", &h, &w, &r);
    direction = h % 2 == 0 ? true : false;
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            scanf("%d", &cube[i][j]);
    while (r-- > 0) {
        memset(visit, 0, sizeof visit);
        roll();
    }
    view();
}