[백준] 로봇 (1726번)

로봇 성공출처분류

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

128 MB

10408

2513

1662

24.528%

문제

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

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

출력

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

예제 입력 1 복사

5 6 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 4 2 3 2 4 1

예제 출력 1 복사

9

---

로봇을 최대한 빨리 목표지점까지 이동시키는 문제이다. 

bfs로 해결했다. 

시작점을 큐에 넣어 가능한 이동과 전환을 모두 하면서 큐에 넣어서 목적지에 도달할 때까지 큐를 돌린다. 

 

방향 다루기가 까다로웠다. 문제에서는 1, 2, 3, 4가 동, 서, 남, 북이라고 했는데, 이런 문제에서는 방향이 시계 또는 반시계 방향으로 연결돼있어야 방향 다루기가 편하기 때문에, 입력으로 들어온 방향 인덱스를 내가 원하는 대로 변경했다.

나는 0, 1, 2, 3이 남, 서, 북, 동으로 남쪽부터 시계방향으로 이동하도록 변경했다. 이렇게 해야 Turn Left나 Right 연산을 할 때 +1 또는 -1로 방향 전환이 쉬워진다. 

 

아무튼 방향을 설정한 후 bfs()를 실행한다.

bfs에서 시작점을 큐에 넣고 방문 여부를 기록한다.

visit함수는 x,y 좌표와 방향인 dir까지 기록한다. 좌표가 같아도 방향이 다르면 이동 횟수가 다르기 때문이다.

그렇게 큐의 각 지점마다 turn left, right, go 1, 2, 3를 실행해서 조건에 맞으면 큐에 다시 넣는다. 

 

코드를 보면 다 이해가 될 것이다. 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EB%A1%9C%EB%B4%87%20(1726%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int N, M, res = 987654321;
int sX, sY, sD; // start X,Y,Dir
int eX, eY, eD; // end X,Y,Dir
int dx[4] = { 1, 0, -1, 0 }; // 남, 서, 북, 동
int dy[4] = { 0, -1, 0, 1 };
int p[110][110];
int visit[110][110][5]; //(x,y)에 dir 방향으로 방문기록

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

void bfs()
{
	visit[sX][sY][sD] = 0;
	queue<robot> q;
	q.push({ sX,sY,sD });
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int dir = q.front().dir;
		q.pop();

		if (x == eX && y == eY && dir == eD) { //종료조건
			res = min(res, visit[x][y][dir]);
			continue;
		}

		int nD = (dir + 1) % 4; // Turn Right
		if (visit[x][y][nD] == -1) {
			q.push({ x,y,nD });
			visit[x][y][nD] = visit[x][y][dir] + 1;
		}

		nD = (dir + 3) % 4; // Turn Left
		if (visit[x][y][nD] == -1) {
			q.push({ x,y,nD });
			visit[x][y][nD] = visit[x][y][dir] + 1;
		}

		//Go 1, 2, 3
		for (int i = 1; i <= 3; i++) {
			int nx = x + i * dx[dir];
			int ny = y + i * dy[dir];
			if (nx<1 || ny<1 || nx>N || ny>M) continue;
			if(p[nx][ny]==1) break;
			if (visit[nx][ny][dir] == -1 || visit[nx][ny][dir] > visit[x][y][dir] + 1) {
				q.push({ nx,ny,dir });
				visit[nx][ny][dir] = visit[x][y][dir] + 1;
			}
		}
	}
}

int main()
{
	cin >> N >> M;
	for (int i = 1; i <= N; i++) 
		for (int j = 1; j <= M; j++) 
			cin >> p[i][j];
	cin >> sX >> sY >> sD >> eX >> eY >> eD;

	// 시작,끝점 동서남북 조정
	if (sD == 1) sD = 3;
	else if (sD == 2) sD = 1;
	else if (sD == 3) sD = 0;
	else sD = 2;

	if (eD == 1) eD = 3;
	else if (eD == 2) eD = 1;
	else if (eD == 3) eD = 0;
	else eD = 2;
	

	memset(visit, -1, sizeof(visit));

	bfs();

	cout << res;
}