로봇 시뮬레이션

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	11999	2773	2173	22.742%

문제

가로 A(1≤A≤100), 세로 B(1≤B≤100) 크기의 땅이 있다.

이 땅 위에 로봇들이 N(1≤N≤100)개 있다.

로봇들의 초기 위치는 x좌표와 y좌표로 나타난다.

위의 그림에서 보듯 x좌표는 왼쪽부터, y좌표는 아래쪽부터 순서가 매겨진다.

또한 각 로봇은 맨 처음에 NWES 중 하나의 방향을 향해 서 있다.

초기에 서 있는 로봇들의 위치는 서로 다르다.

이러한 로봇들에 M(1≤M≤100)개의 명령을 내리려고 한다.

각각의 명령은 순차적으로 실행된다.

즉, 하나의 명령을 한 로봇에서 내렸으면, 그 명령이 완수될 때까지 그 로봇과 다른 모든 로봇에게 다른 명령을 내릴 수 없다.

각각의 로봇에 대해 수행하는 명령은 다음의 세 가지가 있다.

1. L: 로봇이 향하고 있는 방향을 기준으로 왼쪽으로 90도 회전한다.
2. R: 로봇이 향하고 있는 방향을 기준으로 오른쪽으로 90도 회전한다.
3. F: 로봇이 향하고 있는 방향을 기준으로 앞으로 한 칸 움직인다.

간혹 로봇들에게 내리는 명령이 잘못될 수도 있기 때문에, 당신은 로봇들에게 명령을 내리기 전에 한 번 시뮬레이션을 해 보면서 안전성을 검증하려 한다.

이를 도와주는 프로그램을 작성하시오.

잘못된 명령에는 다음의 두 가지가 있을 수 있다.

1. Robot X crashes into the wall: X번 로봇이 벽에 충돌하는 경우이다. 즉, 주어진 땅의 밖으로 벗어나는 경우가 된다.

2. Robot X crashes into robot Y: X번 로봇이 움직이다가 Y번 로봇에 충돌하는 경우이다.

입력

첫째 줄에 두 정수 A, B가 주어진다. 다음 줄에는 두 정수 N, M이 주어진다.

다음 N개의 줄에는 각 로봇의 초기 위치(x, y좌표 순) 및 방향이 주어진다.

다음 M개의 줄에는 각 명령이 명령을 내리는 순서대로 주어진다.

각각의 명령은 명령을 내리는 로봇, 명령의 종류(위에 나와 있는), 명령의 반복 회수로 나타낸다.

각 명령의 반복 회수는 1이상 100이하이다.

출력

첫째 줄에 시뮬레이션 결과를 출력한다.

문제가 없는 경우에는 OK를, 그 외의 경우에는 위의 형식대로 출력을 한다.

만약 충돌이 여러 번 발생하는 경우에는 가장 먼저 발생하는 충돌을 출력하면 된다.

예제 입력 1

5 4
2 2
1 1 E
5 4 W
1 F 7
2 F 7

예제 출력 1

Robot 1 crashes into the wall

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2005 A번

• 잘못된 데이터를 찾은 사람: Apple_Cplus

알고리즘 분류

• 구현
• 시뮬레이션

---

예제 입력 A 

1 1
1 1
1 1 W
1 F 1

예제 출력 A 

Robot 1 crashes into the wall

예제 입력 B 

3 3
1 9
2 2 W
1 F 1
1 L 1
1 F 1
1 L 1
1 F 2
1 L 5
1 F 2
1 R 3
1 F 2

예제 출력 B 

OK

예제 입력 C 

5 5
9 1
3 1 W
3 2 N
3 4 S
3 5 E
1 3 S
2 3 N
4 3 E
5 4 W
3 3 W
9 F 4

예제 출력 C 

Robot 9 crashes into robot 6

예제 입력 D 

5 5
9 1
3 1 W
3 2 N
3 4 S
3 5 E
1 3 S
2 3 N
4 3 E
5 4 W
3 3 S
9 F 4

예제 출력 D 

Robot 9 crashes into robot 2

예제 입력 E 

