이 문제의 핵심은 상어가 먹을 수 있는 위치를 찾는것과

거리가 가까운 물고기가 많다면 가장 위에 있는 물고기, 그 중 가장 왼쪽에 있는 물고기를 고르는 것이다.

처음에 이 문제를 해결하기 위해 접근배열 dx, dy를 상,좌,하,우 순으로 방문하였는데 이 점이 문제가 되었다. 이렇게 했을때 만약 현재 위치에서 상, 좌 ,하 ,우에 모두 물고기가 존재한다면 문제에 어긋나지 않겠지만 우측 상단 물고기와 좌측 하단 물고기가 만날경우 우측 상단 물고기가 우선순위기에 잘못된 접근이 된다.

가장 위쪽, 가장 왼쪽 이라는 조건은 map을 기준으로 생각했을때 0,0에 가장 가까운 것으로 처음 발견된 물고기와 같은 거리에 있는 물고기들을 vector에 넣어 sort하거나 우선 순위 큐를 이용해 top에 있는 물고기를 고른다면 그 물고기는 당연히 가장 위쪽, 가장 왼쪽에 존재한 물고기 일 것이다.

이 것을 해결하고도 한가지 해결하지 못한 점이 있는데 현재 위치가 먹을 수 있는 물고기일때는 더이상 탐색을 진행하면 안된다. 왜냐하면 현재 물고기의 위치가 최종 위치가 될지는 아직 모르기 때문이다.

즉 if 현재 물고기를 먹을 수 있을때 과정을 진행하고 else로 구성해야 맞는 로직이다.

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

struct DATA {
    int x = 0;
    int y = 0;
    int ti = 0;
};
DATA BABY_SHARK;

int result = 0;
int eat = 0;
int map[21][21];

int n;

int BabySize = 2;
//상 좌 하 우
//가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
//상 좌 하 우
int dx[4] = { -1,0,0,1 };
int dy[4] = { 0,-1,1,0 };
bool check[21][21];

//아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다.예를 들어, 
//크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

//거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

//아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다.
//아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다.

void bfs(int x, int y) {

    //flag가 0이면 먹을 상어를 찾지 못한거


    //맨 처음에는 아기상어 위치를 지정해주고 나중에는 자동 업데이트 해야함
    int cur_x = x;
    int cur_y = y;

    //1. 자신이 먹을 수 있는 물고기의 위치를 찾음
    while (true) {

        memset(check, false, sizeof(check));
        check[cur_x][cur_y] = true;

        queue<DATA> q;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

        int dist = 0;
        q.push({ cur_x, cur_y,0 });

        while (!q.empty()) {
            int x = q.front().x;
            int y = q.front().y;
            int ti = q.front().ti;
            //cout << x << " " << y << " " << ti << endl;;
            q.pop();

            if (map[x][y] < BabySize && map[x][y] > 0) {
                if (!dist) {
                    dist = ti;
                    pq.push({ x,y });
                }
                else if (dist == ti) {
                    pq.push({ x,y });
                }
            }
            else {
                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    //범위안, 방문한적 x, 갈 수 있는 위치
                    if (0 <= nx && nx < n && 0 <= ny && ny < n && !check[nx][ny] && BabySize >= map[nx][ny]) {
                        check[nx][ny] = true;
                        q.push({ nx,ny, ti + 1 });
                    }
                }
            }
        }

        //만약 물고기를 찾을 수 없으면 return
        if (pq.empty()) return;

        //2. 그 물고기로 이동하면서 시간 업데이트
        cur_x = pq.top().first;
        cur_y = pq.top().second;
        result += dist;

        map[cur_x][cur_y] = 0;
        eat += 1;
        if (BabySize == eat) {
            BabySize += 1;
            eat = 0;
        }

    }

    return;

}

int main() {
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; i++) {

        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            //9의 위치가 아기상어 위치
            if (map[i][j] == 9) {
                BABY_SHARK.x = i;
                BABY_SHARK.y = j;
                map[i][j] = 0;
            }
        }
    }

    bfs(BABY_SHARK.x, BABY_SHARK.y);

    cout << result;

    return 0;
}

풀이는 제대로 됐지만 한가지를 간과했다. 기존 코드에서는 만약 검사 중 다른 값이 나올경우 현재 count를 1로 설정하고 다시 탐색을 이어갔다.

만약 다른 값이 나오지 않고 그대로 같은 값이 나온다면 정답에는 문제가 없지만 어느정도 같은 값이 나오다 다른 값이 나올경우 현재의 경우를 result에 업데이트 하는건 한 행, 열이 끝난 이후에만 진행했기에 중간 결과가 업데이트 되지 않았다. 이 부분을 추가하니 성공됐다.

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

int n;
int result = 0;
char map[50][50];

char b;
char a;

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

