[ 백준 2194 ] 유닛 이동시키기 (C++) - BFS

---

🔗 문제 링크

2194번: 유닛 이동시키기

---

💡 문제 풀이 및 해석

1. "시작점 -> 도착점"의 최소거리를 구해야 한다는 점에서 BFS로 풀어야 한다 생각했다.
2. 단, queue에 들어간 모든 원소가 빠져나가는 것을 1회로 지정해야 한다.
3. 이 때, 움직이는 Unit은 동서남북으로 한칸씩 움직일 수 있는데, 장애물이 설치된 구역이거나 맵의 바깥쪽으로는 이동할 수 없다.
4. 동서남북으로 이동시에 방향에 맞게 유닛이 이동하는 변이 금지구역에 들어가거나 꼭지점의 위치가 맵 바깥쪽에 있는지만 확인해주면 된다.
5. 상대적으로 꼭지점을 검사하여 맵 바깥쪽에 위치한지 검사하는 것이 간단하므로 아래와같은 순서로 진행한다.
   6-1. 맵 안쪽으로 이동한지 검사
   6-2. 금지구역으로 이동한지 검사
6. 만약 도착점에 도착할 수 없다면, -1을 반환해주면 된다.

---

⭐️ 정답 코드 및 설명

// bfs 코드 중간 출력 주석을 풀면 진행 경로를 알 수 있습니다.
#include<iostream>
#include<queue>
#define endl "\n"
using namespace std;

int N, M, Y, X, K;
int sx, sy, ex, ey;
int next_x[] = { 1,-1,0,0 };
int next_y[] = { 0,0,1,-1 };
bool visit[501][501];
bool prohibitArea[501][501];

void init() {
    cin >> N >> M >> Y >> X >> K;
    for (int i = 0; i < K; i++) {
        int prohibit_y, prohibit_x;
        cin >> prohibit_y >> prohibit_x;
        prohibitArea[prohibit_y][prohibit_x] = true; // 금지구역 설정
    }
    cin >> sy >> sx >> ey >> ex;
}

bool move(int nx, int ny, int dir) {
    switch (dir)
    {
    case 0: // 동쪽 모서리 검사
        for (int i = ny; i < ny + Y; i++) {
            if (prohibitArea[i][nx + X - 1]) return false;
        }
        return true;
        break;
    case 1: // 서쪽 모서리 검사
        for (int i = ny; i < ny + Y; i++) {
            if (prohibitArea[i][nx]) return false;
        }
        return true;
        break;
    case 2: // 남쪽 모서리 검사
        for (int i = nx; i < nx + X; i++) {
            if (prohibitArea[ny + Y -1][i]) return false;
        }
        return true;
        break;
    case 3: // 북쪽 모서리 검사
        for (int i = nx; i < nx + X; i++) {
            if (prohibitArea[ny][i]) return false;
        }
        return true;
        break;
    default:
        return false;
        break;
    }
}

int bfs(int x, int y) {

    queue<pair<int, int>> q; // x,y
    q.push({ x,y });
    visit[y][x] = true;

    int answer = 0;
    while (!q.empty()) {
        int q_size = q.size(); // 현재 상황에서 1번 이동할 크기 지정
        while (q_size--) {
            int cur_x = q.front().first, cur_y = q.front().second;
            //cout << cur_y << ", " << cur_x << endl;
            q.pop();
            for (int i = 0; i < 4; i++) { // 동서남북
                int nx = cur_x + next_x[i];
                int ny = cur_y + next_y[i];
                if (nx > 0 && ny > 0 && nx + X - 1 <= M && ny + Y - 1 <= N && !visit[ny][nx]) {
                    if (move(nx, ny, i)) {
                        q.push({ nx,ny });
                        visit[ny][nx] = true;
                    }
                }
            }
        }
        //cout << "---------------------------\n";
        answer++;
        if (visit[ey][ex]) break;
    }
    if (!visit[ey][ex]) return -1;
    return answer;
}

int main() {

    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
    init();
    cout << bfs(sx, sy);

    return 0;
}

---

🤔 문제 후기

처음에는 유닛의 모든 모서리를 검사해야 되나 생각했다가 이동하는 변만 검사하면 된다는 생각에 생각보다 쉽게 풀었다. 그리고 아래와 같은 이상한 실수를 하여서 시간을 생각보다 많이 잡아먹었다. 이 점 말고는 딱히 어렵거나 이슈가 있던 문제는 아니였다.

for (int i = ny; i < ny + Y; ny++) {
    if (prohibitArea[i][nx + X - 1]) return false;
}