100 100
100 100
42 58 S
49 6 N
40 70 W
8 97 N
57 65 S
85 68 E
75 45 E
17 59 N
43 40 W
2 84 W
14 96 E
12 7 W
10 26 N
48 41 N
82 73 N
53 39 N
49 87 W
96 43 W
4 11 E
63 72 W
45 58 N
23 20 W
69 77 W
15 49 N
61 8 E
47 90 E
88 11 W
60 26 S
89 25 E
11 9 N
62 61 E
62 60 N
93 32 N
59 30 E
38 64 N
14 46 W
74 2 N
47 40 N
72 87 S
58 17 E
97 89 E
68 6 W
82 20 W
73 85 E
61 75 N
42 9 N
45 96 E
84 94 N
26 36 S
44 63 W
35 52 E
97 67 E
98 22 W
2 16 W
88 36 S
86 92 W
67 39 W
4 82 N
48 61 S
23 7 W
41 4 N
98 38 E
65 36 N
48 16 N
61 11 N
52 30 S
16 46 E
54 75 N
42 63 W
37 79 W
29 50 N
81 58 S
42 32 S
60 75 E
6 56 W
82 9 W
23 96 N
95 26 E
62 18 S
54 1 N
87 89 W
26 79 N
20 20 N
91 56 W
6 74 W
57 9 N
25 12 N
39 58 S
57 2 W
33 21 N
69 59 N
10 23 W
26 7 E
25 76 S
74 12 W
87 40 E
7 97 W
50 81 S
78 63 N
51 96 N
34 F 12
77 F 4
75 F 3
5 L 27
17 F 8
77 R 2
87 F 30
8 F 5
95 F 13
17 L 12
70 R 2
45 F 15
44 R 27
76 L 59
91 F 9
89 L 2
67 F 27
76 F 7
73 F 10
73 F 8
15 R 27
47 F 5
49 L 16
82 R 2
15 F 10
56 F 2
40 F 26
37 L 26
7 R 2
19 L 2
42 F 1
76 F 2
37 L 3
73 R 14
5 R 2
67 F 25
15 R 2
64 F 1
61 L 2
16 L 21
89 R 2
37 F 12
80 R 29
96 R 11
90 F 20
44 R 3
46 F 3
56 L 2
36 L 2
95 L 16
45 R 2
75 F 2
22 R 27
71 F 6
22 L 7
27 F 3
90 F 5
10 F 1
88 R 2
24 L 29
91 R 14
21 L 22
91 F 9
46 L 2
82 R 3
50 R 2
76 R 11
47 L 2
96 L 4
34 F 9
72 F 27
35 L 28
96 F 17
21 F 16
55 F 22
89 L 17
60 R 26
7 F 22
23 R 20
16 R 31
62 L 12
60 L 2
8 L 1
29 R 10
58 F 18
36 F 8
55 F 7
4 F 2
69 L 23
76 L 2
31 F 21
29 F 3
14 L 2
94 R 2
34 L 27
21 L 2
78 L 7
4 R 2
9 F 29
78 F 16

예제 출력 E 

OK

예제 입력 F 

79 61
100 100
69 58 S
8 37 N
30 10 E
75 23 S
9 58 N
35 46 N
6 50 S
36 22 W
5 28 S
42 32 E
72 41 N
73 8 W
65 46 S
11 23 E
3 42 S
35 17 S
36 30 N
48 17 S
33 44 W
7 22 W
62 54 E
17 43 S
37 17 E
74 7 S
44 15 N
65 13 N
41 17 S
15 21 N
51 46 E
50 10 E
29 30 W
40 60 W
27 24 S
10 13 E
21 45 S
36 54 E
54 41 W
39 6 S
45 47 W
63 34 S
12 31 S
56 43 S
51 54 W
42 7 N
72 45 W
63 24 W
50 38 S
53 21 N
55 36 S
54 60 S
71 44 N
44 55 N
68 48 W
2 47 W
12 37 N
17 57 E
51 61 N
55 8 N
18 21 N
78 36 E
61 27 W
7 27 N
37 9 S
13 29 W
49 12 W
67 61 S
78 3 S
58 31 S
51 4 W
77 29 W
42 22 S
45 43 S
9 6 W
63 11 S
31 21 N
78 42 E
39 13 S
16 2 N
56 58 S
68 25 W
72 6 W
57 51 W
40 42 E
31 7 E
69 11 S
60 22 N
56 44 S
59 13 W
3 53 N
54 44 N
70 51 N
58 50 N
32 32 W
17 16 E
63 13 E
37 51 N
22 29 E
27 60 S
2 18 E
20 59 S
71 F 15
25 R 8
8 F 17
26 R 30
72 F 20
22 R 2
92 R 31
12 F 19
35 L 2
72 F 5
55 F 19
37 F 14
91 L 18
8 L 31
91 F 5
92 L 2
40 L 1
90 F 1
5 F 8
63 R 22
67 R 5
70 F 21
84 F 1
90 L 2
80 L 2
74 F 19
52 F 18
55 L 18
50 L 2
60 F 17
26 F 4
51 F 23
65 F 9
13 F 7
5 R 2
61 R 2
30 F 8
24 F 19
6 L 2
51 F 9
19 R 25
58 F 22
62 R 5
93 L 5
58 R 2
69 L 2
84 L 2
55 L 31
91 F 6
69 L 29
62 F 6
67 F 3
64 R 2
1 R 30
90 F 9
8 L 2
15 R 2
46 R 27
45 F 11
86 F 10
34 R 2
66 F 19
63 F 4
94 L 19
25 F 12
30 L 2
86 L 27
34 F 1
31 F 9
70 L 31
72 L 30
10 F 2
88 L 2
13 F 10
80 F 14
19 L 25
77 R 2
72 F 13
44 R 31
25 F 8
27 R 1
19 F 21
88 F 19
79 F 5
49 F 11
63 L 22
91 L 30
30 F 19
40 R 2
18 L 2
88 L 2
28 R 3
27 R 2
82 F 1
14 F 1
100 R 2
46 F 5
2 R 2
70 L 25
23 F 16

