시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1182 465 405 42.056%

문제

상근이는 여자친구와의 드라이브를 위해서 운전을 배우고 있다. 도로 연수를 10년쯤 하다 보니 운전은 그럭저럭 잘하게 되었다. 하지만, 그는 유턴을 하지 못한다. 10년동안 도로 연수를 받았지만 유턴을 하지 못한다. 밥먹고 유턴만 연습했지만, 결국 유턴은 하지 못했다.

상근이는 유턴을 연습하기 위해서 시간을 투자하는 대신에 유턴을 할 필요가 없고, 유턴이 금지된 마을로 이사가려고 한다.

상근이가 이사가려고 하는 마을은 막다른 길이 있으면 안 된다. 막다른 길은 유턴을 하지 않고는 빠져나올 수 없기 때문이다. 어떤 마을의 지도가 주어졌을 때, 유턴을 하지 않고 마을의 모든 구역을 돌아다닐 수 있는지 없는지(막다른 길이 있는지 없는지)를 구하는 프로그램을 작성하시오. 

마을의 지도는 R × C 칸으로 이루어진 표로 생각할 수 있다. 각 칸에 빌딩이 있다면 'X'로 표시하고, 길이라면 '.'으로 표시한다. 모든 칸은 빌딩 또는 길이다. 상근이가 어떤 길 위에 있다면, 근처 네 방향(위,아래,오른쪽,왼쪽)의 길로 이동할 수 있다. 빌딩으로는 이동할 수 없다.

이 마을에 막다른 길이 없다면, 상근이는 임의의 한 길에서 시작해서, 갈 수 있는 어떤 방향으로 움직이더라도, 유턴을 하지 않고 그 위치로 돌아올 수 있어야 한다. (유턴은 방향을 이동 방향이 180도로 바꾸는 것을 의미한다. 90도로 2번 바꾸는 것도 180도 이다)

입력

첫째 줄에 마을의 크기 R과 C가 주어진다. (3 ≤ R, C ≤ 10)

다음 R개 줄에는 마을의 지도가 주어진다. 모든 길은 서로 연결되어 있다. 또, 마을에는 적어도 두 개의 길이 있다.

출력

첫째 줄에 마을에 막다른 길이 없다면 0을, 그렇지 않다면 1을 출력한다.

예제 입력 1

4 3
XXX
X.X
X.X
XXX

예제 출력 1

1

힌트

만약, 마을의 지도가 아래와 같다면, 유턴 없이 마을을 돌아다닐 수 있다.

