Problem : 로봇

유형 : BFS

문제 설명

많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다.

명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.

명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.

공장 내 궤도가 설치되어 있는 상태가 아래와 같이 0과 1로 이루어진 직사각형 모양으로 로봇에게 입력된다. 0은 궤도가 깔려 있어 로봇이 갈 수 있는 지점이고, 1은 궤도가 없어 로봇이 갈 수 없는 지점이다. 로봇이 (4, 2) 지점에서 남쪽을 향하고 있을 때, 이 로봇을 (2, 4) 지점에서 동쪽으로 향하도록 이동시키는 것은 아래와 같이 9번의 명령으로 가능하다.

로봇의 현재 위치와 바라보는 방향이 주어졌을 때, 로봇을 원하는 위치로 이동시키고, 원하는 방향으로 바라보도록 하는데 최소 몇 번의 명령이 필요한지 구하는 프로그램을 작성하시오.

예제 입력

첫째 줄에 공장 내 궤도 설치 상태를 나타내는 직사각형의 세로 길이 M과 가로 길이 N이 빈칸을 사이에 두고 주어진다. 이때 M과 N은 둘 다 100이하의 자연수이다. 이어 M줄에 걸쳐 한 줄에 N개씩 각 지점의 궤도 설치 상태를 나타내는 숫자 0 또는 1이 빈칸을 사이에 두고 주어진다. 다음 줄에는 로봇의 출발 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 마지막 줄에는 로봇의 도착 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 방향은 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4로 주어진다. 출발지점에서 도착지점까지는 항상 이동이 가능하다.

예제 출력

첫째 줄에 로봇을 도착 지점에 원하는 방향으로 이동시키는데 필요한 최소 명령 횟수를 출력한다.

해결 전략

방향의 정보도 같이 보관해야 하므로, 3차원 배열을 이용해야 한다. 큐 안에는 좌표, 방향, 명령의 개수를 넣어주었다.

회전 때문에 방향을 굳이 재 설정할 필요 없다. 북쪽이나 남쪽을 보고 있었으면, 명령어 카운트를 한번 더 증가 시키고, 해당 좌표에서 동쪽 , 서쪽을 바라보는 방향 두 개 다 큐에 넣으려고 시도하면 된다. 동쪽과 서쪽의 경우에도 북쪽, 서쪽을 바라보는 방향을 넣어주면 된다.

주의할 점

문제에서 시작 점은 0이 아니라 1부터 시작인 것에 주의한다.
한번의 BFS에서는 한번의 명령만 진행해야한다.
회전 하는 경우에도 방문을 확인해야 한다.

풀이

입력받고 초기설정을 한다.

시작점을 방문표시후, 큐에 넣는다.
도착점을 따로 기록해둔다.

BFS

방향까지 전부 일치할 경우에는 답이다.
직진 해본다.
회전해본다.

직진

가려는곳이 막혔거나, 범위를 이탈할경우 종료한다.
가려는곳이 방문한적이 있다면, 건너뛴다
- 2칸을 직진하지 못해도, 3칸을 직진했을때 최적의 경우가 나올 수 있다.

회전

현재 보고 있는 방향을 확인한다.
좌측, 우측 전부 돌 수 있으므로 한칸씩 좌 우측으로 돌려본다.
- 동쪽이나 서쪽 dir = {1, 2} 일때는 북, 남 {3, 4}
- 북쪽이나 남쪽 dir = {3, 4}일때는 서, 동 {1, 2} 을 시도해보면된다.

코드

#include <bits/stdc++.h>
using namespace std;

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

const int dx[] = { 0,0,0,1,-1 };
const int dy[] = { 0,1,-1,0,0 };

int board[103][103];
bool visit[103][103][5];

queue<Robot> q;

int n, m;
int end_x, end_y, end_dir;
int answer;

void go_straight(Robot &cur) {
    int nx, ny;
    for (int move_cnt = 1; move_cnt <= 3; ++move_cnt) {
        nx = cur.x + dx[cur.dir] * move_cnt;
        ny = cur.y + dy[cur.dir] * move_cnt;

        if (nx < 1 or nx > n or ny < 1 or ny > m)return;
        if (board[nx][ny] == 1)return;

        if (visit[nx][ny][cur.dir])continue;

        visit[nx][ny][cur.dir] = true;
        q.push({ nx,ny,cur.dir, cur.cnt + 1 });
    }
}

void rotate(Robot &cur) {

	if (cur.dir <= 2) {
		for (int n_dir = 3; n_dir <= 4; ++n_dir) {
            if (visit[cur.x][cur.y][n_dir])continue;
			visit[cur.x][cur.y][n_dir] = true;
			q.push({ cur.x, cur.y, n_dir, cur.cnt + 1 });
		}
	}
	else {
        for (int n_dir = 1; n_dir <= 2; ++n_dir) {
            if (visit[cur.x][cur.y][n_dir])continue;
            visit[cur.x][cur.y][n_dir] = true;
            q.push({ cur.x, cur.y, n_dir, cur.cnt + 1 });
        }
	}
}


int bfs() {
    while (!q.empty()) {
        Robot cur = q.front(); q.pop(); 

        if (cur.x == end_x && cur.y == end_y && cur.dir == end_dir) {            
            return cur.cnt;
        }

        go_straight(cur);
        rotate(cur);
    }
	return -1;
}

void init() {
    int s_x, s_y, s_d;
    cin >> s_x >> s_y >> s_d;

    visit[s_x][s_y][s_d] = true;
    q.push({ s_x, s_y, s_d, 0 });

    cin >> end_x >> end_y >> end_dir;
}

void solve() {
    cout << bfs() << "\n";
}

void input() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int ii = 1; ii <= m; ++ii) {
            cin >> board[i][ii];
        }
    }
    init();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    //freopen("input.txt", "r", stdin);

    input();
    solve();

    return 0;
}

피드백

재채점 후 오답 처리되었던 이유는, 하나의 단계 에서 2칸씩 돌리는 작업을 해서, 우선순위가 꼬였었다.
우선 순위 큐가 아니라, 단순히 큐를 이용한 BFS이기 때문에 하나의 단계 에서 명령어는 1번씩 증가하게 했어야 했다.

메모리 초과가 한번 발생했었는데, 회전 처리 부분에서 재 방문 여부를 확인하지 않고 push했기 때문이다.