//가장 긴 연속 행열 찾기
void _find() {

    //0~n-1번째 열 검사
    for (int i = 0; i < n; i++) {
        int count = 1;
        b = map[i][0];
        for (int j = 1; j < n; j++) {
            //만약 b랑 현재가 다를경우
            if (b != map[i][j]) {
                result = max(result, count);
                char q = map[i][j];
                b = map[i][j];
                count = 1;
            }
            else {
                count++;
            }
        }
        result = max(result, count);
    }

    //0~n-1번째 행 검사
    for (int i = 0; i < n; i++) {
        int count = 1;
        b = map[0][i];
        for (int j = 1; j < n; j++) {
            //만약 b랑 현재가 다를경우
            if (b != map[j][i]) {
                result = max(result, count);
                char q = map[i][j];
                b = map[j][i];
                count = 1;
            }
            else {
                count++;
            }
        }
        result = max(result, count);
    }

}

//1. 전환
void trans(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;

        //바꾸고자 하는 곳 값 임시 저장
        a = map[nx][ny];
        map[nx][ny] = map[x][y];
        map[x][y] = a;

        //2. 가장 긴 연속 행열찾기
        _find();

        //원래 상태로 변환
        a = map[nx][ny];
        map[nx][ny] = map[x][y];
        map[x][y] = a;

    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

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

    _find();

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            //답이 이미 n과 같으면 더이상 탐색해도 답은 더 커질수 없음
            if (result == n) {
                cout << result;
                return 0;
            }
            //1. 전환
            trans(i, j);
        }
    }

    cout << result;

    return 0;
}

alpha 가 0일때(정규화 한 것임) 255,2,121 * 0 + Dest(1-0) = Dest 원래 목적지의 색상을 그대로 출력하는 것 = 아무것도 출력안됨

alpha 가 1일때(255를 정규화) 255,2,121 * 1 + Dest(1-1) = 255,2,121 Source의 색상으 그래도 출력

alpha 가 0.5 일때 255,2,121 * 0.5 + Dest(1-0.5) = 122,1,60 + Dest(0.5) 목적지와 Source의 색상이 혼합되서 출력

Alpha Blending 할때 Render Enum Type을 잘 생각해야 한다.

이전에 비슷한 톱니바퀴 (1)문제를 풀었던 기억이 있어 쉽게 해결했다.

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int t, k, turn_gear, direction;

int gear[1001][8];
int c_gear[8];
bool check[1001];

void turn(int _gear, int _direction) {
    check[_gear] = true;
    //양 옆 검사하는건 index 2,6검사하면됨
    //서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다
    //톱니바퀴의 범위는 1~t까지
    if (_gear - 1 >= 1 && !check[_gear - 1] ) {
        if (gear[_gear][6] != gear[_gear - 1][2]) {
            //회전한 방향의 반대로 회전
            turn(_gear - 1, -(_direction));
        }
    }
    if (_gear + 1 <= t && !check[_gear + 1]) {
        if (gear[_gear][2] != gear[_gear + 1][6]) {
            //회전한 방향의 반대로 회전
            turn(_gear + 1, -(_direction));
        }
    }

    // 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.

    //시계 방향
    if (_direction == 1) {
        for (int i = 0; i <= 6; i++) {
            c_gear[i + 1] = gear[_gear][i];
        }
        c_gear[0] = gear[_gear][7];
    }

    //반시계 방향
    if (_direction == -1) {
        for (int i = 6; i >= 0; i--) {
            c_gear[i] = gear[_gear][i + 1];
        }
        c_gear[7] = gear[_gear][0];
    }

    //c_gear 복사는 모든 바퀴가 돌고

    for (int i = 0; i <= 7; i++) {
        gear[_gear][i] = c_gear[i];
    }

    return;
}

int main() {
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cout.tie(NULL);

    cin >> t;

    for (int i = 1; i <= t; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < s.size(); j++) {
            // i번째 톱니바퀴 j번째 값
            // 12시방향부터 시계방향 순서대로 주어진다.
            // 2 6
            gear[i][j] = s[j] - '0';
        }
    }

    cin >> k;
    for (int i = 0; i < k; i++) {
        memset(check, false, sizeof(check));
        cin >> turn_gear >> direction;
        turn(turn_gear, direction);
    }

    int count = 0;
    for (int i = 0; i <= t; i++) {
        if (gear[i][0] == 1) {
            count++;
        }
    }

    cout << count;

    return 0;

}

문제를 제대로 이해하지 못해 시간이 오래 걸렸다. 사각형의 넓이는 두 꼭짓점의 좌표를 각각빼주면 된다고 생각했지만 두 꼭짓점을 제외한 나머지 두개의 꼭짓점에도 똑같은 숫자가 있어야 사각형이 된다는 것을 뒤늦게 생각해 이에 맞게 변경하였지만 맨 뒤에 정사각형이라는 조건이 붙은걸 또 뒤늦게 확인해 문제 풀이에 애를 먹었다.

