[코드트리] 삼성 SW역량테스트 기출 - 메이즈 러너 (C++)

winluck·2024년 9월 21일
C++삼성삼성코테코딩테스트
0

Algorithm

목록 보기
8/8

삼성 코딩테스트 2023년 상반기 오후 1번이었다.

24년 인턴십 지원으로 기회를 얻었던 서천연수원 코딩테스트를 포함하여 삼성 코딩테스트는 느낀 점이 3개 정도 있다.

  • 문제 똑바로 읽고 요구사항을 명확하게 정리한 뒤에 시작해도 늦지 않다. (요구사항을 하나라도 흘리고 시작하면 최소 1시간 뻘짓을 하게 된다.)
  • 기능별로 함수를 분리하여 런타임 에러가 났을 때 어디가 문제인지 빠르게 확인할 수 있어야 한다. (현장에서 진짜 피봤던 기억이..)
  • 배열 90도 돌리기, 달팽이 모양처럼 돌리기 등 2차원 배열의 회전이 정말 자주 나온다. 이런 테크닉을 알아두면 좋을 것 같다.

문제 설명

문제에서 알 수 있는 핵심 정보는 다음과 같다.

  • 좌상단은 (1,1) -> 인덱스 설정 주의
  • 참가자는 벽이 없으면서 항상 출구와 가까운 방향으로 움직여야 하며, 이 때 상하 이동이 우선권을 갖는다.
  • 참가자는 움직일 수 없다면 가만히 있으며, 한 좌표에 2명 이상의 참가자가 존재할 수 있다.
  • 움직임을 마친 후 1명 이상의 참가자와 출구를 포함한 가장 작은 최적의 정사각형을 찾는다.
  • 정사각형 내부 벽, 사람, 출구를 90도 시계방향으로 회전한다.

해결 과정

main

문제의 핵심 동작은 크게 3가지로 나눌 수 있다.

  • 참가자의 움직임 (move)
  • 조건에 맞는 최적의 정사각형을 추적 (rotateFunc)
  • 정사각형 내부 개체(벽, 사람, 출구) 시계 방향 90도로 회전 (rotate)

출구 좌표를 {ex, ey}로 잡고 main에 주요 함수를 세팅한다.

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

    cin >> n >> m >> t;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> arr[i][j];
        }
    }
    for(int i=1; i<=m; i++){
        int a, b;
        cin >> a >> b;
        v.push_back(make_pair(a-1, b-1));
    }
    cin >> ex >> ey;
    arr[--ex][--ey] = -1;

    for(int i=1; i<=t; i++){
        move(); // 참가자의 움직임
        rotateFunc(); // 정사각형 결정 및 회전
    }
    cout << answer << '\n';
    cout << ex+1 << " " << ey+1;
    return 0;
}

move

참가자들의 좌표를 담아둔 vector를 순회하며 현재 좌표에서 벽이 아니면서 출구와 가까운 방향으로 이동할 수 있는지 검증한다. 이후 이동이 가능하다면 상하 이동을 우선으로 하여 움직이고, 이를 answer로 카운트한다.

이 때 참가자들 중 출구에 서 있는 친구는 erase로 제거한다.
이 때 순방향으로 erase 실행 시 인덱스를 당겨줘야 하기 때문에 편의를 위해 역방향으로 처리한다.

// 참가자들이 이동
void move(){
    for(int i=v.size()-1; i>=0; i--){
        if(v[i].first == ex && v[i].second == ey) {
            v.erase(v.begin() + i);
            continue;
        }
        pair<int, int> now = v[i];
        int nowdis = abs(ex - now.first) + abs(ey - now.second); // 현재 출구까지의 거리

        for(int a=0; a<4; a++){
            int nx = now.first + dx[a];
            int ny = now.second + dy[a];

            if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue; // 이탈
            if(arr[nx][ny] > 0) continue; // 벽
            int nextdis = abs(ex - nx) + abs(ey - ny); // 다음 좌표 기준 출구까지의 거리
            if(nowdis > nextdis){ // 이동 가능
                answer++;
                v[i] = make_pair(nx, ny);
                break;
            }
        }
    }
    if(!v.empty())
        sort(v.begin(), v.end(), cmp2); // 최적의 정사각형 추적을 위한 정렬
}

rotateFunc

이제 조건에 맞는 최적의 정사각형을 찾아 해당 영역에서 시계 방향으로 90도 회전을 실행하면 된다.
정사각형의 핵심 정보는 시작점(왼쪽 위)의 좌표와 변의 길이이다.
n = 10이기에 완전탐색으로 해도 문제가 없다.

"최적의 정사각형"이란, 변의 길이가 제일 작고, 행과 열의 값이 가장 작은 정사각형이다.

