코드트리 - 마법의 숲 탐색

마법의 숲 탐색

Codetree Gold3 BFS Simulation
코드트리 마법의 숲 탐색

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 풀이

문제를 꼼꼼하게 읽고 풀이 하면 되는 문제였다.


남쪽, 서쪽, 동쪽이 막혀있는 형태여서 탐색할 때, 바운더리 체크를 안하기 위해 양 옆, 아래에 패딩을 줘 맵을 구성했다.
처음에 골렘이 진입하는 경로와 위치를 표시하기 위해 골렘의 길이인 3만큼 패딩을 맵의 북쪽에 추가해 줬다.
R += 3
C += 2

 

골렘에서 내리는 것은 골렘의 출구에서만 가능하기 때문에, 각 골렘을 표시할 때 편하게 탐색하기 위해 고유의 숫자(짝수)를 부여하고 출구는 골렘이 가지는 숫자 + 1 을 해줬다.

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct golem {
    int loc;
    int dir;
};

vector<vector<int>> fld;
int R, C, cnt=2;
int mv[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

void init() {
    cnt=2;
    for (int i=0; i<R-1; i++) {
        for (int j=1; j<C-1; j++) fld[i][j]=0;
    }
}

bool condition1(int x, int y) {
    return (fld[x+2][y] + fld[x+1][y-1] + fld[x+1][y+1]) == 0;
}
bool condition2(int x, int y) {
    return (fld[x-1][y-1] + fld[x][y-2] + fld[x+1][y-2] + fld[x+1][y-1] + fld[x+2][y-1]) == 0;
}
bool condition3(int x, int y) {
    return (fld[x-1][y+1] + fld[x][y+2] + fld[x+1][y+1] + fld[x+1][y+2] + fld[x+2][y+1]) == 0;
}

void setGolem(golem gol, int x) {
    int y = gol.loc;
    cnt += 2;
    fld[x-1][y] = cnt; fld[x][y] = cnt; fld[x][y-1] = cnt;
    fld[x][y+1] = cnt; fld[x+1][y] = cnt;

    // 출구는 홀수로 표기
    switch (gol.dir) {
        case 0: // 북
            fld[x-1][y] = cnt+1;
            break;
        case 1: // 동
            fld[x][y+1] = cnt+1;
            break;
        case 2: // 남
            fld[x+1][y] = cnt+1;
            break;
        case 3: // 서
            fld[x][y-1] = cnt+1;
            break;
    }
    return ;
}

int bfs(int x, int y) {
    int res = 0;
    queue<pair<int, int>> q;
    vector<vector<bool>> visit(R, vector<bool>(C, false));
    q.push(make_pair(x, y)); visit[x][y] = true;

    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second; q.pop();
        for (int i=0; i<4; i++) {
            int dx = x + mv[i][0];
            int dy = y + mv[i][1];
            if (fld[dx][dy] < 4 || visit[dx][dy]) continue;

            // 출구일 경우 골렘의 몸 어디로든 이동 가능
            if (fld[x][y]%2 == 1) {
                visit[dx][dy] = true;
                q.push(make_pair(dx, dy));
                res = max(res, dx);
            }
            else if (fld[x][y] == fld[dx][dy] || fld[x][y] + 1 == fld[dx][dy]) {
                visit[dx][dy] = true;
                q.push(make_pair(dx, dy));
                res = max(res, dx);
            }
        }
    }
    return res;
}

int simulation(golem gol) {
    // moving
    int x=1, y=gol.loc;
    while (true) {
        if (condition1(x, y)) {
            x += 1;
        }
        else if (condition2(x, y)) {
            x += 1;
            y += -1;
            gol.dir = gol.dir - 1 < 0 ? 3 : gol.dir-1;
        }
        else if (condition3(x, y)) {
            x += 1;
            y += 1;
            gol.dir = gol.dir + 1 > 3 ? 0 : gol.dir+1;
        }
        else break;
    }
    if (x < 4) {
        init();
        return 0;
    }
    gol.loc = y;
    setGolem(gol, x);

    return bfs(x, gol.loc) - 2;
}

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

    int K, ret=0;
    vector<golem> golems;

    cin >> R >> C >> K;
    R += 4; C += 2;
    fld.resize(R, vector<int>(C, 1));
    init();

    for (int i=0; i<K; i++) {
        golem gol;
        cin >> gol.loc >> gol.dir;
        golems.push_back(gol);
    }

    for (golem g : golems) {
        ret += simulation(g);
    }

    cout << ret << "\n";
    return 0;
}

후기

처음에 골렘을 움직일 때, x 와 y를 반대로 생각해 시간을 허비했고, 북쪽에 패딩을 추가할 때 골렘의 길이만큼 해줘야 하는데 2를 추가해 디버깅하는데 시간을 많이 잡아먹었다.