왼쪽 상단부터 숫자를 solve 함수에 넣어 같은 x축 , y축에 현재 숫자가 있다면 이를 vector에 집어넣고 나중에 x축 y축 백터에서 값을 하나씩 완전탐색해 맨 마지막 꼭짓점에 현재 숫자가 있는지를 검사하고 이에 대한 넓이를 구하고 최대값을 갱신하는 방식으로 해결했다.

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

int n, m;
int map[60][60];

int result = 1;


void solve(int cur, int x, int y) {
    //꼭짓점은 4개여야함

    //one은 i값은 min j값은 min
    //two는 i값은 min j값은 max
    //three i값은 max j값은 min
    //four  i값은 max j값은 max
    //42101 
    //22100
    //22101

    vector<int> x_list;
    vector<int> y_list;

    for (int i = x; i < n; i++) {
        if (map[i][y] == cur) x_list.push_back(i);
    }

    for (int j = y; j < m; j++) {
        if (map[x][j] == cur) y_list.push_back(j);
    }

    for (int i = 0; i < x_list.size(); i++) {
        for (int j = 0; j < y_list.size(); j++) {
            if (cur == 5) {
                //cout << x_list[i] << " " << y_list[j] << endl;
            }
            int cur_x = x_list[i];
            int cur_y = y_list[j];

            if ((cur_x - x) != (cur_y - y)) continue;

            if (map[cur_x][cur_y] == cur) {
                //cout << "정답" << cur_x << " " << cur_y << endl;
                //점은 4개여야 함
                if (x == cur_x || y == cur_y) continue;

                int k = ((cur_x - x) + 1) * ((cur_y - y) + 1);
                result = max(result, k);
            }

        }
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < s.size(); j++) {
            map[i][j] = s[j] - '0';
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            //아직 방문한 적이 없는 숫자면 진행
            solve(map[i][j],i,j);
        }
    }

    cout << result;

    return 0;
}

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string s;

string list[8] = { "dz=","c=","c-", "d-", "lj", "nj", "s=", "z=" };
int ct = 0;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int idx;

    cin >> s;

    for (int i = 0; i < 8; i++) {
        while (true) {
            idx = s.find(list[i]);
            if (idx == -1) {
                break;
            }        
            s.replace(idx, list[i].length(), "#");
        }
    }

    cout << s.length();

    return 0;
}

새로운 컴포넌트인 CTileMap을 생성하였다. CTileMap은 행, 열 갯수와 Tile안에 채우고자 하는 아틀라스 텍스쳐의 타일 행, 열 갯수, 해상도등을 알고 있다.

그리고 Final Tick에서 생성할때 입력받은 행, 열값에 기반해서 초록색 Debug line을 그린다.

그리고 Render()에서 입력받은 행, 열과 미리 지정한 tile_size에 알맞게 가져오고자 하는 아틀라스에서 이미지를 때와 BitBlt해준다.

void CTileMap::Render()
{
    if (nullptr == m_Atlas)
        return;

    Vec2 OwnerRenderPos = GetOwner()->GetRenderPos();
    HDC dc = CEngine::GetInst()->GetSecondDC();

    // 카메라 영역 안에 들어오는 행, 열을 계산하기
    Vec2 vCamLook = CCamera::GetInst()->GetLookAt();
    int a = 0;
    //Resolution 메인 윈도우 해상도
    Vec2 vResolution = CEngine::GetInst()->GetResolution();
    Vec2 vCamLeftTop = vCamLook - (vResolution / 2.f);
    Vec2 vCamRightBot = vCamLook + (vResolution / 2.f);

    Vec2 vOwnerPos = GetOwner()->GetPos();
    vCamLeftTop = vCamLeftTop - vOwnerPos;

    int LeftTopCol = vCamLeftTop.x / TILE_SIZE;
    int LeftTopRow = vCamLeftTop.y / TILE_SIZE;

    if (LeftTopCol < 0)
        LeftTopCol = 0;
    if(LeftTopRow < 0)
        LeftTopRow = 0;

    vCamRightBot = vCamRightBot - vOwnerPos;
    int RightBotCol = (vCamRightBot.x / TILE_SIZE) + 1;
    int RightBotRow = (vCamRightBot.y / TILE_SIZE) + 1;

    if (m_Col < RightBotCol)
        RightBotCol = m_Col;
    if (m_Row < RightBotRow)
        RightBotRow = m_Row;

    for (int Row = LeftTopRow; Row < RightBotRow; ++Row)
    {
        for (int Col = LeftTopCol; Col < RightBotCol; ++Col)
        {
            // 반복문 회차에 맞는 행렬에 대해서 이게 몇번째 타일정보인지 1차원 인덱스로 변환
            // 해당 타일정보에 접근한다.
            int TileIdx = m_Col * Row + Col;
            int ImgIdx = m_vecTileInfo[TileIdx].ImgIdx;

            // 해당 타일의 ImgIdx 가 -1 인 경우, Blank Tile
            if (ImgIdx == -1)
                continue;

            int ImgRow = ImgIdx / m_AtlasTileCol; //  1 행
            int ImgCol = ImgIdx % m_AtlasTileCol; //   6 열

            assert(!(ImgIdx < 0 || m_AtlasTileCol * m_AtlasTileRow <= ImgIdx));

            //BOOL BitBlt(
            //    HDC hdcDest,    // 대상 DC (출력할 DC)
            //    int nXDest,     // 대상 DC에서 복사된 비트맵을 출력할 X 좌표
            //    int nYDest,     // 대상 DC에서 복사된 비트맵을 출력할 Y 좌표
            //    int nWidth,     // 복사할 비트맵의 너비
            //    int nHeight,    // 복사할 비트맵의 높이
            //    HDC hdcSrc,     // 원본 비트맵이 있는 DC
            //    int nXSrc,      // 원본 DC에서 복사할 영역의 X 좌표
            //    int nYSrc,      // 원본 DC에서 복사할 영역의 Y 좌표
            //    DWORD dwRop     // 복사할 때 사용할 비트 연산 (Raster Operation)
            //);

            BitBlt(dc
                 , (int)OwnerRenderPos.x + Col * TILE_SIZE
                 , (int)OwnerRenderPos.y + Row * TILE_SIZE
                 , TILE_SIZE, TILE_SIZE
                 , m_Atlas->GetDC()
                 , ImgCol * TILE_SIZE, ImgRow * TILE_SIZE
                 , SRCCOPY); 
        }
    }
}

