[문제 본문]
더보기
문제
'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.
게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.
뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.
- 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
- 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
- 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.
출력
첫째 줄에 게임이 몇 초에 끝나는지 출력한다.
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 #알고리즘