...XXX...
.X.....X.
...XXX...
W3sicHJvYmxlbV9pZCI6IjI4MjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3MjBcdWQxMzQgXHVjMmViXHVjNWI0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNWVjXHVjNzkwXHVjZTVjXHVhZDZjXHVjNjQwXHVjNzU4IFx1YjRkY1x1Yjc3Y1x1Yzc3NFx1YmUwY1x1Yjk3YyBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjNmI0XHVjODA0XHVjNzQ0IFx1YmMzMFx1YzZiMFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YjNjNFx1Yjg1YyBcdWM1ZjBcdWMyMThcdWI5N2MgMTBcdWIxNDRcdWNiZTQgXHVkNTU4XHViMmU0IFx1YmNmNFx1YjJjOCBcdWM2YjRcdWM4MDRcdWM3NDAgXHVhZGY4XHViN2VkXHVjODAwXHViN2VkIFx1Yzc5OFx1ZDU1OFx1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVhZGY4XHViMjk0IFx1YzcyMFx1ZDEzNFx1Yzc0NCBcdWQ1NThcdWM5YzAgXHViYWJiXHVkNTVjXHViMmU0LiAxMFx1YjE0NFx1YjNkOVx1YzU0OCBcdWIzYzRcdWI4NWMgXHVjNWYwXHVjMjE4XHViOTdjIFx1YmMxYlx1YzU1OFx1YzljMFx1YjljYyBcdWM3MjBcdWQxMzRcdWM3NDQgXHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU1Y1x1YjJlNC4gXHViYzI1XHViYTM5XHVhY2UwIFx1YzcyMFx1ZDEzNFx1YjljYyBcdWM1ZjBcdWMyYjVcdWQ1ODhcdWM5YzBcdWI5Y2MsIFx1YWNiMFx1YWQ2ZCBcdWM3MjBcdWQxMzRcdWM3NDAgXHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzcyMFx1ZDEzNFx1Yzc0NCBcdWM1ZjBcdWMyYjVcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWQyMmNcdWM3OTBcdWQ1NThcdWIyOTQgXHViMzAwXHVjMmUwXHVjNWQwIFx1YzcyMFx1ZDEzNFx1Yzc0NCBcdWQ1NjAgXHVkNTQ0XHVjNjk0XHVhYzAwIFx1YzVjNlx1YWNlMCwgXHVjNzIwXHVkMTM0XHVjNzc0IFx1YWUwOFx1YzljMFx1YjQxYyBcdWI5YzhcdWM3NDRcdWI4NWMgXHVjNzc0XHVjMGFjXHVhYzAwXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC91dHVybi5wbmdcIiBzdHlsZT1cImhlaWdodDo1OXB4OyB3aWR0aDo3NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM3NzRcdWMwYWNcdWFjMDBcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1YjljOFx1Yzc0NFx1Yzc0MCBcdWI5YzlcdWIyZTRcdWI5NzggXHVhZTM4XHVjNzc0IFx1Yzc4OFx1YzczY1x1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0LiBcdWI5YzlcdWIyZTRcdWI5NzggXHVhZTM4XHVjNzQwIFx1YzcyMFx1ZDEzNFx1Yzc0NCBcdWQ1NThcdWM5YzAgXHVjNTRhXHVhY2UwXHViMjk0IFx1YmU2MFx1YzgzOFx1YjA5OFx1YzYyYyBcdWMyMTggXHVjNWM2XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC4gXHVjNWI0XHViNWE0IFx1YjljOFx1Yzc0NFx1Yzc1OCBcdWM5YzBcdWIzYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzIwXHVkMTM0XHVjNzQ0IFx1ZDU1OFx1YzljMCBcdWM1NGFcdWFjZTAgXHViOWM4XHVjNzQ0XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWFkNmNcdWM1ZWRcdWM3NDQgXHViM2NjXHVjNTQ0XHViMmU0XHViMmQwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjNWM2XHViMjk0XHVjOWMwKFx1YjljOVx1YjJlNFx1Yjk3OCBcdWFlMzhcdWM3NzQgXHVjNzg4XHViMjk0XHVjOWMwIFx1YzVjNlx1YjI5NFx1YzljMClcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YjljOFx1Yzc0NFx1Yzc1OCBcdWM5YzBcdWIzYzRcdWIyOTQgUiAmdGltZXM7IEMgXHVjZTc4XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWQ0NWNcdWI4NWMgXHVjMGRkXHVhYzAxXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWNlNzhcdWM1ZDAgXHViZTRjXHViNTI5XHVjNzc0IFx1Yzc4OFx1YjJlNFx1YmE3NCAmIzM5O1gmIzM5O1x1Yjg1YyBcdWQ0NWNcdWMyZGNcdWQ1NThcdWFjZTAsIFx1YWUzOFx1Yzc3NFx1Yjc3Y1x1YmE3NCAmIzM5Oy4mIzM5O1x1YzczY1x1Yjg1YyBcdWQ0NWNcdWMyZGNcdWQ1NWNcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWNlNzhcdWM3NDAgXHViZTRjXHViNTI5IFx1YjYxMFx1YjI5NCBcdWFlMzhcdWM3NzRcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM1YjRcdWI1YTQgXHVhZTM4IFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1YWRmY1x1Y2M5OCBcdWIxMjQgXHViYzI5XHVkNWE1KFx1YzcwNCxcdWM1NDRcdWI3OTgsXHVjNjI0XHViOTc4XHVjYWJkLFx1YzY3Y1x1Y2FiZClcdWM3NTggXHVhZTM4XHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWJlNGNcdWI1MjlcdWM3M2NcdWI4NWNcdWIyOTQgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWI5YzhcdWM3NDRcdWM1ZDAgXHViOWM5XHViMmU0XHViOTc4IFx1YWUzOFx1Yzc3NCBcdWM1YzZcdWIyZTRcdWJhNzQsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3ODRcdWM3NThcdWM3NTggXHVkNTVjIFx1YWUzOFx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NzRcdWMxMWMsIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzViNFx1YjVhNCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzc0XHViMzU0XHViNzdjXHViM2M0LCBcdWM3MjBcdWQxMzRcdWM3NDQgXHVkNTU4XHVjOWMwIFx1YzU0YVx1YWNlMCBcdWFkZjggXHVjNzA0XHVjZTU4XHViODVjIFx1YjNjY1x1YzU0NFx1YzYyYyBcdWMyMTggXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gKFx1YzcyMFx1ZDEzNFx1Yzc0MCBcdWJjMjlcdWQ1YTVcdWM3NDQgXHVjNzc0XHViM2Q5IFx1YmMyOVx1ZDVhNVx1Yzc3NCAxODBcdWIzYzRcdWI4NWMgXHViYzE0XHVhZmI4XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIDkwXHViM2M0XHViODVjIDJcdWJjODggXHViYzE0XHVhZmI4XHViMjk0IFx1YWM4M1x1YjNjNCAxODBcdWIzYzQgXHVjNzc0XHViMmU0KTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI5YzhcdWM3NDRcdWM3NTggXHVkMDZjXHVhZTMwIFJcdWFjZmMgQ1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgzICZsZTsgUiwgQyAmbGU7IDEwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgUlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViOWM4XHVjNzQ0XHVjNzU4IFx1YzljMFx1YjNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWFlMzhcdWM3NDAgXHVjMTFjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YjYxMCwgXHViOWM4XHVjNzQ0XHVjNWQwXHViMjk0IFx1YzgwMVx1YzViNFx1YjNjNCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YWUzOFx1Yzc3NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI5YzhcdWM3NDRcdWM1ZDAgXHViOWM5XHViMmU0XHViOTc4IFx1YWUzOFx1Yzc3NCBcdWM1YzZcdWIyZTRcdWJhNzQgMFx1Yzc0NCwgXHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1YjJlNFx1YmE3NCAxXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHViOWNjXHVjNTdkLCBcdWI5YzhcdWM3NDRcdWM3NTggXHVjOWMwXHViM2M0XHVhYzAwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWIyZTRcdWJhNzQsIFx1YzcyMFx1ZDEzNCBcdWM1YzZcdWM3NzQgXHViOWM4XHVjNzQ0XHVjNzQ0IFx1YjNjY1x1YzU0NFx1YjJlNFx1YjJkMCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG4uLi5YWFguLi5cclxuLlguLi4uLlguXHJcbi4uLlhYWC4uLjxcL3ByZT5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODIzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiT0tSRVQiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGhhcyBiZWVuIGxlYXJuaW5nIHRvIGRyaXZlLCBidXQgaGUgc3RpbGwgY2Fubm90IG1ha2UgYSBVLXR1cm4gaW4gYSBuYXJyb3cgc3RyZWV0LiBUaGF0JnJzcXVvO3Mgd2h5IGhlIGhhcyBkZWNpZGVkIHRvIGdvIHByYWN0aWNlIGluIGEgdG93biB3aGVyZSBVLXR1cm5zIGFyZSBmb3JiaWRkZW4gZXZlcnl3aGVyZS4gVGhpcyBwcm9oaWJpdGlvbiBjYW4gYmUgbWFya2VkIGJ5IHRoZSBmb2xsb3dpbmcgc2lnbjombmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC91dHVybi5wbmdcIiBzdHlsZT1cImhlaWdodDo1OXB4OyB3aWR0aDo3NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPk1pcmtvIGhhcyBzb29uIGZpZ3VyZWQgb3V0IHRoYXQgaGlzIGlkZWFsIHRvd24gbXVzdCBub3QgY29udGFpbiBkZWFkLWVuZCBzdHJlZXRzLCBzaW5jZSBpdCBpcyBpbXBvc3NpYmxlIHRvIGV4aXQgc3VjaCBhIHN0cmVldCB3aXRob3V0IGEgVS10dXJuIChsZXQgdXMgYXNzdW1lIHRoYXQgTWlya28gY2Fubm90IGRyaXZlIGluIHJldmVyc2UgZWl0aGVyKS4gV3JpdGUgYSBwcm9ncmFtIHRvIGFuYWx5c2UgYSB0b3duIG1hcCBhbmQgZGV0ZXJtaW5lIHdoZXRoZXIgdGhlIHRvd24gaXMgc3VpdGFibGUgZm9yIE1pcmtvIChpLmUuIHdoZXRoZXIgdGhlIHRvd24gaGFzIGFueSBkZWFkLWVuZCBzdHJlZXRzKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHRvd24gbWFwIGlzIGEgdGFibGUgd2l0aCBSIHggQyBjZWxscywgd2hlcmUgZWFjaCBjZWxsIGlzIGEgYnVpbGRpbmcgc2VnbWVudCAoZGVub3RlZCBieSBYKSBvciBhIHJvYWQgc3VyZmFjZSAoZGVub3RlZCBieSBhIGRvdCkuIEZyb20gYSByb2FkIHN1cmZhY2UgY2VsbCwgTWlya28gY2FuIG1vdmUgdG8gYW55IG9mIHRoZSBzdXJyb3VuZGluZyBmb3VyIGNlbGxzICh1cCwgZG93biwgbGVmdCwgb3IgcmlnaHQpLCBwcm92aWRlZCB0aGF0IGl0IGlzIGFsc28gYSByb2FkIHN1cmZhY2UgKGkuZS4gbm90IGEgYnVpbGRpbmcpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3JtYWxseSwgd2Ugd2lsbCBkZXRlcm1pbmUgdGhhdCBhIHRvd24gaXMgZnJlZSBvZiBkZWFkLWVuZCBzdHJlZXRzIGlmLCBzdGFydGluZyBmcm9tIGFueSByb2FkIHN1cmZhY2UgY2VsbCBhbmQgZ29pbmcgaW4gYW55IG9mIHRoZSBwb3NzaWJsZSBkaXJlY3Rpb25zLCB3ZSBjYW4gcmV0dXJuIHRvIHRoZSBzdGFydGluZyBjZWxsIHdpdGhvdXQgbWFraW5nIGEgMTgwIGRlZ3JlZXMgdHVybiAoY2hhbmdpbmcgb3VyIGRpcmVjdGlvbiB0byB0aGUgb3Bwb3NpdGUgb25lKS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBwb3NpdGl2ZSBpbnRlZ2VycyBSIGFuZCBDICgzICZsZTsgUiwgQyAmbGU7IDEwKSwgdGhlIGRpbWVuc2lvbnMgb2YgdGhlIHRvd24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIG5leHQgUiBsaW5lcyBjb250YWlucyBDIGNoYXJhY3RlcnMsIHdpdGggZWFjaCBjaGFyYWN0ZXIgZWl0aGVyICZsZHF1bztYJnJkcXVvOyBvciAmbGRxdW87LiZyZHF1bzsuIFRoZXNlIFIgeCBDIGNoYXJhY3RlcnMgcmVwcmVzZW50IHRoZSB0b3duIG1hcCBhcyBkZXNjcmliZWQgaW4gdGhlIHRleHQgYWJvdmUuIEF0IGxlYXN0IHR3byBjZWxscyB3aWxsIGJlIHJvYWQgc3VyZmFjZXMsIGFuZCBhbGwgcm9hZCBzdXJmYWNlcyB3aWxsIGJlIGNvbm5lY3RlZCAoaS5lLiBtdXR1YWxseSByZWFjaGFibGUpLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gMCBpZiB0aGUgdG93biBpcyBmcmVlIG9mIGRlYWQtZW5kIHN0cmVldHMsIG90aGVyd2lzZSBpdCBtdXN0IGNvbnRhaW4gMS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #2 2번

  • 문제의 오타를 찾은 사람: august14
  • 문제를 번역한 사람: baekjoon
  • 잘못된 번역을 찾은 사람: dlwodnsdl