https://www.codetree.ai/training-field/frequent-problems/problems/maze-runner?&utm_source=clipboard&utm_medium=text

중요포인트

행과 열을 헷갈리지 말자!!

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cstring>
#include <tuple>
#include <iomanip>

using namespace std;

struct Player {
    int y, x, howmany;
};

int N, M, K, exitY, exitX, maze[11][11], player[11][11], dy[4] = { -1,1,0,0 }, dx[4] = { 0,0,-1,1 }, totalDis = 0;

void printMaze() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cout << setw(3) << maze[i][j];
        }
        cout << "\n";
    }
}

bool oob(int y, int x) {
    return y < 1 || x < 1 || y > N || x > N;
}

void rotate(tuple<int, int, int> pointWithSize) {
    int size = get<2>(pointWithSize);
    vector<vector<int>> tmp(size + 1, vector<int>(size + 1, 0));
    int row = get<0>(pointWithSize), col = get<1>(pointWithSize);

    for (int i = 1; i <= size; i++) {
        for (int j = 1; j <= size; j++) {
            tmp[j][size - i + 1] = maze[row + i - 1][col + j - 1];
            if (tmp[j][size - i + 1] > 0) tmp[j][size - i + 1]--;
        }
    }

    for (int i = 1; i <= size; i++) {
        for (int j = 1; j <= size; j++) {
            maze[row + i - 1][col + j - 1] = tmp[i][j];
        }
    }
}

tuple<int, int, int> findSmallSqure() {
    tuple<int, int, int> pointWithSize;
    int eY, eX;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (maze[i][j] == -11) {
                eY = i;
                eX = j;
            }
        }
    }

    for (int size = 2; size <= N; size++) {
        for (int i = 1; i <= N - size + 1; i++) {
            for (int j = 1; j <= N - size + 1; j++) {
                int peopleCount = 0;
                bool hasExit = false;

                for (int row = i; row < i + size; row++) {
                    for (int col = j; col < j + size; col++) {
                        if (maze[row][col] == -11) hasExit = true;
                        else if (-10 <= maze[row][col] && maze[row][col] <= -1) peopleCount += -1 * maze[row][col];
                    }
                }

                if (hasExit && peopleCount >= 1) {
                    pointWithSize = {i, j, size};
                    return pointWithSize;
                }
            }
        }
    }
    return pointWithSize;
}

void move() {
    int eY, eX, tmp[21][21];
    queue<pair<int, int>> q;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            tmp[i][j] = 0;
            if (maze[i][j] == -11) {
                eY = i;
                eX = j;
            } else if (maze[i][j] <= -1 && -10 <= maze[i][j]) {
                q.push({i, j});
            }
        }
    }

    while (!q.empty()) {
        int curY = q.front().first, curX = q.front().second;
        q.pop();
        int moveY = 0, moveX = 0, exitDis = abs(eY - curY) + abs(eX - curX);

        for (int d = 0; d < 4; d++) {
            int ny = curY + dy[d], nx = curX + dx[d];
            if (oob(ny, nx) || maze[ny][nx] > 0) continue;
            int dis = abs(ny - eY) + abs(nx - eX) + 1;
            if (exitDis < dis) continue;
            else if (exitDis == dis) {
                if ((eY - curY > 0 && ny - curY > 0) || (eY - curY < 0 && ny - curY < 0) || maze[ny][nx] == -11) {
                    moveY = ny;
                    moveX = nx;
                } else if (moveY == 0) {
                    moveY = ny;
                    moveX = nx;
                }
            }
        }

        if (moveY != 0) {
            totalDis += maze[curY][curX] * -1;
            if (maze[moveY][moveX] != -11) tmp[moveY][moveX] += maze[curY][curX];
            maze[curY][curX] = 0;
        }
    }

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (tmp[i][j] != 0) maze[i][j] += tmp[i][j];
        }
    }
}

bool isAllEmpty() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (-10 <= maze[i][j] && maze[i][j] <= -1) return false;
        }
    }
    return true;
}

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

    for (int i = 0; i < M; i++) {
        int y, x;
        cin >> y >> x;
        maze[y][x] -= 1;
    }

    cin >> exitY >> exitX;
    maze[exitY][exitX] = -11;

    while (K--) {
        if (isAllEmpty()) break;
        move();
        tuple<int, int, int> pointWithSize = findSmallSqure();
        rotate(pointWithSize);
    }

    cout << totalDis << "\n";
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (maze[i][j] == -11) cout << i << " " << j;
        }
    }
    return 0;
}

