[백준] 1726 로봇

1726번: 로봇

 

www.acmicpc.net

풀이

까다로운 BFS문제이다. 로봇은 한번에 1~3 만큼 이동하거나 방향을 바꿀 수 있다. 이 말은 다른 방향일 때 같은 자리에 위치할 수 있다는 말이므로 중복을 제외하기 위한 visited배열을 생성할 때 3차원 배열로 생성해야해서 해결해야한다.

코드

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

struct robot {
    int x, y, dir, cnt;
};

int n, m;
int sx, sy, sdir, ex, ey, edir;
int map[101][101];
bool visited[101][101][5];
const int dx[] = { 0, 1, -1, 0, 0 }, dy[] = { 0, 0, 0, 1, -1 };

int bfs() {
    int ret = 0;
    queue<robot> q;
    q.push({ sx, sy, sdir, 0 });
    visited[sy][sx][sdir] = true;

    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int dir = q.front().dir;
        int cnt = q.front().cnt;
        // 목적지에 도착하고 방향까지 일치한 경우
        if (x == ex && y == ey && dir == edir) break;
        q.pop();

        // 1 ~ 3 이동하는 경우
        for (int i = 1; i <= 3; i++) {
            int nx = x + i * dx[dir];
            int ny = y + i * dy[dir];

            // 범위를 벗어나거나 길이 막힌 경우 반복문 종료
            if (nx < 1 || nx > n || ny < 1 || ny > m || map[ny][nx] == 1) break;
            // 방문 안한 경우
            if (!visited[ny][nx][dir]) {
                visited[ny][nx][dir] = true;
                q.push({ nx, ny, dir, cnt + 1 });
            }
        }

        // 방향을 바꾸는 경우
        for (int i = 1; i <= 4; i++) {
            // 기존의 방향과 똑같거나 이미 방문한 경우는 건너뛴다
            if (i == dir || visited[y][x][i] == true) continue;
            visited[y][x][i] = true; 
            // 180도 회전하는 경우
            if (dx[i] + dx[dir] == 0 && dy[i] + dy[dir] == 0) q.push({ x, y, i, cnt + 2 });
            // 90도 회전하는 경우
            else q.push({ x, y, i, cnt + 1 });
        }
    }
    return q.front().cnt;
}

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

    cin >> m >> n;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            cin >> map[i][j];
    cin >> sy >> sx >> sdir;
    cin >> ey >> ex >> edir;
    cout << bfs() << '\n';
    return 0;
}