시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1779 744 635 43.703%

문제

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

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

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

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

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

유턴은 방금 이동한 방향의 반대 방향으로 이동하는 것을 말한다.

입력

첫째 줄에 마을의 크기 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+PFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM3NzRcdWMwYWNcdWFjMDBcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1YjljOFx1Yzc0NFx1Yzc0MCBcdWI5YzlcdWIyZTRcdWI5NzggXHVhZTM4XHVjNzc0IFx1Yzc4OFx1YzczY1x1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0LiBcdWI5YzlcdWIyZTRcdWI5NzggXHVhZTM4XHVjNzQwIFx1YzcyMFx1ZDEzNFx1Yzc0NCBcdWQ1NThcdWM5YzAgXHVjNTRhXHVhY2UwXHViMjk0IFx1YmU2MFx1YzgzOFx1YjA5OFx1YzYyYyBcdWMyMTggXHVjNWM2XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC4gXHVjNWI0XHViNWE0IFx1YjljOFx1Yzc0NFx1Yzc1OCBcdWM5YzBcdWIzYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzIwXHVkMTM0XHVjNzQ0IFx1ZDU1OFx1YzljMCBcdWM1NGFcdWFjZTAgXHViOWM4XHVjNzQ0XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWFkNmNcdWM1ZWRcdWM3NDQgXHViM2NjXHVjNTQ0XHViMmU0XHViMmQwIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjNWM2XHViMjk0XHVjOWMwKFx1YjljOVx1YjJlNFx1Yjk3OCBcdWFlMzhcdWM3NzQgXHVjNzg4XHViMjk0XHVjOWMwIFx1YzVjNlx1YjI5NFx1YzljMClcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YjljOFx1Yzc0NFx1Yzc1OCBcdWM5YzBcdWIzYzRcdWIyOTQgUiAmdGltZXM7IEMgXHVjZTc4XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWQ0NWNcdWI4NWMgXHVjMGRkXHVhYzAxXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWNlNzhcdWM1ZDAgXHViZTRjXHViNTI5XHVjNzc0IFx1Yzc4OFx1YjJlNFx1YmE3NCAmIzM5O1gmIzM5O1x1Yjg1YyBcdWQ0NWNcdWMyZGNcdWQ1NThcdWFjZTAsIFx1YWUzOFx1Yzc3NFx1Yjc3Y1x1YmE3NCAmIzM5Oy4mIzM5O1x1YzczY1x1Yjg1YyBcdWQ0NWNcdWMyZGNcdWQ1NWNcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWNlNzhcdWM3NDAgXHViZTRjXHViNTI5IFx1YjYxMFx1YjI5NCBcdWFlMzhcdWM3NzRcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM1YjRcdWI1YTQgXHVhZTM4IFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1YWRmY1x1Y2M5OCBcdWIxMjQgXHViYzI5XHVkNWE1KFx1YzcwNCxcdWM1NDRcdWI3OTgsXHVjNjI0XHViOTc4XHVjYWJkLFx1YzY3Y1x1Y2FiZClcdWM3NTggXHVhZTM4XHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWJlNGNcdWI1MjlcdWM3M2NcdWI4NWNcdWIyOTQgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWI5YzhcdWM3NDRcdWM1ZDAgXHViOWM5XHViMmU0XHViOTc4IFx1YWUzOFx1Yzc3NCBcdWM1YzZcdWIyZTRcdWJhNzQsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3ODRcdWM3NThcdWM3NTggXHVkNTVjIFx1YWUzOFx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NzRcdWMxMWMsIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzViNFx1YjVhNCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzc0XHViMzU0XHViNzdjXHViM2M0LCBcdWM3MjBcdWQxMzRcdWM3NDQgXHVkNTU4XHVjOWMwIFx1YzU0YVx1YWNlMCBcdWFkZjggXHVjNzA0XHVjZTU4XHViODVjIFx1YjNjY1x1YzU0NFx1YzYyYyBcdWMyMTggXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzIwXHVkMTM0XHVjNzQwIFx1YmMyOVx1YWUwOCBcdWM3NzRcdWIzZDlcdWQ1NWMgXHViYzI5XHVkNWE1XHVjNzU4IFx1YmMxOFx1YjMwMCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWI5ZDBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjljOFx1Yzc0NFx1Yzc1OCBcdWQwNmNcdWFlMzAgUlx1YWNmYyBDXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDMgJmxlOyBSLCBDICZsZTsgMTApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBSXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI5YzhcdWM3NDRcdWM3NTggXHVjOWMwXHViM2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YWUzOFx1Yzc0MCBcdWMxMWNcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHViNjEwLCBcdWI5YzhcdWM3NDRcdWM1ZDBcdWIyOTQgXHVjODAxXHVjNWI0XHViM2M0IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVhZTM4XHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjljOFx1Yzc0NFx1YzVkMCBcdWI5YzlcdWIyZTRcdWI5NzggXHVhZTM4XHVjNzc0IFx1YzVjNlx1YjJlNFx1YmE3NCAwXHVjNzQ0LCBcdWFkZjhcdWI4MDdcdWM5YzAgXHVjNTRhXHViMmU0XHViYTc0IDFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWI5Y2NcdWM1N2QsIFx1YjljOFx1Yzc0NFx1Yzc1OCBcdWM5YzBcdWIzYzRcdWFjMDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YjJlNFx1YmE3NCwgXHVjNzIwXHVkMTM0IFx1YzVjNlx1Yzc3NCBcdWI5YzhcdWM3NDRcdWM3NDQgXHViM2NjXHVjNTQ0XHViMmU0XHViMmQwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbi4uLlhYWC4uLlxyXG4uWC4uLi4uWC5cclxuLi4uWFhYLi4uPFwvcHJlPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI4MjMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJPS1JFVCIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gaGFzIGJlZW4gbGVhcm5pbmcgdG8gZHJpdmUsIGJ1dCBoZSBzdGlsbCBjYW5ub3QgbWFrZSBhIFUtdHVybiBpbiBhIG5hcnJvdyBzdHJlZXQuIFRoYXQmcnNxdW87cyB3aHkgaGUgaGFzIGRlY2lkZWQgdG8gZ28gcHJhY3RpY2UgaW4gYSB0b3duIHdoZXJlIFUtdHVybnMgYXJlIGZvcmJpZGRlbiBldmVyeXdoZXJlLiBUaGlzIHByb2hpYml0aW9uIGNhbiBiZSBtYXJrZWQgYnkgdGhlIGZvbGxvd2luZyBzaWduOiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3V0dXJuLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjU5cHg7IHdpZHRoOjc0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+TWlya28gaGFzIHNvb24gZmlndXJlZCBvdXQgdGhhdCBoaXMgaWRlYWwgdG93biBtdXN0IG5vdCBjb250YWluIGRlYWQtZW5kIHN0cmVldHMsIHNpbmNlIGl0IGlzIGltcG9zc2libGUgdG8gZXhpdCBzdWNoIGEgc3RyZWV0IHdpdGhvdXQgYSBVLXR1cm4gKGxldCB1cyBhc3N1bWUgdGhhdCBNaXJrbyBjYW5ub3QgZHJpdmUgaW4gcmV2ZXJzZSBlaXRoZXIpLiBXcml0ZSBhIHByb2dyYW0gdG8gYW5hbHlzZSBhIHRvd24gbWFwIGFuZCBkZXRlcm1pbmUgd2hldGhlciB0aGUgdG93biBpcyBzdWl0YWJsZSBmb3IgTWlya28gKGkuZS4gd2hldGhlciB0aGUgdG93biBoYXMgYW55IGRlYWQtZW5kIHN0cmVldHMpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgdG93biBtYXAgaXMgYSB0YWJsZSB3aXRoIFIgeCBDIGNlbGxzLCB3aGVyZSBlYWNoIGNlbGwgaXMgYSBidWlsZGluZyBzZWdtZW50IChkZW5vdGVkIGJ5IFgpIG9yIGEgcm9hZCBzdXJmYWNlIChkZW5vdGVkIGJ5IGEgZG90KS4gRnJvbSBhIHJvYWQgc3VyZmFjZSBjZWxsLCBNaXJrbyBjYW4gbW92ZSB0byBhbnkgb2YgdGhlIHN1cnJvdW5kaW5nIGZvdXIgY2VsbHMgKHVwLCBkb3duLCBsZWZ0LCBvciByaWdodCksIHByb3ZpZGVkIHRoYXQgaXQgaXMgYWxzbyBhIHJvYWQgc3VyZmFjZSAoaS5lLiBub3QgYSBidWlsZGluZykuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvcm1hbGx5LCB3ZSB3aWxsIGRldGVybWluZSB0aGF0IGEgdG93biBpcyBmcmVlIG9mIGRlYWQtZW5kIHN0cmVldHMgaWYsIHN0YXJ0aW5nIGZyb20gYW55IHJvYWQgc3VyZmFjZSBjZWxsIGFuZCBnb2luZyBpbiBhbnkgb2YgdGhlIHBvc3NpYmxlIGRpcmVjdGlvbnMsIHdlIGNhbiByZXR1cm4gdG8gdGhlIHN0YXJ0aW5nIGNlbGwgd2l0aG91dCBtYWtpbmcgYSAxODAgZGVncmVlcyB0dXJuIChjaGFuZ2luZyBvdXIgZGlyZWN0aW9uIHRvIHRoZSBvcHBvc2l0ZSBvbmUpLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXJzIFIgYW5kIEMgKDMgJmxlOyBSLCBDICZsZTsgMTApLCB0aGUgZGltZW5zaW9ucyBvZiB0aGUgdG93bi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCBSIGxpbmVzIGNvbnRhaW5zIEMgY2hhcmFjdGVycywgd2l0aCBlYWNoIGNoYXJhY3RlciBlaXRoZXIgJmxkcXVvO1gmcmRxdW87IG9yICZsZHF1bzsuJnJkcXVvOy4gVGhlc2UgUiB4IEMgY2hhcmFjdGVycyByZXByZXNlbnQgdGhlIHRvd24gbWFwIGFzIGRlc2NyaWJlZCBpbiB0aGUgdGV4dCBhYm92ZS4gQXQgbGVhc3QgdHdvIGNlbGxzIHdpbGwgYmUgcm9hZCBzdXJmYWNlcywgYW5kIGFsbCByb2FkIHN1cmZhY2VzIHdpbGwgYmUgY29ubmVjdGVkIChpLmUuIG11dHVhbGx5IHJlYWNoYWJsZSkuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiAwIGlmIHRoZSB0b3duIGlzIGZyZWUgb2YgZGVhZC1lbmQgc3RyZWV0cywgb3RoZXJ3aXNlIGl0IG11c3QgY29udGFpbiAxLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

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