[삼성 SW 역량평가] 꼬리잡기놀이(C++)

풀이 소요시간 : 약 2시간

레일을 저장하는 방식

처음에 어떤 방식으로 레일을 저장해야하나 고민했다. 레일을 전체 회전시키기도 해야하기 때문에 Map 으로만 감당하는 것이 불가능해보였다. 따라서 Vector를 선언하여 레일의 격자정보를 저장했다.

레일을 회전시키는 방법

레일을 양방향으로 회전시킬 수 있어야한다. 이것을 어떻게 구현해야하나 고민했다. 나는 비교적 노가다 방식으로 정답을 통과시켰지만, 리팩토링 과정에서 더 나은 방법이 있었음을 알게되었다. 사실 Rotation 함수는 한 방향으로만 구현하면 된다. 대신 레일을 관리하는 Vector의 구성요소를 정반대로 바꿔버리면 된다.

reverse(Team[L].begin(), Team[L].begin() + Person[L]);
reverse(Team[L].begin() + Person[L], Team[L].end());

이런 식의 순서 변화는 애초에 배열의 시작 좌표가 달라진다. 단순한 방향 뒤집기로 해결될 수 없다.

뒤집기를 완료한 후 Map을 따로 관리해준다.
레일 내부의 인구 수를 저장하는 Person 을 활용하여 Map을 동기화시킬 수 있다.

for (int i = 0; i < Team[n].size(); i++)
{
            if(i == 0) 
                Map[Team[n][i].x][Team[n][i].y] = 1;
            else if(i > 0 && i < Person[n] - 1) 
                Map[Team[n][i].x][Team[n][i].y] = 2;
            else if(i == Person[n] - 1) 
                Map[Team[n][i].x][Team[n][i].y] = 3;
            else 
                Map[Team[n][i].x][Team[n][i].y] = 4;
}

전체 코드

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

int N, M, K;

int Map[21][21];
int Lab[21][21];
int Visit[21][21];

int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

struct Block {
    int x;
    int y;
};

vector<Block> Team[6];
int Person[6];
int Point[6];

void Input() {
    cin >> N >> M >> K;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            cin >> Map[i][j];
}

//팀 구역 탐색 : 머리 -> 꼬리 방향
void Label(int x, int y, int L) {
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 1 || ny < 1 || nx > N || ny > N) continue;
        if (Visit[nx][ny] == 1 || Map[nx][ny] == 0) continue;

        //가장 처음 탐색할 때 무조건 2가 있는 방향으로 DFS 진행한다.
        //Vector.size() 를 활용
        //자연스럽게 머리 -> 꼬리 방향으로 Vector에 삽입된다.
        if(Team[L].size() == 1 && Map[nx][ny] != 2) continue;

        //꼬리가 나오는 곳까지 탐색하면 현재까지의 Vector.size()가 인구
        if(Map[nx][ny] == 3) Person[L] = Team[L].size() + 1;

        Visit[nx][ny] = 1;
        Team[L].push_back({ nx, ny });
        Label(nx, ny, L);
    }
}

//팀 생성
void Make_Team() {
    int L = 1;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
        {
            if (Map[i][j] == 1 && Visit[i][j] == 0)
            {
                Visit[i][j] = 1;
                Team[L].push_back({ i, j });
                Label(i, j, L);
                L++;
            }
        }

    for (int i = 1; i < L; i++)
    {
        for (int j = 0; j < Team[i].size(); j++)
        {
            Lab[Team[i][j].x][Team[i][j].y] = i;
        }
    }
    memset(Visit, 0, sizeof(Visit));
}

//팀 회전
void Rotation() {
    for (int n = 1; n <= M; n++)
    {
        int sz = Team[n].size();
        int tx = Team[n][sz - 1].x;
        int ty = Team[n][sz - 1].y;

        for (int i = sz - 1; i >= 1; i--)
        {
            Team[n][i].x = Team[n][i - 1].x;
            Team[n][i].y = Team[n][i - 1].y;
        }
        Team[n][0].x = tx;
        Team[n][0].y = ty;

        //Map 동기화
        for (int i = 0; i < Team[n].size(); i++)
        {
            if(i == 0) 
                Map[Team[n][i].x][Team[n][i].y] = 1;
            else if(i > 0 && i < Person[n] - 1) 
                Map[Team[n][i].x][Team[n][i].y] = 2;
            else if(i == Person[n] - 1) 
                Map[Team[n][i].x][Team[n][i].y] = 3;
            else 
                Map[Team[n][i].x][Team[n][i].y] = 4;
        }

    }
}


void State(int L, int x, int y) {

    for (int i = 0; i < Team[L].size(); i++)
    {
        if (Team[L][i].x == x && Team[L][i].y == y)
        {
            Point[L] += (i + 1) * (i + 1);
        }
    }

    reverse(Team[L].begin(), Team[L].begin() + Person[L]);
    reverse(Team[L].begin() + Person[L], Team[L].end());
    //좌표 역순 
    for(int i = 0; i < Team[L].size(); i++)
    {
        if(i == 0) 
            Map[Team[L][i].x][Team[L][i].y] = 1;
        else if(i > 0 && i < Person[L] - 1) 
            Map[Team[L][i].x][Team[L][i].y] = 2;
        else if(i == Person[L] - 1) 
            Map[Team[L][i].x][Team[L][i].y] = 3;
        else 
            Map[Team[L][i].x][Team[L][i].y] = 4;
    }
}

void Ball(int Round) {

    int R = Round % (4 * N);
    if (R >= 1 && R <= N)
    {
        for (int i = 1; i <= N; i++)
        {
            if (Map[R][i] == 0 || Map[R][i] == 4) continue;
            State(Lab[R][i], R, i);
            break;
        }
    }
    
    if (R > N && R <= 2 * N)
    {
        for (int i = N; i >= 1; i--)
        {
            if (Map[i][R - N] == 0 || Map[i][R - N] == 4) continue;
            
            State(Lab[i][R - N], i, R - N);
            break;
        }
    }
    
    if (R > 2 * N && R <= 3 * N)
    {
        for (int i = N; i >= 1; i--)
        {
            if (Map[3 * N - R + 1][i] == 0 || Map[3 * N - R + 1][i] == 4) continue;
            State(Lab[3 * N - R + 1][i], 3 * N - R + 1, i);
            break;
        }
    }
    
    if(R > 3 * N)
    {
        for (int i = 1; i <= N; i++)
        {
            if (Map[i][4 * N - R + 1] == 0 || Map[i][4 * N - R + 1] == 4) continue;
            State(Lab[i][4 * N - R + 1], i, 4 * N - R + 1);
            break;
        }
    }
    
    if(R == 0)
    {
        for (int i = 1; i <= N; i++)
        {
            if (Map[i][1] == 0 || Map[i][1] == 4) continue;
            State(Lab[i][1], i, 1);
            break;
        }
    }
}

int Make_Ans() {
    int sum = 0;
    for (int i = 1; i <= M; i++)
    {
        sum += Point[i];
    }
    return sum;
}

int main() {
    Input();
    Make_Team();

    int Time = 1;
    while (Time <= K)
    {
        Rotation();
        Ball(Time);
        Time++;
    }
    cout << Make_Ans() << endl;
}