[C/C++] 백준 - 로봇

https://www.acmicpc.net/problem/1726

1726번: 로봇

 

문제

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

• 명령 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로 주어진다. 출발지점에서 도착지점까지는 항상 이동이 가능하다.

출력

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

---

 

원하는 위치까지 가는 것 뿐만 아니라 원하는 방향까지 진행하는 최소 명령을 구하는 문제이다.

원하는 위치까지 가는 최소 명령을 구하는 문제는 메모이제이션을 이용하여 진행한다. 해당 문제도 비슷한 방법으로 원하는 위치에 원하는 방향까지 추가로 메모이제이션만 진행해주면 된다.

 

// 원하는 위치까지 이동할 때 구현하는 메모이제이션 방법
int cache[row][col];

// 원하는 위치에 방향까지 고려하는 메모이제이션 방법
int cache[row][col][dir];

 

위와 같이 진행해주면 된다.

 

그리고 해당 문제에서 주의해야 할 사항이 있는데,

만약 어느 위치에서 바라보는 궤도의 상태가 [현 위치 : 바라보는 방향 -> ] - [0] - [1] - [0] 일 경우 바로 다음 칸인(k=1)은 이동가능하며, 그 다음 칸(k=2)인 경우는 당연히 이동이 불가능하다. 그렇다면 k가 3인 경우는 어떻게 될까?

 

해당 문제에서 어떤 방식으로 해야할 지 명시해주지 않았지만, '1은 궤도가 없어 로봇이 갈 수 없는 지점이다.' 라는 문장으로 이동이 불가능하도록 처리해야 한다는 것을 알 수 있다. 

 

나머지 구현은 일반적인 BFS문제와 동일하게 처리해주면 된다.

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 123456789
#define endl '\n'

using namespace std;

typedef long long ll;
typedef struct info{
	int y;
	int x;
	int dir;
	int cnt;
}Info;

int M, N, cy, cx, py, px, cdir, pdir;
int board[100 + 1][100 + 1];
int cache[100 + 1][100 + 1][4 + 1];
const pair<int, int> dyx[] = {
	{0, 0}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}
};

void input(){
	cin >> M >> N;
	for(int i=1;i<=M;++i){
		for(int j=1;j<=N;++j){
			cin >> board[i][j];
		}
	}

	cin >> cy >> cx >> cdir;
	cin >> py >> px >> pdir;
}

bool isValid(int y, int x){
	return (1 <= y && y <= M && 1 <= x && x <= N);
}

vector<int> getTurnDir(int dir){
	vector<int> res;
	if(dir == 1 || dir == 2){
		res.push_back(3);
		res.push_back(4);
	} else {
		res.push_back(1);
		res.push_back(2);
	}
	return res;
}

bool isValidArea(int y, int x, int dir, int len){
	for(int i=1;i<=len;i++){
		int ny = y + dyx[dir].first * i;
		int nx = x + dyx[dir].second * i;

		if(board[ny][nx] == 1) return false;
	}
	return true;
}

int solution(){
	queue<Info> q;
	q.push({cy, cx, cdir, 0});
	memset(cache, INF, sizeof(cache));

	cache[cy][cx][cdir] = 0;
	while(!q.empty()){
		Info cur = q.front();
		q.pop();

		if(cur.y == py && cur.x == px && cur.dir == pdir) return cur.cnt;

		for(int k=1;k<=3;k++){
			int ny = cur.y + dyx[cur.dir].first * k;
			int nx = cur.x + dyx[cur.dir].second * k;

			if(!isValidArea(cur.y, cur.x, cur.dir, k)) continue;
			if(isValid(ny, nx) && !board[ny][nx] && cache[ny][nx][cur.dir] > cur.cnt + 1){
				cache[ny][nx][cur.dir] = cur.cnt + 1;
				q.push({ny, nx, cur.dir, cur.cnt+1});
			}
		}

		vector<int> dirs = getTurnDir(cur.dir);
		for(int i=0;i<dirs.size();i++){
			if(cache[cur.y][cur.x][dirs[i]] > cur.cnt + 1){
				cache[cur.y][cur.x][dirs[i]] = cur.cnt + 1;
				q.push({cur.y, cur.x, dirs[i], cur.cnt+1});
			}
		}
	}
	return -1;
}

int main() {
	fastio;
	input();
	cout << solution() << endl;
	
	return 0;
}