그리고 새로운 obj를 하나 만들어준 다음에 자신이 원하는 행, 열, 아틀라스를 정해주고 Levelmgr을 통해 지금 레벨에 추가해주면 된다.

CTilemap component를 가지는 m_tilemap 생성

타일 사이즈 define.h에서 고정 게임 리소스에 따라서 수치가 달라 질 수 있음 수업용은 64px

배경이미지는 lyaertype background인걸로 levelmgr에서 추가해보자

map이라는 오브젝트는 CTilemap이라는 컴포넌트를 가지고 있는거임 CTilemap에서 원하는 아틀라스의 스프라이트를 넣는거임

bitblit, transbitblt의 차이 bitblt은 마젠타 값을 제외하지 않고 그대로 가져오는 것이고 transbitblt은 마젠타 값을 제외하고 가져오는것 상황에 알맞게 가져오면 된다.

struch.h 의 tTile에 tile형태에서 관리할 수 있는 데이터를 넣을 수 있음 충돌 ,데미지 tile 기반이면 여기서 설정하면 될 듯

기존에는 하나의 Atals에서 여러개의 Sprite를 만들어 Flipbook을 만들었지만 현재 리소스는 여러개의 png로 구성돼있다.

이는 여러개의 Atals가 존재하고 이것 하나하나가 sprite이기 때문에 약간의 변형을 주었다. Atals는 key가 하나씩 존재하는데 이 key를 다른 atlas끼리 동일하게 해서 문제가 발생했었다.

void CPlayer::CreatePngFlipbook(const wstring& _FlipbookName, const wstring& _Pngname, Vec2 _LeftTop, Vec2 _RightBot, int MaxFrame)
{
    // Sprite 생성하기
    for (int i = 0; i < MaxFrame; i++)
    {
        wchar_t filePath[100] = {};
        wchar_t textureName[100] = {};
        // 각 프레임에 대한 경로 생성
        swprintf_s(filePath, 100, L"Texture\\azazel\\%s_%d.bmp", _Pngname.c_str(), i);
        swprintf_s(textureName, 100, L"azazel%d", i);

        CTexture* pAtlas = CAssetMgr::GetInst()->LoadTexture(textureName, filePath);

        CSprite* pSprite = new CSprite;

        // _RightBot를 그대로 넘기지 않고 크기로 사용해야 합니다.
        Vec2 spriteSize = _RightBot - _LeftTop;
        pSprite->Create(pAtlas, _LeftTop, spriteSize);

        // Key를 만들 때, wstring을 미리 생성 후 사용
        wchar_t Key[50] = {};
        swprintf_s(Key, 50, L"%s_%d", _FlipbookName.c_str(), i);  // 여기서 형식 문자열을 분리하여 사용
        CAssetMgr::GetInst()->AddSprite(Key, pSprite);

        wstring strSavePath = L"Sprite\\";
        strSavePath += pSprite->GetKey();
        pSprite->Save(strSavePath);
    }


    for (int i = 0; i < MaxFrame; ++i)
    {
        wchar_t Key[50] = {};
        swprintf_s(Key, 50, (_FlipbookName + L"_%d").c_str(), i);
        wstring Path = L"Sprite\\";
        Path += Key;
        CAssetMgr::GetInst()->LoadSprite(Key, Path + L".sprite");
    }

    // Flipbook 생성하기
    CFlipbook* pFlipbook = new CFlipbook;

    for (int i = 0; i < MaxFrame; ++i)
    {
        wchar_t Key[50] = {};
        swprintf_s(Key, 50, (_FlipbookName + L"_%d").c_str(), i);
        pFlipbook->AddSprite(CAssetMgr::GetInst()->FindSprite(Key));
    }

    CAssetMgr::GetInst()->AddFlipbook(_FlipbookName, pFlipbook);
    wstring Path = L"Flipbook\\";
    pFlipbook->Save(Path + _FlipbookName);
}

