코드트리 - 마법의 숲 탐색 [C++]

이 문제는 구현 문제이다.

 

나는 이 문제를 읽고 크게 두 파트로 나뉜다고 생각했다. 골렘이 이동하는 파트, 정령이 이동하는 파트 두 개로 분리하여 문제를 풀었다.

 

Golem이라는 구조체를 정의하여 골렘을 나타냈다. 골렘의 한 가운데 좌표를 저장하고, 출구 위치를 저장하는 식으로 구현했다.

 

골렘 이동을 구현하는 것은 사실 단순하다. 그림에 나와있는 대로 상대 좌표를 검사하고, 모두 비어있으면서 격자를 벗어나지 않으면 이동시키면 된다.

 

문제는 정령을 이동시키는 것인데, 여기서는 DFS(재귀), BFS 모두 가능하다. 그런데 한 가지 유의할 점은 두 방식 모두에서 반드시 이미 타고 간 골렘은 다시 탐색하지 않아야 한다는 것이다. 처음에 재귀로 문제를 풀었다가 이 부분을 놓치고 BFS로 바꿔 문제를 해결했는데, 재귀로 풀었더라도 visited만 체크했다면 아마 정답이 나왔을 것 같다.

 

이 문제에서 키 포인트는 어떻게 격자 밖을 나타내는지이다. 나는 이 부분에 대해 위로 3개의 행을 추가하여 골렘이 맨 처음 서있는 부분을 나타내서 문제를 풀었다.

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

#define R_MAX 70
#define C_MAX 70
#define GOLEM_MAX 1000

#define NORTH 0
#define EAST 1
#define SOUTH 2
#define WEST 3

struct Golem {
    int num;
    int y;
    int x;
    int exit;
};

Golem golems[GOLEM_MAX + 1];
int forest[R_MAX + 3 + 1][C_MAX + 1];
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
int R, C, K;

bool inRange(int y, int x) {
    return (1 <= y && y <= R + 3 && 1 <= x && x <= C);
}

bool isSouthMove(int y, int x) {
    if ((inRange(y + 2, x) && forest[y + 2][x] == 0) &&
        (inRange(y + 1, x - 1) && forest[y + 1][x - 1] == 0) &&
        (inRange(y + 1, x + 1) && forest[y + 1][x + 1] == 0)) {
            return true;
    }
    return false;
}

bool isWestMove(int y, int x) {
    if ((inRange(y, x - 2) && forest[y][x - 2] == 0) &&
        (inRange(y + 1, x - 1) && forest[y + 1][x - 1] == 0) &&
        (inRange(y - 1, x - 1) && forest[y - 1][x - 1] == 0) &&
        (inRange(y + 2, x - 1) && forest[y + 2][x - 1] == 0) &&
        (inRange(y + 1, x - 2) && forest[y + 1][x - 2] == 0)) {
            return true;
    }
    return false;
}

bool isEastMove(int y, int x) {
    if ((inRange(y, x + 2) && forest[y][x + 2] == 0) &&
        (inRange(y - 1, x + 1) && forest[y - 1][x + 1] == 0) &&
        (inRange(y + 1, x + 1) && forest[y + 1][x + 1] == 0) &&
        (inRange(y + 2, x + 1) && forest[y + 2][x + 1] == 0) &&
        (inRange(y + 1, x + 2) && forest[y + 1][x + 2] == 0)) {
            return true;
    }
    return false;
}

int rollCounterClock(int direction) {
    direction--;
    direction %= 4;
    if (direction < 0) {
        direction += 4;
    }
    return direction;
}

int rollClock(int direction) {
    direction++;
    direction %= 4;
    return direction;
}

void moveGolem(int num, int c, int d) {
    int y = 2;
    int x = c;
    int direction = d;

    while (true) {
        if (isSouthMove(y, x)) {
            y++;
            continue;
        }

        if (isWestMove(y, x)) {
            direction = rollCounterClock(direction);
            y++;
            x--;
            continue;
        }

        if (isEastMove(y, x)) {
            direction = rollClock(direction);
            y++;
            x++;
            continue;
        }
        break;
    }

    golems[num] = {num, y, x, direction};
    
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];

        forest[ny][nx] = num;
    }
    forest[y][x] = num;
}

bool isOutsideForest() {
    for (int y = 1; y <= 3; y++) {
        for (int x = 1; x <= C; x++) {
            if (forest[y][x] != 0) {
                return true;
            }
        }
    }

    return false;
}

void clearForest() {
    for (int y = 1; y <= R + 3; y++) {
        for (int x = 1; x <= C; x++) {
            forest[y][x] = 0;
        }
    }
}

int moveGhost(int golemNum) {
    vector<bool> visited(GOLEM_MAX + 1, false);
    visited[golemNum] = true;
    queue<int> q;
    q.push(golemNum);

    int answer = 0;

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

        Golem& presentGolem = golems[present];
        answer = max(answer, presentGolem.y - 2);
        int direction = presentGolem.exit;

        int exitY = presentGolem.y + dy[direction];
        int exitX = presentGolem.x + dx[direction];

        for (int i = 0; i < 4; i++) {
            int ny = exitY + dy[i];
            int nx = exitX + dx[i];
            
            if (inRange(ny, nx) && 
                forest[ny][nx] != 0 && 
                !visited[forest[ny][nx]]) {
                visited[forest[ny][nx]] = true;
                q.push(forest[ny][nx]);
            }
        }
    }
    return answer;
}

void print() {
    for (int y = 1; y <= R + 3; y++) {
        for (int x = 1; x <= C; x++) {
            cout << forest[y][x] << " ";
        }
        cout << '\n';
    }
    cout << '\n';
}

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

    cin >> R >> C >> K;

    int answer = 0;
    for (int i = 1; i <= K; i++) {
        int c, d;
        cin >> c >> d;

        moveGolem(i, c, d);
        //print();
        if (isOutsideForest()) {
            clearForest();
        } else {
            answer += moveGhost(i);
        }
    }

    cout << answer << '\n';

    return 0;
}