[삼성SW] 고대 문명 유적 탐사

문제 : 코드트리

풀이 방식

아래의 3개가 한 턴에 이루어지며, 총 K개의 턴을 반복해야 한다.
1. (1,1)~(1,3), ... , (3,1)~(3,3)까지 각각 3개의 각도로 회전해보며 조건에 맞는 적합한 회전 조건을 구한다.
2. 조건에 맞게 회전한다.
3. 유물이 찾아지지 않을 때까지 유물을 찾고, 리필하고를 반복한다.

배운 점

1.회전시 좌표 구하기

회전 후 (i,j)의 좌표에 들어갈 값을 기존 배열의 (x,y)로 가정한 후, 방정식을 풀어 (x,y)값을 구하는 식으로 계산하면 편하다.
그리고, copy[i][j]에 board[x][y] 값을 옮길 때, board에서 회전시킬 부분만 따로 복사해서 사용하는 것이 훨씬 편하다.
이문제에선 회전할 3x3 배열만 따로 복사해두었다.

2. 2차원 벡터는 fill보다 2중 for문으로 채우자

2차원 벡터는 벡터 내부에 벡터들이 존재하기 때문에, 단일 시퀀스를 대상으로 동작하는 fill을 사용하려면 결국 for문을 돌아야한다. 그냥 2중 for문을 사용하자

3. 우선순위 큐의 비교연산자(cmp)를 커스텀 할 때는, 무조건 struct로 만들어주어야 한다.

4. 큐와 벡터는 clear()함수가 없다.

while(!큐.empty() {큐.pop();} 으로 처리하자.

5. 다른 함수로 큐나 벡터 등을 보내고, 값을 넣고싶다면 함수를 선언할 때 파라미터에 주소선언을 하자

void dfs2(int index, int y, int x, vector<vector<bool>>& visited, vector<pair<int, int>>& pv) 
{
}

이런식으로 파라미터에 "타입& 변수명" 으로 받으면 받은 벡터나 큐에 값을 더하거나 뺀 후 반환해도 변화가 반영되어있다.

6. nextY, nextX의 유효성을 체크할 때 순서주의

 if(nextY<0||nextY>4||nextX<0||nextX>4||visited[nextY][nextX]||copy[nextY][nextX]!=index)continue;

이렇게 범위체크를 먼저 안해주면, visited 체크 때 outOfBounds 가 필연적으로 뜬다.

7. 배열에서 나처럼 [y][x]를 사용한다면, y=행, x=열임을 잊지말자

종이 제일위에 적어두고 시작하는게 마음편하다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <utility>
using namespace std;
int moveY[4]={-1,1,0,0}, moveX[4]={0,0,-1,1}, K,M;
vector<vector<bool>> visited(5,vector<bool>(5, false));
vector<int> refill;
int refillIndex=0;
vector<vector<int>> board(5,vector<int>(5));

struct Rotate{
    int y,x, relic, angle; //중심 행, 열, 유물수, 회전각도
};
struct Compare{  //Rotate구조체 비교연산자
    bool operator()(const Rotate& a, const Rotate& b){
        if(a.relic!=b.relic) return a.relic<b.relic;
        else if(a.angle!=b.angle) return a.angle>b.angle;
        else if(a.x!=b.x) return a.x>b.x;
        else return a.y>b.y;
    }
};
struct Cmp{ //유물 리필 비교연산자
    bool operator()(pair<int, int>& a, pair<int, int>& b){
        if(a.second!=b.second) return a.second>b.second;
        else return a.first<b.first;
    }
};

Rotate makeRotate(int y, int x, int relic, int angle){
    Rotate rotate;
    rotate.y=y;
    rotate.x=x;
    rotate.relic=relic;
    rotate.angle=angle;
    return rotate;
}

Rotate makeNullRotate(){
    Rotate rotate;
    rotate.y=-1;
    return rotate;
}

int dfs(vector<vector<int>> copy, int y, int x, int index){
    int cnt=0;
    if(copy[y][x]==index) {
        cnt++;
        visited[y][x]=true;
    }
    for(int i=0;i<4;i++){
        int nextY=y+moveY[i];
        int nextX=x+moveX[i];
        if(nextY<0||nextY>4||nextX<0||nextX>4||visited[nextY][nextX]||copy[nextY][nextX]!=index)continue;
        visited[nextY][nextX]=true;
        cnt+=dfs(copy, nextY, nextX,index);
    }
    return cnt;
}

Rotate findRotate(int y, int x, int angle){ //보드 돌려서 유물갯수 찾고, Rotate만들기
    vector<vector<int>> copy(5,vector<int>(5));
    //보드 복사
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++) copy[i][j]=board[i][j];
    }
    // 3x3 배열을 따로 저장
    int subBoard[3][3];
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            subBoard[i][j] = board[y-1+i][x-1+j];
        }
    }
    // 회전된 3x3 배열을 copy로 복사
    if (angle == 1) {
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                copy[y-1+i][x-1+j] = subBoard[2-j][i]; // 시계방향 90도 회전
            }
        }
    } else if (angle == 2) {
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                copy[y-1+i][x-1+j] = subBoard[2-i][2-j]; // 180도 회전
            }
        }
    } else if (angle == 3) {
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                copy[y-1+i][x-1+j] = subBoard[j][2-i]; // 시계방향 270도 회전
            }
        }
    }
    //현재 배열의 유물 수 찾기
    int relic=0;
    //fill(visited[0].begin(), visited[4].end(), false); //방문배열 초기화 다차원벡터는 fill하면안됨
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++) visited[i][j]=false;
    }
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            if(visited[i][j]) continue;
            int nowRelic=dfs(copy,i,j,copy[i][j]);
            if(nowRelic>=3) relic+=nowRelic;
        }
    }
    Rotate rotate=makeRotate(y,x,relic,angle);
    return rotate;
}