// 사각형 크기 오름차순, 행/열 번호 오름차순 정렬
bool cmp(pair<int, pair<int, int> > p1, pair<int, pair<int, int> > p2){
    if(p1.first == p2.first){
        if(p1.second.first == p2.second.first){
            return p1.second.second < p2.second.second;
        }
        return p1.second.first < p2.second.first;
    }
    return p1.first < p2.first;
}

k를 통해 변의 길이 2부터(1이면 조건을 절대 만족할 수 없다.) 2중 for문을 통해 특정 시작점에서 해당 정사각형이 유효한지 검증한다.
이를 위해 내부 2중 for문을 추가하여 출구와 참가자를 포함하는 것이 확인되면 바로 회전에 돌입한다.

// 회전시킬 영역을 결정
void rotateFunc(){
    vector<pair<int, pair<int, int> > > info;
    for(int k=2; k<=n; k++){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(i+k > n || j+k > n) continue;
                bool exit = false; // 출구 존재 여부
                bool user = false; // 참가자 존재 여부
                for(int a=i; a<i+k; a++){
                    for(int b=j; b<j+k; b++){
                        int sx = 0;
                        int sy = 0;
                        if(a < 0 || b < 0 || a >= n || b >= n) continue;
                        if(a == ex && b == ey) exit = true;

                        for(auto &it: v){
                            if(it.first >= i && it.first < i+k && it.second >= j && it.second < j+k){
                                if(it.first == ex && it.second == ey) continue;
                                sx = it.first;
                                sy = it.second;
                                user = true;
                                break;
                            }
                        }
                        if(exit == true && user == true){ // 둘 다 존재함 -> 현재 k, i, j 등록
                            rotate(i, j, k);
                            return;
                        }
                    }
                }
            }
        }
    }
}

rotate

실제 회전은 다음과 같은 순서로 진행된다.

  1. 정해진 정사각형 내부에 들어있는 참가자를 추적하고, 이를 기존 참가자 리스트 v에서 제거한다.
  2. 이후 임시 참가자 리스트에 저장한다.
  3. 2차원 배열을 시계방향으로 90도 회전한다. 이 때 출구가 회전되었을 경우 이를 반영해준다.
  4. 임시 참가자 리스트를 순회하며 참가자의 위치도 회전한고 다시 기존 참가자 리스트 v에 저장한다.
  5. 요구사항에 따라 회전 후 정사각형 내부 벽의 내구도를 1씩 낮춰준다.
// 특정 영역 회전
void rotate(int r, int c, int size){
    int tmp[11][11]; // 임시 arr
    vector<pair<int, int> > tmpvec; // 임시 v

    // 영역에 들어있는 사람 추적
    for(int i=v.size()-1; i>=0; i--){
        if(v[i].first >= r && v[i].first < r+size && v[i].second >= c && v[i].second < c+size){
            if(!(v[i].first == ex && v[i].second == ey)){
                tmpvec.push_back(v[i]);
            }
            v.erase(v.begin() + i);
        }
    }

    for(int i=r; i<r+size; i++){
        for(int j=c; j<c+size; j++){
            tmp[i][j] = arr[i][j];
        }
    }

    // 시계방향 90도 회전
    for(int i=r; i<r+size; i++){
        for(int j=c; j<c+size; j++){
            tmp[j - c + r][r + c + size - 1 - i] = arr[i][j];
        }
    }

    for(int i=r; i<r+size; i++){
        for(int j=c; j<c+size; j++){
            arr[i][j] = tmp[i][j];
            if(arr[i][j] == -1){ // 출구 조정
                ex = i;
                ey = j;
            }
        }
    }

    // 사람 좌표 갱신
    for(auto& it: tmpvec){
        int x = it.first;
        int y = it.second;
        int nx = y - c + r; // 회전된 x 좌표
        int ny = r + c + size - 1 - x; // 회전된 y 좌표
        v.push_back(make_pair(nx, ny));
    }
    sort(v.begin(), v.end(), cmp2);

    // 회전 후 내구도 감소
    for(int i=r; i<r+size; i++){
        for(int j=c; j<c+size; j++){
            if(arr[i][j] > 0) arr[i][j]--; 
        }
    }
}

소스 코드

개인적으로 초기에 방향을 잘못 잡아 트러블 슈팅에 꽤나 고생했던 문제였다.

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
int n, m, t, ex, ey;
vector<pair<int, int> > v;
int arr[11][11]; // 좌표별 벽 정보
int answer = 0;
map<int, pair<int, int> > dict;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

// 좌표 오름차순 정렬
bool cmp(pair<int, int> p1, pair<int, int> p2){
    if(p1.second == p2.second){
        return p1.second < p2.second;
    }
    return p1.first < p2.first;
}

