BaekJoon 1726 로봇

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

소스결과 2036KB / 0 ms

출처 Baekjoon, Olympiad 지역본선 2005 고등부 3번

언어 C++ 17

분류 BFS

 

설명

공장의 로봇을 제어하는 명령어 2가지를 통해 지정한 시작 지점에서 목표 지점까지 이동하고 바라보게 하는 최소시간을 구하는 문제

 

최소시간, 이동 2가지 키워드에서 BFS를 사용해야 한다. DFS를 사용하게 되면 상당히 오랜 시간이 걸릴 뿐더러 최소 명령을 확인하는 문제이기에 모든 경우의 수를 확인해야 할 수도 있다.

유의사항

로봇은 현재 위치를 기준으로 동, 서, 남, 북 4방향을 쳐다 볼 수 있다. 따라서 같은 위치더라도 쳐다보는 경우에 따라 재방문 가능하다.

이동시 1 ~ 3칸을 움직일 수 있다. 4칸을 움직이는 경우 2번의 명령이 필요하다.

 

한 뱡향을 기준으로 - 90 / + 90 만 볼 수 있다. 한번에 180도씩 검사하는 것과 같다. 따라서 방향은 4방향이지만 결과적으로는 동서/ 남북 2방향으로 나누어서 확인하는경우로도 볼 수 있다.

이동 방법은 2가지 알고리즘을 썼었다. 먼저 사용했던 알고리즘은 현재 몇 칸 전진했는기 기억하는 방법을 사용했었다. 따라서 전진은 무조건 1칸씩만 전진하고 현재 전진 칸이 3이 되면 이동 칸을 0으로 초기화 한후 명령 카운트를 1 늘리는 방법을 사용했었다. 정답이 틀렸다고 나왔지만 디버그가 너무 힘들어 포기했다.

나중에 사용한 알고리즘은 1 ~ 3칸을 전부 경우의 수로 넣고 명령 카운트를 1 증가시키는 방법을 썼다. 1칸에서 벽이 존재할 경우 2,3칸 전진하는 경우를 진행시키지 않게 예외처리를 해야 했고, 디버그도 간단했다. ( 성공 ! )

 

알고리즘

1. 맵의 정보를 받아온다.

2. 현재 위치와 바라보는 방향을 Queue에 집어넣은후 BFS를 진행한다.

 2 - 1. 현재 바라보는 방향을 기준으로 -90 / + 90 방향을 확인 후 방문하지 않았으면 Queue에 집어넣는다.

 2 - 2. 현재 바라보는 방향으로  1 ~ 3칸 전진 가능한지 확인한다.

 2 - 3. 벽이 존재 한다면 전진 Loop를 취소한다.

 2 - 4. 맵을 벗어나지 않고, 전진 가능하다면 다음 위치를 Queue에 넣는다.

 2 - 5. Queue가 비거나 목표 지점, 목표 방향이 일치하면 종료한다.

3. 결과 count를 출력한다.

 

소스코드

#include <iostream>
#include <queue>

using namespace std;

struct Point {
	short x;
	short y;
	short look;
	int count;

	Point() : count(0) {};
	Point(short x, short y, short look, int count) : x(x), y(y), look(look), count(count) {}
	bool operator==(Point& p) { return x == p.x && y == p.y && look == p.look; }
};

const short MAX = 100;

bool board[MAX + 1][MAX + 1];
bool check[MAX + 1][MAX + 1][4]; // row col look
const short posX[4] = { 0, 0, 1, -1 };
const short posY[4] = { 1, -1, 0, 0 };

int main()
{
	short row, col;
	queue<Point> q;
	Point start, des;
	Point res;

	cin >> row >> col;

	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++)
			cin >> board[i][j];

	cin >> start.x >> start.y >> start.look;
	cin >> des.x >> des.y >> des.look;

	--start.x; --start.y; --start.look; --des.x; --des.y; --des.look;

	q.push(start);

	while (!q.empty())
	{
		Point cur = q.front();
		q.pop();

		if (check[cur.x][cur.y][cur.look])
			continue;

		//cout << cur.x << ' ' << cur.y << ' ' << cur.look << " / " << cur.count << endl; // For debug

		if (cur == des)
		{
			res.count = cur.count;
			break;
		}

		check[cur.x][cur.y][cur.look] = true;

		// N S <-> W,E 
		for (int i = 0; i < 2; i++)
		{
			short nextLook = !(cur.look / 2) * 2 + i;
			if (!check[cur.x][cur.y][nextLook])
				q.push(Point(cur.x, cur.y, nextLook, cur.count + 1));
		}

		for (int i = 1; i <= 3; i++)
		{
			short nextX = cur.x + posX[cur.look] * i; // go i block
			short nextY = cur.y + posY[cur.look] * i;

			if (board[nextX][nextY]) // check wall
				break;

			if (0 <= nextX && nextX < row && 0 <= nextY && nextY < col && !check[nextX][nextY][cur.look])
					q.push(Point(nextX, nextY, cur.look, cur.count + 1));
		}
	}

	cout << res.count;

	return 0;
}