풀이는 모두 맞았는데 포장지를 덮는 부분이 반복문 안에 있어 만약 마지막 반복문까지 돌아간 후 포장지 덮는 것이 끝난다면 이를 계산하지 못해 답이 덜 나오거나 아예 0으로 출력됐다.

시작일이 앞선 일정부터 차례대로 채워지지만 시작일이 같을 경우 일정의 기간이 긴 것이 먼저 채워진다는 조건이 있다.

기존 sort를 그대로 사용하면 모든 수들이 오름차순으로 채워지기 때문에 두번째 조건에 맞지 않는다 그래서 comapre라는 비교함수를 만들어서 sort에 사용하였다.

compare(a, b)가 true를 반환하면, a는 b보다 앞에 와야 합니다. compare(a, b)가 false를 반환하면, a는 b보다 뒤에 와야 합니다.

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

vector<pair<int, int>> v;

int map[1000][366];

int min_s = 10000;
int max_t = 0;
int max_z = 0;

int n;

int s, t;

int result = 0;

bool compare(const pair<int,int> &a, const pair<int,int> &b) {
    //x는 같은데
    if (a.first != b.first) {
        return a.first < b.first;
    }
    else {
        return (a.second - a.first) > (b.second - a.first);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    //일정은 시작날짜와 종료날짜를 포함한다.
    //시작일이 가장 앞선 일정부터 차례대로 채워진다.
    //시작일이 같을 경우 일정의 기간이 긴 것이 먼저 채워진다.
    //일정은 가능한 최 상단에 배치된다.
    //일정 하나의 세로의 길이는 1이다.
    //하루의 폭은 1이다.

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s >> t;
        v.push_back({ s,t });
    }

    sort(v.begin(), v.end(), compare);
    //cout << endl;
    for (int i = 0; i < v.size(); i++) {
        //cout << s << " " << t << endl;
        s = v[i].first;
        t = v[i].second;

        //다른 종이를 붙일 타이밍
        if (max_t + 1 < s && i != 0) {
            //cout << 1 << endl;
            result += (max_t - min_s + 1) * max_z;
            min_s = 10000;
            max_t = 0;
            max_z = 0;
        }

        for (int z = 1; z <= n; z++) {
            int flag = 0;
            for (int q = s; q <= t; q++) {
                if (map[z][q] == 1) {
                    flag = 1;
                    break;
                }
            }
            //일정이 칠해져있지 않으면 추가함
            if (flag == 0) {
                for (int q = s; q <= t; q++) {
                    map[z][q] = 1;
                    min_s = min(q, min_s);
                    max_t = max(q, max_t);
                    max_z = max(z, max_z);
                }
                break;
            }
        }
    }

    result += (max_t - min_s + 1) * max_z;

    cout << result;

    return 0;
}

Minimum Spanning Tree(MST)는 최소 스패닝 트리로 하나의 시작점에서 다른 모든 노드까지의 최단 경로를 찾는 것이 목표이다.

즉 그래프의 모든 노드를 포함하는 최소 비용 트리를 반환한다. 모든 노드를 방문해야 하며, 경로는 중요하지 않고 총 비용이 최소가 되는 트리를 만듭니다.

Dijkstra와의 차이

Dijkstra는 한 노드에서 각기 다른 노드들까지 도착할 수 있는 최소 값을 구하는 것으로 모든 노드들이 연결돼있을때 최소 값을 구하는 MST와는 차이가 있다.

Dijkstra에서 c까지는 3이겠지만 MST에서는 굳이 A에서 연결한 값을 더할 필요가 없기때문에 E에서 바로 C로 가는 2가 나온다.

MST 예시 문제

백준 1197 최소 스패닝 트리

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

int v, e;
int mst[10001];
vector < pair<int, pair<int, int>>> li;
int result = 0;

//-2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

int find(int x) {
    if (mst[x] == x) return x;
    return mst[x] = find(mst[x]);
}    