예제 출력 F 

Robot 71 crashes into robot 44

예제 입력 G 

20 90
73 4
5 88 N
10 9 N
4 28 W
10 36 E
4 88 W
4 68 S
3 2 S
12 44 E
4 84 W
14 48 E
1 7 S
12 84 S
8 2 N
18 44 S
2 80 S
18 15 N
12 58 W
7 34 S
19 64 E
9 20 W
18 81 S
4 30 S
10 21 W
14 18 N
11 90 N
18 17 S
14 69 W
10 16 N
12 81 W
17 21 E
15 77 S
8 25 S
19 47 S
1 57 E
16 21 E
13 22 S
9 68 W
16 3 S
12 37 E
19 73 S
13 30 E
14 24 E
11 65 E
13 39 W
9 36 E
13 27 S
13 67 W
10 48 E
15 75 E
2 1 W
12 75 E
3 45 S
9 58 E
8 9 S
4 32 E
11 54 E
13 75 S
11 75 N
7 81 E
1 59 S
10 42 E
12 31 S
4 87 N
20 46 E
5 29 N
16 20 S
13 84 W
9 78 N
5 63 S
10 90 W
6 46 W
14 57 W
11 43 S
15 F 10
56 R 2
34 F 16
39 F 10

예제 출력 G 

Robot 34 crashes into robot 72

예제 입력 H 

42 27
19 1
19 25 E
24 20 S
14 3 E
41 3 N
3 18 W
30 2 E
8 24 N
35 13 E
20 7 S
32 23 E
29 1 W
1 14 E
39 7 E
1 12 E
10 4 E
19 18 W
28 6 E
29 21 W
7 13 W
12 F 1

예제 출력 H 

OK

---

https://nordic.icpc.io/ncpc2005/ <- 출처

---

입력 확인 코드

#include <iostream>
#include <list>

using namespace std;

constexpr auto MAX = 101;


// 0 빈공간 
// 1 ~ 100 로봇 
int map[MAX][MAX];

// A : 가로의 길이, B : 세로의 길이
int A, B, N, M;

// 로봇의 방향을 저장
char dir[MAX];

// 명령어 구조체
struct Command
{
	int robotNumber; // 로봇의 번호
	char orderDir; // 로봇이 움직일 방향
	int repetition; // 반복 횟수
} CS[100];

// 명령들을 저장할 리스트를 생성
list<Command> CommandList;
list<Command>::iterator iterCommandList;

bool debug = true;

// 디버그 확인용 함수
void DebugMap()
{
	cout << "\n";
	// 맵 출력
	for (int i = 1; i <= A; i++)
	{
		for (int j = 1; j <= B; j++)
		{
			cout << map[i][j] << " ";
		}
		cout << "\n";
	}

	// 명령 확인
	for (iterCommandList = CommandList.begin(); iterCommandList != CommandList.end(); iterCommandList++)
	{
		cout << "\n" << "robotNumber : " << iterCommandList->robotNumber << " orderDir : " 
			<< iterCommandList->orderDir << "  repetition : " << iterCommandList->repetition;
	}

}