https://www.codetree.ai/training-field/frequent-problems/problems/magical-forest-exploration?&utm_source=clipboard&utm_medium=text

문제 로직

1. 골렘이 남쪽으로 갈 수 있을 때까지 내려간다.
2. 골렘이 왼쪽 그리고 왼쪽 아래쪽으로 갈수있다면 왼쪽으로 구른다.
3. 왼쪽으로 가지 못한다면, 골렘이 오른쪽 그리고 오른쪽 아래쪽으로 갈 수 있다면 오른쪽으로 구른다.
4. 아래, 왼쪽 & 왼쪽아래, 오른쪽 & 오른쪽아래 세곳 모두 움직이지 못한다면 골렘의 숲을 탐색한다.

계속되는 실수

구른 뒤 중력을 생각했어야지

문제를 잘못 이해해서 왼쪽으로 구른다는 것을 골렘의 현재 위치 (y,x) -> 구른 뒤 위치 (y+1,x-1) 로 이해했다.

여기서 중요한 점은 (y,x) -> (y+1, x-1) 이 아닌 (y+n, x-1) ( n : 아래쪽으로 내려갈 수 있는 최대 값) 이라는 것이다.

계속 왼쪽한칸 아래한칸 만 움직이니 답이 제대로 나올리가 없었다.

애매한 위치 저장 방법

기존 코드는 탈출구 저장을 이상하게 했다. 탐색하고자 하는 위치를 기준으로 4방향 중 음수인 값이 탈출구이므로 그때 방향을 알게되는 것.

이렇게 되면 방향을 잘못 설정할 수 가 있다는 것이다. 따라서, 나는 Golem 이라는 구조체하나를 생성해서 방향 관리를 하게 되었다.

정답 코드

int main() {
    // 여기에 코드를 작성해주세요.

    cin >> R >> C >> K;
    int ans = 0;
    for (int i = 0; i < K; i++) {
        int sRow, dir;
        cin >> sRow >> dir;
        //인덱스 0 으로 맞추기위한 빼기
        //0 북 1 동 2 남 3 서
        sRow -= 1;

        int curY = 1;
        int curX = sRow;

        Golem golem;
        golem.num = i + 1;
        golem.y = curY;
        golem.x = curX;
        golem.dir = dir;

        while (canMoveDown(golem)) {}

        while(canMoveRL(golem)){}

        if (isFull()) {
            fill(&map[0][0], &map[0][0] + 80 * 80, 0);
        }
        else {
            ans += bfs(golem);
        }
    }
    cout << ans;
    return 0;
}

1. 골렘의 생성위치와 골렘의 번호 및 방향을 붙여 관리
2. 해당 골렘이 canMoveDown을 통해 밑으로 갈 수 있을 만큼 가고
3. canMoveRL 을 통해 왼쪽으로 오른쪽으로 구를 수 있을만큼 구른 후
4. 위치한 골렘이 맵을 벗어나면 초기화하거나
5. 그렇지않다면 골렘의 숲을 탐색한다.

개선점

canMoveDown 과 canMoveRL을 지금보면 합칠 수 있을 것 같다. 하지만, 귀찮아서 나중에할래 ㅎㅎ

전체 코드

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

int R, C, K;
int map[80][80];

struct Golem {
    int y, x;
    int num;
    int dir;
};

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

bool oob(int y, int x) {
    return y < 0 || x < 0 || y >= R + 3 || x >= C;
}

void print() {
    for (int i = 0; i < R + 3; i++) {
        for (int j = 0; j < C; j++) {
            cout << map[i][j] << "  ";
        }
        cout << "\n";
    }
}
void clearMap(int y, int x) {
    map[y][x] = 0;
    for (int d = 0; d < 4; d++) {
        int ny = y + dy[d];
        int nx = x + dx[d];
        map[ny][nx] = 0;
    }
}

bool canMove(Golem &golem, int ey, int ex) {

    //초기위치 초기화
    clearMap(golem.y, golem.x);

    //다음 움직일 곳으로 갈수 있는지?
    for (int d = 0; d < 4; d++) {
        int ny = ey + dy[d];
        int nx = ex + dx[d];

        if (map[ny][nx] != 0 || oob(ny, nx)) {
            int sy = golem.y; int sx = golem.x;
            map[sy][sx] = golem.num;
            for (int dd = 0; dd < 4; dd++) {
                int nny = sy + dy[dd];
                int nnx = sx + dx[dd];
                map[nny][nnx] = golem.num;
            }
            map[sy + dy[golem.dir]][sx + dx[golem.dir]] = golem.num * -1;
            return false;
        }
    }

    // 움직일 수 있따면
    int sy = golem.y; int sx = golem.x;
    map[sy][sx] = golem.num;
    for (int dd = 0; dd < 4; dd++) {
        int nny = sy + dy[dd];
        int nnx = sx + dx[dd];
        map[nny][nnx] = golem.num;
    }
    map[sy + dy[golem.dir]][sx + dx[golem.dir]] = golem.num * -1;
    return true;
}