void _union(int x, int y) {
    x = find(x);
    y = find(y);
    if (x > y) {
        mst[x] = y;
    }
    else {
        mst[y] = x;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> v >> e;

    //초기화
    for (int i = 0; i <= v; i++) {
        mst[i] = i;
    }

    for (int i = 0; i < e; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        li.push_back({ c,{a,b} });
    }

    sort(li.begin(), li.end());

    for (int i = 0; i < li.size(); i++) {
        int x = li[i].second.first;
        int y = li[i].second.second;
        //부모가 같이 않으면 사이클이 발생할 수 없음
        if (find(x) != find(y)) {
            //연결함
            _union(x, y);
            result += li[i].first;
        }
    }

    cout << result;

    return 0;
}

생성자에서 CreatePlayerFlipbook을 통해 Player obj의 애니메이션을 만들고자 하였다.

Flipbook이란

책장마다 연속적인 그림을 포함하고 있어 책장을 빠르게 넘기면 그림이 움직이는 듯하게 보이는 효과가 있는 책을 뜻한다.

CreatePlayerFlipbook

CreatePlayerFlipbook에서는 CreateFlipbook으로 플립북을 생성하고 AddFlipbook으로 자신이 원하는 key name으로 플립북을 등록한다.

Atlas

Atlas는 주로 게임 개발과 그래픽 프로그래밍에서 사용되는 개념으로, 여러 개의 작은 이미지를 하나의 큰 이미지에 합쳐놓은 것을 의미한다.

아래와 같은 이미지에서 Flipbook을 만들 구역을 지정하고 구역 내 이미지를 1장씩 잘라 Sprite를 만들어 그것을 합쳐 한장씩 재생함으로서 Flipbook을 만든다.

CreateFlipbook

인자로는 만들고자 하는 플립북의 이름, 원본 Atlas, 시작점의 좌표, 1번째 장의 끝 좌표, 장면 갯수이다.

LeftTop부터 _Slice까지의 위치를 i번째 frame으로 생각하고 SpriteType 포인터로 만들어진 vector에 저장한다.

과거 풀었던 비슷한 단계의 내리막길 문제와 유사해 풀이법을 생각해냈다. 대나무가 적힌 map을 입력받고 모든 위치에서의 먹을 수 있는 넓이를 구해야 하기에 처음엔 모든 index에 접근하지만 이전 재귀에서 한번이라도 접근했던 곳은 다시 접근하지 않게 했다.

만약 현재 이미 방문한 기록이 있으면 그 위치에서는 더 발전될 가능성이 없다. 이미 이전 재귀에서 해당 위치보다 대나무 수가 많은 곳은 이미 방문하였기 때문이다.

범위 내 상하좌우에 방문해 현재 대나무보다 많은 곳이 있다면 그곳을 추가 방문한다.

만약 문제 index가 [0][3] 으로 1 2 3 4로 위치한다고 가정하자

맨 처음 1에서 2로 이동하고 2는 자신이 현재 처음방문하였기에 자신의 값을 1로 지정한다.

그 뒤로 2에서 3으로 이동하고 3은 자신이 현재 처음 방문하였기에 자신의 값을 1로 지정한다.

3역시 같은 과정을 반복한다.

4까지 도착했을때 4는 더이상 자신의 위치에서 더 갈 곳이 없다. 자신 주위에는 더이상 대나무 밭이 없거나 자신보다 작은(3)대나무 밭 만이 존재하기 때문이다.

이때 return eat[x][y]로 이전 대나무 밭의 깊이를 정해준다.

1부터 4까지 dfs 후 return이기에 값은 4->1순으로 return된다. 3은 자신의 현재 값(1)과 이전 대나무밭(4)의 크기에 1을 더한것을 비교해 현재 자신의 밭 크기를 정한다.

1을 더한 것으로 비교하는 이유는 4는 현재 자신보다 1칸 더 먹었기 때문이다.

그렇기에 3은 2가 된다.

2는 앞서 3이 한 것과 마찬가지로 자신의 값과 3의 결과 + 1를 비교한다. 이와 같은 과정을 반복하면

1위치의 대나무밭 깊이는 4가 된다.

정답

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

int n;

int map[501][501];
int eat[501][501];
int result = 0;

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

int dfs(int x, int y) {

    if (eat[x][y] != 0) {
        return eat[x][y];
    }
    //이미 방문한 기록이 있으면 위에서 반환했음
    eat[x][y] = 1;

    //cout << x << " " << y << " " << cur_count << endl;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (0 <= nx && nx < n && 0 <= ny && ny < n) {
            if (map[x][y] < map[nx][ny]) {
                eat[x][y] = max(eat[x][y], dfs(nx, ny) + 1);
            }
        }
    }

    return eat[x][y];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

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

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (eat[i][j] == 0) {
                result = max(result, dfs(i, j));
            }
        }
    }

    cout << result;

    return 0;
}

다익스트라 알고리즘은 하나의 시작 정점에서 다른 모든 정점까지 최단 경로를 구하는 알고리즘이다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#define INF 987654321
using namespace std;


priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;
int n, m, r;
//위치 아이템
int goods[101];
//거리 저장
int li[101];
vector<pair<int,int>> v[101];
int result = 0;

