재시민

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;
}