// 디버깅용
void print(){
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cout << arr[i][j] << " ";
        }
        cout << '\n';
    }
    cout << '\n';
}

// 참가자들이 이동
void move(){
    for(int i=v.size()-1; i>=0; i--){
        if(v[i].first == ex && v[i].second == ey) {
            v.erase(v.begin() + i);
            continue;
        }
        pair<int, int> now = v[i];
        int nowdis = abs(ex - now.first) + abs(ey - now.second); // 현재 출구까지의 거리

        for(int a=0; a<4; a++){
            int nx = now.first + dx[a];
            int ny = now.second + dy[a];

            if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue; // 이탈
            if(arr[nx][ny] > 0) {
                continue; // 벽
            }
            int nextdis = abs(ex - nx) + abs(ey - ny); // 다음 좌표 기준 출구까지의 거리
            if(nowdis > nextdis){ // 이동 가능
                answer++;
                v[i] = make_pair(nx, ny);
                break;
            }
        }
    }
    if(!v.empty())
        sort(v.begin(), v.end(), cmp);
}

// 특정 영역 회전
void rotate(int r, int c, int size){
    int tmp[11][11]; // 임시 arr
    vector<pair<int, int> > tmpvec; // 임시 v

    // 영역에 들어있는 사람 추적
    for(int i=v.size()-1; i>=0; i--){
        if(v[i].first >= r && v[i].first < r+size && v[i].second >= c && v[i].second < c+size){
            if(!(v[i].first == ex && v[i].second == ey)){
                tmpvec.push_back(v[i]);
            }
            v.erase(v.begin() + i);
        }
    }

    for(int i=r; i<r+size; i++){
        for(int j=c; j<c+size; j++){
            tmp[i][j] = arr[i][j];
        }
    }

    // 시계방향 90도 회전
    for(int i=r; i<r+size; i++){
        for(int j=c; j<c+size; j++){
            tmp[j - c + r][r + c + size - 1 - i] = arr[i][j];
        }
    }

    for(int i=r; i<r+size; i++){
        for(int j=c; j<c+size; j++){
            arr[i][j] = tmp[i][j];
            if(arr[i][j] == -1){ // 출구 조정
                ex = i;
                ey = j;
            }
        }
    }

    // 사람 좌표 갱신
    for(auto& it: tmpvec){
        int x = it.first;
        int y = it.second;
        int nx = y - c + r; // 회전된 x 좌표
        int ny = r + c + size - 1 - x; // 회전된 y 좌표
        v.push_back(make_pair(nx, ny));
    }
    sort(v.begin(), v.end(), cmp);

    // 회전 후 내구도 감소
    for(int i=r; i<r+size; i++){
        for(int j=c; j<c+size; j++){
            if(arr[i][j] > 0) arr[i][j]--; 
        }
    }
}

// 회전시킬 영역을 결정
void rotateFunc(){
    vector<pair<int, pair<int, int> > > info;
    for(int k=2; k<=n; k++){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(i+k > n || j+k > n) continue;
                bool exit = false; // 출구 존재 여부
                bool user = false; // 참가자 존재 여부
                for(int a=i; a<i+k; a++){
                    for(int b=j; b<j+k; b++){
                        int sx = 0;
                        int sy = 0;
                        if(a < 0 || b < 0 || a >= n || b >= n) continue;
                        if(a == ex && b == ey) exit = true;

                        for(auto &it: v){
                            if(it.first >= i && it.first < i+k && it.second >= j && it.second < j+k){
                                if(it.first == ex && it.second == ey) continue;
                                sx = it.first;
                                sy = it.second;
                                user = true;
                                break;
                            }
                        }
                        if(exit == true && user == true){ // 둘 다 존재함 -> 현재 k, i, j 등록
                            rotate(i, j, k);
                            return;
                        }
                    }
                }
            }
        }
    }
}

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

    cin >> n >> m >> t;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> arr[i][j];
        }
    }
    for(int i=1; i<=m; i++){
        int a, b;
        cin >> a >> b;
        v.push_back(make_pair(a-1, b-1));
    }
    cin >> ex >> ey;
    arr[--ex][--ey] = -1;

    for(int i=1; i<=t; i++){
        move();
        rotateFunc();
    }
    cout << answer << '\n';
    cout << ex+1 << " " << ey+1;
    return 0;
}

교훈

  • 코드 먼저 앞서나가지 말고 요구사항에 맞는 최적의 구조는 무엇인지 일정 시간 고민하고 시작하도록 하자.
profile
winluck
Discover Tomorrow
이전 포스트

[프로그래머스 Lv.2] (C++) 순위 검색

0개의 댓글