void dij(int x) {

    for (int i = 1; i <= n; i++)
        li[i] = INF;

    li[x] = 0;

    pq.push({ 0,x });
    //거리 ,위치 
    //거리가 작은 순서대로 방문하고 만약 그곳 방문했으면 다시방문 안해도됨
    while (!pq.empty()) {
        int distance = pq.top().first;
        int point = pq.top().second;
        pq.pop();

        for (int i = 0; i < v[point].size(); i++) {
            int next_point = v[point][i].first;
            int next_distance = v[point][i].second;
            int sum_distance = distance + next_distance;
            //탐색 가능한 범위내에 있을때
            if (sum_distance < li[next_point]) {
                li[next_point] = sum_distance;
                pq.push({ sum_distance, next_point });
            }
        }
    }
    int cur_result = 0;

    for (int i = 1; i <= n; i++) {
        if (li[i] <= m) {
            cur_result += goods[i];
        }
    }

    result = max(cur_result, result);
}

int main() {
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m >> r;

    for (int i = 1; i <= n; i++) {
        cin >> goods[i];
    }

    for (int i = 0; i < r; i++) {
        //c는 탐색범위임
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }

    for (int i = 1; i <= n; i++) {
        //예은이가 1번 지역부터 n번 지역까지 가는 경우의 수에서 검사
        dij(i);
    }

    cout << result;

    return 0;
}

플로이드-워셜을 통해 해결하는 문제 같지만 BFS를 통해 해결했다. 회장 후보를 알아내야 하기 때문에 모든 인원이 회장후보가 가능한지 부터 시작하였다. 예제에서는 모든 사람이 1개 이상의 관계를 가지고 있는 것 같았지만 혹시나 없을 수도 있기에 만약 SIZE가 0라면 진행하지 않았다.

자신의 인간관계를 거치면서 다녀온 인간관계는 현재 인간관계에서 +1 해주었고 최대 깊이 인간 관계를 계속 업데이트 해줬다.

마지막으로 현재 사람의 인간관계 깊이에 현재 사람 번호를 넣고 최소 인간 관계층을 업데이트 한 후 마지막에 출력해주었다.

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

struct DATA {
    int cur;
    int floor;
};
vector<int> v[51];
vector<int> result[51];
int n = 0;
int a, b;
bool check[51];

int minfloor = 9999999999;

void solve(int a) {
    memset(check, false, sizeof(check));
    queue<DATA> q;
    int maxfloor = 0;
    q.push({a, 0});

    check[a] = true;

    while (!q.empty()) {
        int cur = q.front().cur;
        int floor = q.front().floor;
        q.pop();

        //cout << cur << " " << floor << endl;

        maxfloor = max(maxfloor, floor);

        for (int i = 0; i < v[cur].size(); i++) {
            if (check[v[cur][i]] == false) {
                check[v[cur][i]] = true;
                q.push({ v[cur][i], floor + 1 });
            }
        }
    }
    result[maxfloor].push_back(a);
    minfloor = min(maxfloor, minfloor);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    while (true) {
        cin >> a >> b;
        if (a == -1 && b == -1) {
            break;
        }
        v[a].push_back(b);
        v[b].push_back(a);
    }

    //1~n번째 사람까지의 회장 후보 검사
    for (int i = 1; i <= n; i++) {
        if (v[i].size() == 0) continue;
        solve(i);
    }

    cout << minfloor << " " << result[minfloor].size() << "\n";
    for (int i = 0; i < result[minfloor].size(); i++) {
        cout << result[minfloor][i] << " ";
    }

    return 0;
}

스프라이트는 텍스쳐를 알고있다. 그렇기 때문에 플립북은 스프라이트를 알고 있어야 한다.

sprite는 Asset으로부터 key값이랑 경로를 알고 있어야 한다. sprite는 가리키던 atlas 텍츠셔의 key값이랑 경로값을 알고 있어야 한다. 이건 자주 사용하기 때문에 함수로 만들어준다.

Sprite: 애니메이션이나 게임에서 사용되는 이미지 또는 그림의 집합입니다. 보통 여러 프레임이 하나의 이미지 파일에 모여 있으며, 이 프레임들은 캐릭터나 오브젝트의 다양한 상태(예: 걷기, 점프하기 등)를 표현합니다.

Flipbook: 일반적으로 스프라이트 시트에서 한 프레임씩 순차적으로 표시하여 애니메이션을 만드는 방식입니다. 각 프레임은 동영상을 만드는 것처럼 연속적으로 빠르게 전환되어 애니메이션 효과를 생성합니다. 이 과정은 종종 "플립북 애니메이션"이라고도 불립니다.

아틀라스(Sprite Atlas)는 여러 개의 스프라이트(이미지)나 텍스처를 하나의 큰 이미지 파일에 모아놓은 것을 말합니다. 주로 게임 개발에서 사용되며, 이 방식은 여러 개의 작은 이미지를 각각 따로 로드하는 대신, 하나의 큰 이미지를 사용해 성능을 최적화할 수 있다는 장점이 있습니다.