// 초기화를 위한 함수입니다.
void Initialization()
{
	// 맵을 전부 빈공간으로 만들어줍니다.
	for (int i = 1; i < MAX; i++)
	{
		for (int j = 1; j < MAX; j++)
		{
			map[i][j] = 0;
		}
	}
}

// 입력을 받는 함수 입니다.
void ReceiveInput()
{

	cin >> A >> B >> N >> M;

	int Number = 1;
	int tempOne, tempTwo;
	char tempChar;

	// 로봇의 초기 좌표와 방향을 입력받습니다.
	while (N > 0)
	{
		cin >> tempOne >> tempTwo >> tempChar;
		map[tempOne][tempTwo] = Number;
		dir[Number] = tempChar;
		Number++;
		N--;
	}

	Number = 0;

	while (M > 0)
	{
		cin >> tempOne >> tempChar >> tempTwo;
		CS[Number].robotNumber = tempOne;
		CS[Number].orderDir = tempChar;
		CS[Number].repetition = tempTwo;
		CommandList.push_back(CS[Number]);
		Number++;
		M--;
	}

}

int main()
{
	Initialization();

	ReceiveInput();

	if (debug) { DebugMap(); }

	return 0;
}

---

문제의 맵은 왼쪽 하단부터 1,1로 시작한다.

로봇이 방향을 전환할 때 주의가 필요할 것 같다.

E : 1,0 N : 0,1 W : -1 , 0 S : 0, -1

로봇의 위치 및 방향 정의

코드를 작성하다 보니 로봇의 현재 위치를 저장해둘 공간이 필요했다. (명령을 할때마다 탐색할 수 는 없으니…)

새로운 구조체를 만들어 x, y를 저장하고 char dir[MAX];과 합쳐주었다.

RP[로봇의 번호]로 로봇들을 따로 관리한다.

로봇의 방향을 정의하는 부분에서 int 2차원 배열로 접근

-> char 값을 계속 변경

-> Int로 방향을 정의하는 것으로 구조체 변경 (입력을 받을 때 한번만 변환)

로봇의 명령을 저장하고 관리하는 부분

각 명령은 struct 구조에 로봇의 번호/명령/반복하는 횟수를 저장

List<struct> 구조로 명령들을 저장하고 관리한다.

로봇의 명령을 처리하는 부분

명령어 리스트를 순회하면서 먼저 입력된 명령들을 처리합니다.

L / R 이 입력되면 명령을 받은 로봇의 구조체의 방향을 바꾸어주고

F가 입력되면 해당 명령을 받은 로봇의 구조체의 방향의 값으로 로봇을 움직이고 맵을 수정해줍니다.

만약 로봇이 이동하려는 위치가 맵의 범위를 벗어나거나 다른 로봇이 있을 경우 결과를 출력하고 Return 합니다.

마지막으로 모든 명령을 다 수행했다면 OK 값을 출력하고 프로그램을 종료합니다.

통과된 코드

#include <iostream>
#include <list>

using namespace std;
constexpr auto MAX = 101;

// 0 빈공간 
// 1 ~ 100 로봇 
int map[MAX][MAX];

// A : 가로의 길이, B : 세로의 길이
int A, B, N, M;

// 명령어 구조체
struct Command
{
	int robotNumber; // 로봇의 번호
	char orderDir; // 로봇이 움직일 방향
	int repetition; // 반복 횟수
} CS[100];

// 명령들을 저장할 리스트를 생성
list<Command> CommandList;
list<Command>::iterator iterCommandList;

// 로봇의 위치와 방향을 저장
struct robotPos
{
	int x, y;
	int dir;

} RP[100];

// E N W S
int dirXY[4][2] = { {1, 0}, {0,1}, {-1,0}, {0,-1} };

bool debug = false;

// 디버그 확인용 함수
void DebugMap()
{
	cout << "\n";
	// 맵 출력
	for (int i = 1; i < MAX; i++)
	{
		for (int j = 1; j < MAX; j++)
		{
			cout << map[i][j] << " ";
		}
		cout << "\n";
	}

	// 명령 확인
	for (iterCommandList = CommandList.begin(); iterCommandList != CommandList.end(); iterCommandList++)
	{
		cout << "\n" << "robotNumber : " << iterCommandList->robotNumber << " orderDir : " 
			<< iterCommandList->orderDir << "  repetition : " << iterCommandList->repetition;
	}

}