void setMap(Golem & golem,int lr) {
    //cout << "setMap " << ey << ex << num<<"\n";
    clearMap(golem.y, golem.x);

    if (lr == 1) {//right
        golem.dir = (golem.dir + 1) % 4;
        golem.x += 1;
        golem.y += 1;
    }
    else if (lr == 2) { golem.dir = (golem.dir + 3) % 4; 
    golem.x -= 1;
    golem.y += 1;
    }
    else if(lr == 0) {
        golem.y += 1;
    }
    else if (lr == -1) {

    }


    int ey = golem.y;
    int ex = golem.x;

    //움직이고자 하는 위치에 맵 저장
    map[ey][ex] = golem.num;
    for (int dir = 0; dir < 4; dir++) {
        int ny = ey + dy[dir];
        int nx = ex + dx[dir];
        map[ny][nx] = golem.num;
    }
    map[ey + dy[golem.dir]][ex + dx[golem.dir]] = golem.num * -1;

}
bool canMoveDown(Golem &golem) {
    int dy = golem.y + 1;
    int dx = golem.x;

    if (canMove(golem,  dy, dx)) {
        setMap(golem, 0);
        return true;
    }

    return false;
}

bool canMoveRL(Golem &golem) {


    //현재 위치에서 오른쪽 왼쪽 갈수있는지

    int y = golem.y;
    int x = golem.x;


    int ly = y;
    int lx = x - 1;
    while (canMoveDown(golem)) {}

    if (canMove(golem, ly, lx) && canMove(golem, ly + 1, lx)) {
        setMap(golem, 2);
        while (canMoveDown(golem)) {}
        //cout << "move left\n";
        return true;
    }

    setMap(golem,-1);

    //move right
    int ry = y;
    int rx = x + 1;

    if (canMove(golem, ry, rx) && canMove(golem, ry + 1, rx)) {
        setMap(golem, 1);
        while (canMoveDown(golem)) {}
        //cout << "move right\n";
        return true;
    }
    setMap(golem,-1);
    return false;
}


bool isFull() {
    for (int i = 0; i < C; i++) {
        if (map[2][i] != 0) {
            return true;
        }
    }
    return false;
}

int bfs(Golem &golem) {
    queue<pair<int, int>> q;
    int maxDepth = 0;
    q.push({ golem.y, golem.x });
    bool v[80][80];
    fill(&v[0][0], &v[0][0] + 80 * 80, false);
    v[golem.y][golem.x] = true;

    //print();
    while (!q.empty()) {
        int yy = q.front().first;
        int xx = q.front().second;
        q.pop();
        for (int d = 0; d < 4; d++) {
            int ny = yy + dy[d];
            int nx = xx + dx[d];
            if (oob(ny, nx) || v[ny][nx])continue;
            if (map[ny][nx] == 0)continue;
            if (map[yy][xx] > 0) {
                if (map[ny][nx] > 0) {
                    if (map[ny][nx] != map[yy][xx])continue;
                }
                else if (map[ny][nx] < 0) {
                    if (map[ny][nx] != -1 * map[yy][xx])continue;
                }
                //cout << yy << " " << xx << " " << map[ny][nx] << "-\n";
                q.push({ ny,nx });
                v[ny][nx] = true;
                maxDepth = max(maxDepth, ny);
            }
            else if (map[yy][xx] < 0) {
                //cout << yy << " " << xx << " " << map[yy][xx] << " " << map[ny][nx] << "-\n";
                q.push({ ny,nx });
                v[ny][nx] = true;
                maxDepth = max(maxDepth, ny);
            }
        }
    }
    //cout << "값 : " << maxDepth - 2 <<"\n";
    return maxDepth - 2;
}