Rotate findRotate(){ //턴 시작 직후 회전해야 하는 각도와 중심점 찾기
    priority_queue<Rotate, vector<Rotate>, Compare> pq;
    for(int i=1;i<=3;i++){ //행 (3x3배열 회전시켜야 하므로 중심점은 1,1~3,3까지 총 9개)
        for(int j=1;j<=3;j++){ //열
            for(int k=1;k<=3;k++){ //회전각도
                pq.push(findRotate(i,j,k));
            }
        }
    }
    if(pq.top().relic==0) return makeNullRotate();
    return pq.top();
}

void doRotate(int y, int x, int angle){
    int subBoard[3][3];
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            subBoard[i][j] = board[y-1+i][x-1+j];
        }
    }
    // 회전된 3x3 배열을 copy로 복사
    if (angle == 1) {
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                board[y-1+i][x-1+j] = subBoard[2-j][i]; // 시계방향 90도 회전
            }
        }
    } else if (angle == 2) {
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                board[y-1+i][x-1+j] = subBoard[2-i][2-j]; // 180도 회전
            }
        }
    } else if (angle == 3) {
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                board[y-1+i][x-1+j] = subBoard[j][2-i]; // 시계방향 270도 회전
            }
        }
    }
}

void dfs2(int index, int y, int x, vector<vector<bool>>& visited, vector<pair<int, int>>& pv) {
    // 방문 처리
    visited[y][x] = true;
    pv.push_back({y, x});  // 좌표 저장
    // 상하좌우로 이동
    for (int i = 0; i < 4; i++) {
        int nextY = y + moveY[i];
        int nextX = x + moveX[i];
        // 경계 체크와 방문 체크
        if (nextY < 0 || nextY > 4 || nextX < 0 || nextX > 4 || visited[nextY][nextX] || board[nextY][nextX] != index)
            continue;
        // 재귀적으로 탐색
        dfs2(index, nextY, nextX, visited, pv);
    }
}

void refillRelic(priority_queue<pair<int, int>, vector<pair<int, int>>, Cmp>& pq){
    while(!pq.empty()){
        int y=pq.top().first;
        int x=pq.top().second;
        pq.pop();
        board[y][x]=refill[refillIndex];
        refillIndex++;
    }
}

int relay(){ //보드가 회전한 상태에서, 유물들을 찾고 다시 리필하고 찾고 반복
    int result=0; //최종적으로 얻은 유물 수
    priority_queue<pair<int, int>, vector<pair<int, int>>, Cmp> pq; //유물을 찾은 좌표 큐, 우선순위대로 리필하면됨
    vector<vector<bool>> visited(5,vector<bool>(5, false)); 
    while(1){ //유물 찾고 리필하기
        vector<pair<int, int>> pv;
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++) visited[i][j]=false;
        }
        //pq.clear(); 우선순위큐는 clear없음
        while (!pq.empty()) pq.pop();
        //현재상황에서 유물 전부 찾고 좌표들 받기
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++) {
                if(visited[i][j]) continue;
                pv.clear();
                dfs2(board[i][j],i,j,visited, pv);
                if(pv.size()>=3){
                    //cout<<i<<", "<<j<<"에서 "<<pv.size()<<" ";
                    for(int i=0;i<pv.size();i++) pq.push(pv[i]);
                }
            }
        }
        int relicCnt=pq.size(); //찾은 유물의 수
        result+=relicCnt; //유물 개수 결과에 추가
        if(relicCnt==0) return result;
        refillRelic(pq);
    }
    return -1;
}

int main() {
    cin>>K>>M;
    refill.resize(M+1);
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++) cin>>board[i][j];
    }
    for(int i=0;i<M;i++) cin>>refill[i];
    while(K--){
        Rotate rotate=findRotate();
        if(rotate.y==-1) break; //유물을 찾을수없음
        doRotate(rotate.y, rotate.x, rotate.angle); //찾은 좌표와 각도로 회전
        int turnResult=relay();
        cout<<turnResult<<" ";
    }
    return 0;
}