[구현] (백준 3190) 뱀

알고리즘

구현

 

 

[문제 본문]

문제

 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

• 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
• 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
• 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

입력

첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)

다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.

다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)

다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데,  정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.

출력

첫째 줄에 게임이 몇 초에 끝나는지 출력한다.

제한

예제 입력 1

6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

예제 출력 1

9

예제 입력 2

10
4
1 2
1 3
1 4
1 5
4
8 D
10 D
11 D
13 L

예제 출력 2

21

예제 입력 3

10
5
1 5
1 3
1 2
1 6
1 7
4
8 D
10 D
11 D
13 L

예제 출력 3

13

힌트

W3sicHJvYmxlbV9pZCI6IjMxOTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjNDAiLCJkZXNjcmlwdGlvbiI6IjxwPiZuYnNwOyYjMzk7RHVtbXkmIzM5OyBcdWI3N2NcdWIyOTQgXHViM2M0XHVjMmE0XHVhYzhjXHVjNzg0XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YWM4Y1x1Yzc4NFx1YzVkMFx1YjI5NCBcdWJjNDBcdWM3NzQgXHViMDk4XHVjNjQwXHVjMTFjIFx1YWUzMFx1YzViNFx1YjJlNFx1YjJjOFx1YjI5NFx1YjM3MCwgXHVjMGFjXHVhY2ZjXHViOTdjIFx1YmEzOVx1YzczY1x1YmE3NCBcdWJjNDAgXHVhZTM4XHVjNzc0XHVhYzAwIFx1YjI5OFx1YzViNFx1YjA5Y1x1YjJlNC4gXHViYzQwXHVjNzc0IFx1Yzc3NFx1YjlhY1x1YzgwMFx1YjlhYyBcdWFlMzBcdWM1YjRcdWIyZTRcdWIyYzhcdWIyZTRcdWFjMDAgXHViY2JkIFx1YjYxMFx1YjI5NCBcdWM3OTBcdWFlMzBcdWM3OTBcdWMyZTBcdWM3NTggXHViYWI4XHVhY2ZjIFx1YmQ4MFx1YjUyYVx1ZDc4OFx1YmE3NCBcdWFjOGNcdWM3ODRcdWM3NzQgXHViMDVkXHViMDljXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjOGNcdWM3ODRcdWM3NDAgTnhOIFx1YzgxNVx1YzBhY1x1YWMwMSZuYnNwO1x1YmNmNFx1YjRkY1x1YzcwNFx1YzVkMFx1YzExYyBcdWM5YzRcdWQ1ODlcdWI0MThcdWFjZTAsIFx1YmE4N1x1YmE4NyBcdWNlNzhcdWM1ZDBcdWIyOTQmbmJzcDtcdWMwYWNcdWFjZmNcdWFjMDAgXHViMTkzXHVjNWVjXHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViY2Y0XHViNGRjXHVjNzU4IFx1YzBjMVx1ZDU1OFx1Yzg4Y1x1YzZiMCBcdWIwNWRcdWM1ZDAgXHViY2JkXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVhYzhjXHVjNzg0XHVjNzc0IFx1YzJkY1x1Yzc5MVx1ZDU2MFx1YjU0YyBcdWJjNDBcdWM3NDAgXHViOWU4XHVjNzA0IFx1YjllOFx1Yzg4Y1x1Y2UyMVx1YzVkMCBcdWM3MDRcdWNlNThcdWQ1NThcdWFjZTAgXHViYzQwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAxIFx1Yzc3NFx1YjJlNC4gXHViYzQwXHVjNzQwIFx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NDQgXHVkNWE1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjNDBcdWM3NDAgXHViOWU0IFx1Y2QwOFx1YjljOFx1YjJlNCBcdWM3NzRcdWIzZDlcdWM3NDQgXHVkNTU4XHViMjk0XHViMzcwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YjUzMFx1Yjk3OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWJhM2NcdWM4MDAgXHViYzQwXHVjNzQwIFx1YmFiOFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWIyOThcdWI4MjQmbmJzcDtcdWJhMzhcdWI5YWNcdWI5N2MmbmJzcDtcdWIyZTRcdWM3NGNcdWNlNzhcdWM1ZDAgXHVjNzA0XHVjZTU4XHVjMmRjXHVkMGE4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI5Y2NcdWM1N2QgXHVjNzc0XHViM2Q5XHVkNTVjIFx1Y2U3OFx1YzVkMCBcdWMwYWNcdWFjZmNcdWFjMDAgXHVjNzg4XHViMmU0XHViYTc0LCBcdWFkZjggXHVjZTc4XHVjNWQwIFx1Yzc4OFx1YjM1OCBcdWMwYWNcdWFjZmNcdWFjMDAgXHVjNWM2XHVjNWI0XHVjOWMwXHVhY2UwIFx1YWYyY1x1YjlhY1x1YjI5NCBcdWM2YzBcdWM5YzFcdWM3NzRcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI5Y2NcdWM1N2QgXHVjNzc0XHViM2Q5XHVkNTVjIFx1Y2U3OFx1YzVkMCBcdWMwYWNcdWFjZmNcdWFjMDAgXHVjNWM2XHViMmU0XHViYTc0LCBcdWJhYjhcdWFlMzhcdWM3NzRcdWI5N2MgXHVjOTA0XHVjNWVjXHVjMTFjIFx1YWYyY1x1YjlhY1x1YWMwMCBcdWM3MDRcdWNlNThcdWQ1NWMgXHVjZTc4XHVjNzQ0IFx1YmU0NFx1YzZjY1x1YzkwMFx1YjJlNC4gXHVjOTg5LCBcdWJhYjhcdWFlMzhcdWM3NzRcdWIyOTQgXHViY2MwXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWMwYWNcdWFjZmNcdWM3NTggXHVjNzA0XHVjZTU4XHVjNjQwIFx1YmM0MFx1Yzc1OCBcdWM3NzRcdWIzZDlcdWFjYmRcdWI4NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YyBcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzc0IFx1YmE4NyBcdWNkMDhcdWM1ZDAgXHViMDVkXHViMDk4XHViMjk0XHVjOWMwIFx1YWNjNFx1YzBiMFx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViY2Y0XHViNGRjXHVjNzU4IFx1ZDA2Y1x1YWUzMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMTAwKSBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwIFx1YzBhY1x1YWNmY1x1Yzc1OCBcdWFjMWNcdWMyMTgmbmJzcDtLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyBLICZsZTsgMTAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgS1x1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGFjXHVhY2ZjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAsIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjODE1XHVjMjE4XHViMjk0Jm5ic3A7XHVkNTg5LCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzgxNVx1YzIxOFx1YjI5NCZuYnNwO1x1YzVmNCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiZuYnNwO1x1YzBhY1x1YWNmY1x1Yzc1OCBcdWM3MDRcdWNlNThcdWIyOTQgXHViYWE4XHViNDUwIFx1YjJlNFx1Yjk3NFx1YmE3MCwgXHViOWU4IFx1YzcwNCBcdWI5ZTggXHVjODhjXHVjZTIxICgxXHVkNTg5IDFcdWM1ZjQpIFx1YzVkMFx1YjI5NCBcdWMwYWNcdWFjZmNcdWFjMDAgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmM0MFx1Yzc1OCBcdWJjMjlcdWQ1YTUgXHViY2MwXHVkNjU4IFx1ZDY5Zlx1YzIxOCBMIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTCAmbGU7IDEwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIExcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmM0MFx1Yzc1OCBcdWJjMjlcdWQ1YTUgXHViY2MwXHVkNjU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAsICZuYnNwO1x1YzgxNVx1YzIxOCBYXHVjNjQwIFx1YmIzOFx1Yzc5MCBDXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAuIFx1YWM4Y1x1Yzc4NCBcdWMyZGNcdWM3OTEgXHVjMmRjXHVhYzA0XHVjNzNjXHViODVjXHViZDgwXHVkMTMwIFhcdWNkMDhcdWFjMDAgXHViMDVkXHViMDljIFx1YjRhNFx1YzVkMCBcdWM2N2NcdWNhYmQoQ1x1YWMwMCAmIzM5O0wmIzM5OykgXHViNjEwXHViMjk0IFx1YzYyNFx1Yjk3OFx1Y2FiZChDXHVhYzAwICYjMzk7RCYjMzk7KVx1Yjg1YyA5MFx1YjNjNCBcdWJjMjlcdWQ1YTVcdWM3NDQgXHVkNjhjXHVjODA0XHVjMmRjXHVkMGE4XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gWFx1YjI5NCAxMCwwMDAgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWJhNzAsIFx1YmMyOVx1ZDVhNSBcdWM4MDRcdWQ2NTggXHVjODE1XHViY2Y0XHViMjk0IFhcdWFjMDAgXHVjOTlkXHVhYzAwXHVkNTU4XHViMjk0IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjOGNcdWM3ODRcdWM3NzQgXHViYTg3IFx1Y2QwOFx1YzVkMCBcdWIwNWRcdWIwOThcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMxOTAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJ6bWlqYSIsImRlc2NyaXB0aW9uIjoiPHA+T25lIG9mIHRoZSBtb3N0IHBvcHVsYXIgRE9TIGdhbWVzIGlzICYjMzk7RHVtbXkmIzM5Oy4gVGhlIHNuYWtlIGlzIGNyYXdsaW5nIHRocm91Z2ggdGhlIGJvYXJkIGFuZCBlYXRpbmcgYXBwbGVzIHRoYXQgaW5jcmVhc2UgaXRzIGxlbmd0aC4gVGhlIGdhbWUgZW5kcyB3aGVuIHRoZSBzbmFrZSBidW1wcyBpbnRvIGl0c2VsZiBvciBpbnRvIHRoZSB3YWxsLiZuYnNwOzxcL3A+XHJcblxyXG48cD5HYW1lIGJvYXJkIGNvbnNpc3RzIG9mIE54TiBzcXVhcmVzIGFycmFuZ2VkIGluIE4gcm93cyBhbmQgTiBjb2x1bW5zLCBhbmQgc29tZSBzcXVhcmVzIGNvbnRhaW4gYXBwbGVzLiBBcm91bmQgdGhlIGJvYXJkIHRoZXJlIGlzIGEgd2FsbC4gQXQgdGhlIGJlZ2lubmluZyBvZiB0aGUgZ2FtZSwgdGhlIHNuYWtlIGlzIGxvY2F0ZWQgaW4gdGhlIHRvcC1sZWZ0IGNvcm5lciwgaXRzIGxlbmd0aCBpcyBlcXVhbCB0byAxIGFuZCBpdHMgaGVhZCBpcyBkaXJlY3RlZCB0b3dhcmRzIHJpZ2h0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5TbmFrZSBpcyBjcmF3bGluZyBieSBjaGFuZ2luZyBpdHMgcG9zaXRpb24gZHVyaW5nIGVhY2ggc2Vjb25kIGFjY29yZGluZyB0byB0aGUgZm9sbG93aW5nIHJ1bGVzOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPmZpcnN0LCBzbmFrZSBleHRlbmRzIGl0cyBsZW5ndGggYnkgc3ByZWFkaW5nIHRvIHRoZSBuZXh0IHNxdWFyZSBpbiBmcm9udCBvZiB0aGUgaGVhZCAoaS5lLiBpbiB0aGUgZGlyZWN0aW9uIG9mIHRoZSBoZWFkKSw8XC9saT5cclxuXHQ8bGk+aWYgdGhlcmUgaXMgYW4gYXBwbGUgb24gdGhhdCBzcXVhcmUsIHRhaWwgb2YgdGhlIHNuYWtlIGRvZXMgbm90IG1vdmUgKGhlbmNlLCBpdHMgbGVuZ3RoIGlzIGluY3JlYXNlZCBieSAxIGluIHRoaXMgc3RlcCksPFwvbGk+XHJcblx0PGxpPmlmIHRoZXJlIGlzIG5vIGFwcGxlLCBsYXN0IHNxdWFyZSBvZiB0aGUgdGFpbCBpcyBlcmFzZWQgKGhlbmNlLCBpdHMgbGVuZ3RoIHN0YXlzIHVuY2hhbmdlZCkmbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Qb3NpdGlvbnMgb2YgdGhlIGFwcGxlcyBhbmQgbW92ZW1lbnRzIG9mIHRoZSBzbmFrZSBhcmUgZ2l2ZW4uIFdyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgY2FsY3VsYXRlIHRoZSBudW1iZXIgb2Ygc2Vjb25kcyB1bnRpbCB0aGUgZ2FtZSBlbmRzLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+Rmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIE4sIDIgJmxlOyBOICZsZTsgMTAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb2xsb3dpbmcgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIEssIDAgJmxlOyBLICZsZTsgMTAwLCB0aGUgbnVtYmVyIG9mIGFwcGxlcyBvbiB0aGUgYm9hcmQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvbGxvd2luZyBLIGxpbmVzIGNvbnRhaW4gY29vcmRpbmF0ZXMgb2YgYXBwbGVzIG9uIHRoZSBib2FyZC4gRmlyc3QgbnVtYmVyIGRlbm90ZXMgdGhlIHJvdyBhbmQgc2Vjb25kIG51bWJlciBkZW5vdGVzIHRoZSBjb2x1bW4gb2YgdGhlIGJvYXJkIHdoZXJlIHRoZSBhcHBsZSBpcyBzaXR1YXRlZC4gVGhlcmUgd2lsbCBiZSBubyBhcHBsZSBhdCB0aGUgdG9wLWxlZnQgY29ybmVyIG9mIHRoZSBib2FyZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9sbG93aW5nIGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBudW1iZXIgTCwgMSAmbGU7IEwgJmxlOyAxMDAsIHRoZSBudW1iZXIgb2YgdGltZXMgdGhlIHNuYWtlIG1ha2VzIGEgdHVybi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIEwgbGluZXMgY29udGFpbnMgdGhlIGRlc2NyaXB0aW9uIG9mIG9uZSB0dXJuLiBBIHNpbmdsZSB0dXJuIGlzIGRlc2NyaWJlZCBieSBhIG51bWJlciBYIChwb3NpdGl2ZSBpbnRlZ2VyIGxlc3MgdGhhbiBvciBlcXVhbCB0byAxMCwwMDApIGFuZCBhIGNoYXJhY3RlciBDLiBUaGlzIG1lYW5zIHRoYXQgdGhlIHNuYWtlIHJvdGF0ZXMgaXRzIGhlYWQgOTAgZGVncmVlcyBsZWZ0IChpZiBDIGlzICYjMzk7TCYjMzk7KSBvciByaWdodCAoaWYgQyBpcyAmIzM5O0QmIzM5OykgYXQgdGhlIGVuZCBvZiB0aGUgWHRoIHNlY29uZCZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIG51bWJlciBvZiBzZWNvbmRzIGZyb20gdGhlIHByb2JsZW0gc3RhdGVtZW50LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

 