int main() {
    // 여기에 코드를 작성해주세요.

    cin >> R >> C >> K;
    int ans = 0;
    for (int i = 0; i < K; i++) {
        int sRow, dir;
        cin >> sRow >> dir;
        //인덱스 0 으로 맞추기위한 빼기
        //0 북 1 동 2 남 3 서
        sRow -= 1;

        int curY = 1;
        int curX = sRow;

        Golem golem;
        golem.num = i + 1;
        golem.y = curY;
        golem.x = curX;
        golem.dir = dir;

        while (canMoveDown(golem)) {}

        while(canMoveRL(golem)){}

        if (isFull()) {
            fill(&map[0][0], &map[0][0] + 80 * 80, 0);
        }
        else {
            ans += bfs(golem);
        }
    }
    cout << ans;
    return 0;
}

https://www.acmicpc.net/problem/1011

문제 개요
이 문제는 우주선이 현재 위치에서 목표 위치로 이동할 때, 주어진 규칙에 따라 최소한의 이동 횟수를 구하는 문제이다. 이동하는 규칙은 다음과 같다:

1. 우주선은 매번 이동할 때마다 "최대 속도"가 1만큼 변할 수 있다. 이 최대 속도는 1부터 시작하며, 속도는 양수만 가능하다.
2. 우주선이 목표 위치에 도달하기 전까지 속도를 감소시킬 수 없다. 즉, 우주선이 목표 위치에 도달할 때까지 속도는 증가하거나 일정하게 유지될 수 있다.
3. 목표 위치에 도달한 순간에는 속도가 0이 된다.

입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스는 두 정수 (x)와 (y)로 이루어져 있으며, 이는 우주선의 현재 위치와 목표 위치를 나타낸다. (0 ≤ x < y ≤ (2^{31}-1))

출력
각 테스트 케이스에 대해, 목표 위치에 도달하기 위한 최소 이동 횟수를 출력한다.

문제 풀이

이 문제를 풀기 위해서는 특정 패턴을 찾는 것이 중요하다. 먼저, 거리 (d = y - x)를 계산한 뒤, 이 거리에 도달하기 위해 우주선이 취할 수 있는 이동 패턴을 살펴봐야 한다.

1. 거리 분석

우주선이 움직일 수 있는 패턴은 다음과 같다:

• 시작할 때 속도를 1씩 증가시키다가, 일정 속도로 유지한 후, 다시 1씩 감소시키며 목표 위치에 도달한다.
• 증가하는 속도 구간과 감소하는 속도 구간의 대칭성을 고려해야 한다.

2. 움직임 패턴

• 거리 (d)에 대해, 속도를 증가시켜서 움직일 수 있는 최대 거리와 그에 필요한 횟수를 계산한다.
• 그 후, 남은 거리만큼 추가적인 이동이 필요한지 판단한다.

이동 패턴 정리

• (n^2 \leq d < (n+1)^2) 일 때, 이 거리를 최소한의 이동으로 도달할 수 있는 패턴은:
  • (d = n^2) -> 총 2n - 1번 이동
  • (n^2 < d \leq n^2 + n) -> 총 2n번 이동
  • (n^2 + n < d < (n+1)^2) -> 총 2n + 1번 이동

이를 바탕으로 C++ 코드를 작성하였다.

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

int main() {
    int t;
    cin >> t;

    while (t--) {
        long long x, y;
        cin >> x >> y;
        long long d = y - x;
        long long n = sqrt(d);

        if (d == n * n) {
            cout << 2 * n - 1 << endl;
        } else if (n * n < d && d <= n * n + n) {
            cout << 2 * n << endl;
        } else {
            cout << 2 * n + 1 << endl;
        }
    }

    return 0;
}

코드 설명

1. 거리 계산: 각 테스트 케이스에 대해 목표 위치와 현재 위치의 거리를 계산한다.
2. 최소 이동 횟수 계산: 주어진 거리 (d)에 대해 최소 이동 횟수를 계산한다. 이때, 거리의 제곱근을 기준으로 3가지 경우로 나누어 결과를 구한다.
   • (d = n^2) 일 경우: 2n - 1번 이동
   • (n^2 < d \leq n^2 + n) 일 경우: 2n번 이동
   • (n^2 + n < d < (n+1)^2) 일 경우: 2n + 1번 이동

결론

이 문제는 수학적 패턴을 분석하는 과정이 중요하다. 각 테스트 케이스에서 목표 위치에 도달하기 위한 최소한의 이동 횟수를 구하기 위해 제곱근과 그 범위에 따른 계산이 핵심이다. 위의 알고리즘을 사용하면 효율적으로 문제를 해결할 수 있다.

2011번: 암호코드

문제

상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.

• 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.
• 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어.
• 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아?
• 선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그걸 언제 다해봐?
• 상근: 얼마나 많은데?
• 선영: 구해보자!

어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작성하시오.

문제 풀이

