[코드트리 챌린지] 1주차 Simulation - 격자 안에서 여러 객체를 이동/ 숫자의 순차적 이동

https://www.codetree.ai/missions/2/problems/sequential-movement-of-numbers/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드:

#include <bits/stdc++.h>
using namespace std;

int n, m;
int arr[25][25];

int dx[8] = { -1,-1,0,1,1,1,0,-1 }; // 위 방향부터 시계방향
int dy[8] = { 0,1,1,1,0,-1,-1,-1 };

bool InRange(int nx, int ny) {
    return (0 <= nx && nx < n && 0 <= ny && ny < n);
}

void Move(int i, int j) {
    int nxt_i = i;
    int nxt_j = j;
    int maxVal = 0;

    // 8방향에 대해 가장 큰 값을 찾음
    for (int dirNum = 0; dirNum < 8; dirNum++) {
        int nx = i + dx[dirNum];
        int ny = j + dy[dirNum];

        if (InRange(nx, ny) && arr[nx][ny] > maxVal) {
            nxt_i = nx;
            nxt_j = ny;
            maxVal = arr[nxt_i][nxt_j];
        }
    }
    
    // 가장 큰 값과 위치 교환
    int tmp = arr[i][j];
    arr[i][j] = arr[nxt_i][nxt_j];
    arr[nxt_i][nxt_j] = tmp;

    return;
}

void Find(int k) {
    // 1부터 차례로 숫자를 찾고
    // Move() 함수 호출
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j] == k) {
                Move(i, j);
                return;
            }
        }
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }

    // m턴 동안
    while (m--) {
        // 1부터 차례로 숫자를 찾음
        for (int k = 1; k <= n * n; k++) {
            Find(k);
        }

    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << arr[i][j] << " ";
        }
        cout << "\n";
    }
    
}

 

n,m을 입력받고 배열을 채웁니다.

while문으로 m턴 동안 1~n*n 까지의 숫자를 차례로 Find()함수에 매개변수로 넣습니다.

2차원 배열을 모두 탐색하여 숫자 k(1~n*n)를 찾고 그 위치에 대해 Move()함수를 호출합니다.

Move()함수에서 8방향에 대해 가장 큰 값을 탐색하고 위치를 서로 교환합니다.