[푼 코드]

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define MAXNUM 101
struct Pos
{
	int x;
	int y;
};
int n, k, l;
int board[MAXNUM][MAXNUM];
vector<Pos> v;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
queue<pair<int, char>> q;

int ChangeDir(int cur , char dir)
{
	if (dir == 'L')
	{
		if (cur - 1 >= 0)
		{
			return cur - 1;
		}
		else
		{
			return 3;
		}
	}
	else
	{
		if (cur + 1 <= 3)
		{
			return cur + 1;
		}
		else
		{
			return 0;
		}
	}
}

bool IsRange(Pos p)
{
	return (p.x > 0 && p.x <= n && p.y > 0 && p.y <= n);
}

void moveBody(bool eat)
{
	Pos last = v[v.size() - 1];
	for (int cur = v.size()-1; cur > 0; cur--)
	{
		v[cur].x = v[cur-1].x;
		v[cur].y = v[cur-1].y;
	}
	if(eat) v.push_back(last);
}

bool IsBody(Pos p)
{
	for (auto iter = v.begin(); iter < v.end(); iter++)
	{
		if (iter->x == p.x && iter->y == p.y)
		{
			return true;
		}
	}
	return false;
}

int Solved()
{
	int time = 0;
	int currentDir = 1;
	v.push_back({ 1,1 });
	while (1)
	{
		time++;
		int nextHeadX = v[0].x + dx[currentDir];
		int nextHeadY = v[0].y + dy[currentDir];

		if (IsBody({ nextHeadX ,nextHeadY }))
		{
			break;
		}

		if (!q.empty())
		{
			int frontSec = q.front().first;
			if (time == frontSec)
			{
				char frontDir = q.front().second;
				currentDir = ChangeDir(currentDir, frontDir);
				q.pop();
			}
		}

		if (IsRange({ nextHeadX ,nextHeadY }))
		{
			if (board[nextHeadY][nextHeadX] == 1)
			{
				board[nextHeadY][nextHeadX] = 0; 
				moveBody(true);
			}
			else
			{
				moveBody(false);
			}
			v[0] = { nextHeadX ,nextHeadY };
		}
		else
		{
			break;
		}
	}
	return time;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie();
	cout.tie();
	cin >> n >> k;

	int y, x;
	for (int i = 0; i < k; i++)
	{
		cin >> y >> x;
		board[y][x] = 1;
	}

	cin >> l;
	int sec;
	char dir;
	for (int i = 0; i < l; i++)
	{
		cin >> sec >> dir;
		q.push({ sec,dir });
	}
	cout << Solved();
	return 0;
}

 

 

#구현 #C++ #백준뱀 #백준3190 #알고리즘