알고리즘 : 다이나믹 프로그래밍

왜 와이? : 경우의 수를 세고 최적화 위해

설명

1. 입력은 문자열로 받고 for loop 순회를 한다.
2. 현재 인덱스(i) 와 이전 인덱스 (i-1)를 통해 현재 위치에서 26이하인 숫자임을 확인한다.
3. 26이하라면 DP[i] += DP[i-1] + DP[i-2]
   • 두자리 숫자를 쓸 경우와 한자리의 숫자만 쓸경우를 더한다.
4. 26초과라면 DP[i] += DP[i-1]
   • 한자리의 숫자만 사용할 수 있다.

하지만 코드가 옳지 않은 경우 0 을 출력해야한다.

0이 되는 경우

1. 두자리 숫자를 합쳤을 시 26 이상
2. 0이 두번이상 붙어 나올 경우
3. 맨앞에 0 이 나올 경우

또한, 0이 나와도 가능한 경우 0이 아닐 때 사용되는 풀이와 다른 풀이를 적용해야한다.

즉, 한자리 숫자만 쓸 경우는 빼고 생각해야한다.

이렇게 복잡하게 해야하나 싶다. 일단 내 머릿속에 나온거니 정리해본다.

풀이 총정리

1. 문자열로 입력 받아 for loop
2. 현재 인덱스와 이전 인덱스 문자를 조합해 두자리 숫자를 만들어본다.
3. 현재 위치가 0 이거나 이전 위치가 0 이거나 이후 위치가 0 이면 멈출지 말지 본다
4. dp 배열 업데이트

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

typedef long long ll;

int N;

ll dp[5010];
int main (){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    string str;
    cin >> str;
    dp[0] = 1;
    dp[1] = 1;

    //맨앞자리가 0이면 종료
    if(str[0] == '0'){
        cout << 0;
        return 0;
    }

    for(int i = 1;i<str.size();i++){
            //두자리 숫자 만들어보자
        int one = str[i] - '0';
        int ten = str[i-1] -'0';
        int number = ten * 10 + one;

                //현재 인덱스가 0이라면?
        if(str[i] == '0'){
                //0이어도 26안넘으면 오케이, 하지만 00 이면 탈락
            if(number > 26 || number == 0){
                cout << 0;
                return 0;
            }else{
                    //dp 이월
                dp[i+1] = dp[i];
                continue;
            }
            //이전 인덱스가 0이라면?
        }else if(str[i-1] == '0'){
                //dp 이월
            dp[i+1] = dp[i];
            continue;
            //다음 인덱스가 0이라면?
        }else if(i+1 <= str.size() && str[i+1] == '0'){
            dp[i+1] = dp[i];
            continue;
        }

        if(number > 26){
            dp[i+1] =(dp[i+1] + dp[i] )% rest;
        }else{
            dp[i+1] = (dp[i+1] + dp[i] + dp[i-1]) %rest;
        }
    }
    cout << dp[str.size()];
    return 0;
}

나의 코드가 너무 지저분해서 지피티형에게 수정해달라고 할거다

도와줘요 지피티

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

typedef long long ll;

const int MOD = 1000000;
ll dp[5001];  // 최대 길이 + 1

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

    string s;
    cin >> s;

    if (s.empty() || s[0] == '0') {  // 비어있거나 0으로 시작하면
        cout << 0;
        return 0;
    }

    dp[0] = 1;  // 초기 조건 설정
    dp[1] = 1;

    for (size_t i = 1; i < s.length(); i++) {
        int current = s[i] - '0';  // 현재 문자를 숫자로 변환
        int prev = s[i-1] - '0';  // 이전 문자를 숫자로 변환
        int number = prev * 10 + current;  // 두 자리 수

        if (current == 0) {  // 현재 숫자가 '0'인 경우
            if (number == 0 || number > 26) {  // "00"이거나 "30", "40"...
                cout << 0;
                return 0;
            }
            dp[i+1] = dp[i-1];  // "10"이나 "20"
        } else {  // '0'이 아닌 경우
            dp[i+1] = dp[i];  // 일단 현재 위치에서 이전 위치를 이어 받음
            if (number <= 26 && prev != 0) {  // "10" ~ "26" 사이의 유효한 두 자리 수
                dp[i+1] = (dp[i+1] + dp[i-1]) % MOD;
            }
        }
    }

    cout << dp[s.length()];
    return 0;
}

다른점

1. 현재위치에서 0인 경우만 판별
2. 0인경우 dp[i+1] = dp[i-1] 을 통해 두자리 숫자 적용