백준 2174 - 로봇 시뮬레이션

문제링크

• 백준 2174

문제설명

• 가로 A(1~100), 세로 B(1~100) 크기의 땅이 있고, 이 땅 위에 로봇들이 N(1~100)개 있다.
• 로봇들의 초기 위치는 x좌표와 y좌표로 나타난다. x좌표는 왼쪽부터, y좌표는 아래쪽부터 순서가 매겨진다.
  • 행렬 좌표가 아니라 직각 좌표계를 의미
• 각 로봇은 좌표 정보와 방향 정보가 주어진다.
  • 동서남북 (EWST)
• 로봇들에게 명령을 내리는데 각각의 명령은 순차적으로 실행된다. 즉, 하나의 명령을 한 로봇에서 내렸으면 그 명령이 완수될 때까지 그 로봇과 다른 모든 로봇에게 다른 명령을 내릴 수 없다.
• 명령은 아래와 같다.
  • L: 로봇이 향하고 있는 방향을 기준으로 왼쪽으로 90도 회전한다.
  • R: 로봇이 향하고 있는 방향을 기준으로 오른쪽으로 90도 회전한다.
  • F: 로봇이 향하고 있는 방향을 기준으로 앞으로 한 칸 움직인다.
• 명령이 잘못된 경우는 두 가지가 있다.
  • Robot X crashes into the wall: X번 로봇이 벽에 충돌하는 경우이다. 즉, 주어진 땅의 밖으로 벗어나는 경우가 된다.
  • Robot X crashes into robot Y: X번 로봇이 움직이다가 Y번 로봇에 충돌하는 경우이다.
• 충돌이 발생하면 그대로 그 뒤에 명령은 무시하고, 충돌을 위와 같은 예시로 출력한다. 충돌하지 않고 모든 명령으르 수행하면 OK를 출력한다.

문제접근

• 직각좌표계로 로봇의 위치를 나타내고 있어서 헷갈리지 않게 주의해야 한다. 직각좌표계에서는 동쪽, 서쪽으로 이동시 x좌표가 변하고 북쪽, 남쪽으로 이동시 y좌표가 변한다.
• 2차원 배열 board[101][101] 은 문제에서 주어지는 땅의 모습을 나타내는 것이 아니라 단지 (x,y) 좌표에 몇번 로봇이 존재하는지를 표현하기 위한 용도이다.
  • board[x][y] 의 의미는 (x,y) 좌표에 존재하는 로봇의 번호
• 방향은 90도씩 회전하였을 때 계산이 쉽게 시작 방향을 정하고, 90도씩 회전한 방향대로 데이터를 정의하면 편하다.
  • 0번 방향을 동쪽으로 정했다면, 왼쪽으로 90도씩 회전하며 북쪽, 서쪽, 남쪽 순서대로 정의한다.
• 회전 명령의 경우 4바퀴를 돌면 원래 방향과 동일하므로 4를 나눈 나머지에 대해서만 회전을 한다.

구현

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

typedef struct _robot {
	int x, y, dir;
} Robot;

int A, B, N, M;
int board[101][101] = { 0, }; // board[x][y] 는 (x,y)에 위치한 로봇의 번호
// 동(0), 북(1), 서(2) 남(3)
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
vector<Robot> robotList(101); // robotList[idx] 는 idx 번 로봇의 좌표, 방향 정보

void cmdLeft(int robotNum, int cnt) {
	int realCnt = cnt % 4; // 0인 경우 방향 그대로
	for (int i = 0; i < realCnt; i++) {
		robotList[robotNum].dir = (robotList[robotNum].dir + 1) % 4;
	}
}

void cmdRight(int robotNum, int cnt) {
	int realCnt = cnt % 4;
	for (int i = 0; i < realCnt; i++) {
		robotList[robotNum].dir = robotList[robotNum].dir - 1;
		if (robotList[robotNum].dir == -1) robotList[robotNum].dir = 3;
	}
}

bool cmdFront(int robotNum, int cnt) {
	int curX = robotList[robotNum].x;
	int curY = robotList[robotNum].y;
	int dir = robotList[robotNum].dir;
	for (int i = 0; i < cnt; i++) {
		int nextX = curX + dx[dir];
		int nextY = curY + dy[dir];
		if (nextX < 1 || nextX > A || nextY < 1 || nextY > B) {
			printf("Robot %d crashes into the wall\n", robotNum);
			return false;
		}
		if (board[nextX][nextY] == 0) {
			board[nextX][nextY] = robotNum;
			board[curX][curY] = 0;
			curX = nextX;
			curY = nextY;
			robotList[robotNum].x = nextX;
			robotList[robotNum].y = nextY;
			continue;
		}
		int crashNum = board[nextX][nextY];
		printf("Robot %d crashes into robot %d\n", robotNum, crashNum);
		return false;
	}
	return true;
}

bool playCommand(int robotNum, char cmd, int cnt) {
	if (cmd == 'L') cmdLeft(robotNum, cnt);
	else if (cmd == 'R') cmdRight(robotNum, cnt);
	else if (cmd == 'F') {
		if (cmdFront(robotNum, cnt) == false) return false;
		else return true;
	}
	return true;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	scanf("%d %d %d %d", &A, &B, &N, &M);
	int x, y;
	char dir;
	Robot rbt;
	for (int i = 0; i < N; i++) {
		scanf("%d %d %c", &x, &y, &dir);
		rbt.x = x;
		rbt.y = y;
		if (dir == 'E') {
			rbt.dir = 0;
		}
		else if (dir == 'N') {
			rbt.dir = 1;
		}
		else if (dir == 'W') {
			rbt.dir = 2;
		}
		else if (dir == 'S') {
			rbt.dir = 3;
		}
		robotList[i + 1] = rbt;
		board[x][y] = i + 1;
	}

	int robotNum, cnt;
	char cmd;
	bool flag = true;
	for (int i = 0; i < M; i++) {
		scanf("%d %c %d", &robotNum, &cmd, &cnt);
		if (flag) flag = playCommand(robotNum, cmd, cnt);
	}
	if (flag) printf("OK\n");

	return 0;
}