무언가를 저장할때 주소를 저장하는 것은 위험하다. 현재 모든 것은 동적 할당인데 나중에 내가 해당 데이터에 접근하고자 할때 값 자체를 저장하는 것이 아니라 주소값을 저장한다면 나중에 프로그램을 재시작하고 해당 주소에 접근했을때 해당 주소에는 다른 값이 동적할당돼 이상한 결과를 가져올 수 있기 때문이다.

Union-find를 통해 해결한 문제이다. 여행 계획에 속한다는 것은 맨 마지막에 입력되는 도시들이 같은 집합에 속해야 한다는 것을 의미한다.

그렇기에 입력받는 도시들을 모두 연결해 준다.

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

int city[20000];

int n, m;

int find(int x) {
    //자기 자신이 최상위 노드일 경우 x return;
    if (city[x] == x) return x;
    return city[x] = find(city[x]);
}

void _union(int x, int y) {
    int _x = find(x);
    int _y = find(y);
    //_x가 더 작을경우 _x가 최상위 노드가됨
    if (_x < _y) {
        city[_y] = _x;
    }
    else {
        city[_x] = _y;
    }
}

bool get_find(int x, int y) {
    int a = find(x);
    int b = find(y);
    if (a == b) return true;
    else return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        city[i] = i;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int a;
            cin >> a;    
            if (a == 1) {
                _union(i, j);
            }
        }
    }

    int top = 0;

    for (int i = 0; i < m; i++) {
        int a;
        cin >> a;
        a--;
        if (i == 0) top = find(a);
        else {
            if (!get_find(top, a)) {
                cout << "NO";
                return 0;
            }
        }
    }

    cout << "YES";

    return 0;
}

문제 해결에 너무 어려움을 겪고 있다. 분명히 쉽게 해결 할 수 있는 문제임에도 바로 해결법을 떠올리지 못해 답답하다.

정답

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

int n = 0;

char map[6][6];

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

int min_r = 1e9;
int max_r = -1e9;

void solve(int x, int y, int r) {

    if (x == n && y == n) {
        min_r = min(min_r, r);
        max_r = max(max_r, r);
        return;
    }

    for (int i = 0; i < 2; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx > n || ny > n) continue;
        int nr = r;
        if (map[x][y] == '-') {
            nr -= map[nx][ny] - '0';
        }
        else if (map[x][y] == '+') {
            nr += map[nx][ny] - '0';
        }
        else if (map[x][y] == '*') {
            nr *= map[nx][ny] - '0';
        }
        //연산자가 아니면 연산할 수 없으니까 그냥 이전 값 그대로 넘김
        solve(nx, ny, nr);
    }
    return;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> map[i][j];
        }
    }

    solve(1, 1, map[1][1] -'0');

    cout << max_r << " " << min_r;

    return 0;
}

오답

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



int n = 0;

char map[6][6];
int max_dp[6][6];
int min_dp[6][6];

int dx[2] = { 2,0 };
int dy[2] = { 0,2 };
int mx[2] = { 1,0 };
int my[2] = { 0,1 };

int min_r;
int max_r;

void min_solve(int x, int y, int r) {

    min_dp[x][y] = min(min_dp[x][y], r);

    if (x == n && y == n) {
        min_r = min_dp[x][y];
        return;
    }

    for (int i = 0; i < 2; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx > n || ny > n) continue;
        if (map[x + mx[i]][y + my[i]] == '-') {
            min_solve(x + dx[i], y + dy[i], min_dp[x][y] - map[x + dx[i]][y + dy[i]] - '0');
        }
        if (map[x + mx[i]][y + my[i]] == '+') {
            min_solve(x + dx[i], y + dy[i], min_dp[x][y] + map[x + dx[i]][y + dy[i]] - '0');

        }
        if (map[x + mx[i]][y + my[i]] == '*') {
            min_solve(x + dx[i], y + dy[i], min_dp[x][y] * map[x + dx[i]][y + dy[i]] - '0');
        }
    }
    return;
}

void max_solve(int x, int y, int r) {
    max_dp[x][y] = max(max_dp[x][y], r);

    if (x == n && y == n) {
        max_r = max_dp[x][y];
        return;
    }
    for (int i = 0; i < 2; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx > n || ny > n) continue;
        if (map[x + mx[i]][y + my[i]] == '-') {
            max_solve(x+dx[i],y+dy[i], max_dp[x][y]- map[x + dx[i]][y + dy[i]] - '0');
        }
        if (map[x + mx[i]][y + my[i]] == '+') {
            max_solve(x + dx[i], y + dy[i], max_dp[x][y] + map[x + dx[i]][y + dy[i]] - '0');

        }
        if (map[x + mx[i]][y + my[i]] == '*') {
            max_solve(x + dx[i], y + dy[i], max_dp[x][y] * map[x + dx[i]][y + dy[i]] - '0');
        }
    }
    return;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> map[i][j];
        }
    }

    min_solve(1, 1, 0);
    max_solve(1, 1, 0);

    cout << max_r << " " << min_r;

    return 0;
}