// 방향을 정수로 변환해주는 함수
int ChangeDirCharToInt(char ch)
{
	int temp = 0;
	switch (ch)
	{
		case 'E':
			temp = 0;
			break;
		case 'N':
			temp = 1;
			break;
		case 'W':
			temp = 2;
			break;
		case 'S':
			temp = 3;
			break;
	}

	return temp;
}

// 초기화를 위한 함수입니다.
void Initialization()
{
	// 맵을 전부 빈공간으로 만들어줍니다.
	for (int i = 1; i < MAX; i++)
	{
		for (int j = 1; j < MAX; j++)
		{
			map[i][j] = 0;
		}
	}
}

// 입력을 받는 함수 입니다.
void ReceiveInput()
{

	cin >> A >> B >> N >> M;

	int Number = 1;
	int tempOne, tempTwo;
	char tempChar;

	// 로봇의 초기 좌표와 방향을 입력 받습니다.
	while (N > 0)
	{
		cin >> tempOne >> tempTwo >> tempChar;
		map[tempOne][tempTwo] = Number;
		RP[Number - 1].x = tempOne;
		RP[Number - 1].y = tempTwo;
		RP[Number - 1].dir = ChangeDirCharToInt(tempChar);
		Number++;
		N--;
	}

	Number = 0;

	// 명령들을 구조체 리스트에 넣습니다.
	while (M > 0)
	{
		cin >> tempOne >> tempChar >> tempTwo;
		CS[Number].robotNumber = tempOne;
		CS[Number].orderDir = tempChar;
		CS[Number].repetition = tempTwo;
		CommandList.push_back(CS[Number]);
		Number++;
		M--;
	}

}

// 시뮬레이션 시작
void SimulationStart()
{
	int cnt, number, tempX, tempY, tempdir;

	// 명령 리스트를 순회
	for (iterCommandList = CommandList.begin(); iterCommandList != CommandList.end(); iterCommandList++)
	{
		cnt = iterCommandList->repetition;
		number = iterCommandList->robotNumber - 1;
		tempX = RP[number].x;
		tempY = RP[number].y;
		tempdir = RP[number].dir;

		while (cnt > 0)
		{
			switch (iterCommandList->orderDir)
			{
				case 'L': 	// L: 로봇이 향하고 있는 방향을 기준으로 왼쪽으로 90도 회전한다.
					RP[number].dir ++;
					if (RP[number].dir >= 4)
					{
						RP[number].dir = 0;
					}
					break;

				case 'R':	// R: 로봇이 향하고 있는 방향을 기준으로 오른쪽으로 90도 회전한다.
					RP[number].dir--;
					if (RP[number].dir <= -1)
					{
						RP[number].dir = 3;
					}
					break;

				case 'F':	// F : 로봇이 향하고 있는 방향을 기준으로 앞으로 한 칸 움직인다.
					tempdir = RP[number].dir;
					map[tempX][tempY] = 0;
					tempX += dirXY[tempdir][0];
					tempY += dirXY[tempdir][1];

					// 로봇이 벽에 부딪힐 경우 또는 범위를 벗어날 경우 결과 출력
					if (tempX <= 0 || tempY <= 0 || tempX > A || tempY > B)
					{
						cout << "Robot "<< number + 1 <<" crashes into the wall";
						return;
					}
					else if (map[tempX][tempY] > 0) // 로봇끼리 부딪힐 경우
					{
						cout << "Robot " << number + 1 << " crashes into robot "<< map[tempX][tempY];
						return;
					}
					else // 빈공간일경우 로봇의 위치를 바꾸어주고 맵에 로봇을 표시
					{
						RP[number].x = tempX;
						RP[number].y = tempY;
						map[tempX][tempY] = number + 1;
					}

					break;

				default:
					cout << "이 값이 나오면 안됨";
					break;
			}

			cnt--;
		}
	}

	cout << "OK";

}

int main()
{
	Initialization();
	ReceiveInput();
	SimulationStart();
	if (debug) { DebugMap(); }

	return 0;
}

1차적으로 다른 문제들과 X, Y의 좌표가 다른 방식이라서 약간의 혼동이 있었고

출력 값 중간에 스페이스 하나가 있는 것을 나중에 발견해서 계속 통과되지 못한 문제

X, Y 값의 변화를 제외하면 로직은 크게 어렵지 않은 문제같다.