시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1027 387 337 40.311%

문제

상근이는 여자친구와의 드라이브를 위해서 운전을 배우고 있다. 도로 연수를 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+PFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM3NzRcdWMwYWNcdWFjMDBcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1YjljOFx1Yzc0NFx1Yzc0MCBcdWI5YzlcdWIyZTRcdWI5NzggXHVhZTM4XHVjNzc0IFx1Yzc4OFx1YzczY1x1YmE3NCBcdWM1NDhcdWI0MWNcdWIyZTQuIFx1YjljOVx1YjJlNFx1Yjk3OCBcdWFlMzhcdWM3NDAgXHVjNzIwXHVkMTM0XHVjNzQ0IFx1ZDU1OFx1YzljMCBcdWM1NGFcdWFjZTBcdWIyOTQgXHViZTYwXHVjODM4XHViMDk4XHVjNjJjIFx1YzIxOCBcdWM1YzZcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LiBcdWM1YjRcdWI1YTQgXHViOWM4XHVjNzQ0XHVjNzU4IFx1YzljMFx1YjNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3MjBcdWQxMzRcdWM3NDQgXHVkNTU4XHVjOWMwIFx1YzU0YVx1YWNlMCBcdWI5YzhcdWM3NDRcdWM3NTggXHViYWE4XHViNGUwIFx1YWQ2Y1x1YzVlZFx1Yzc0NCBcdWIzY2NcdWM1NDRcdWIyZTRcdWIyZDAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWM1YzZcdWIyOTRcdWM5YzAoXHViOWM5XHViMmU0XHViOTc4IFx1YWUzOFx1Yzc3NCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjNWM2XHViMjk0XHVjOWMwKVx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHViOWM4XHVjNzQ0XHVjNzU4IFx1YzljMFx1YjNjNFx1YjI5NCBSICZ0aW1lczsgQyBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1ZDQ1Y1x1Yjg1YyBcdWMwZGRcdWFjMDFcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1Y2U3OFx1YzVkMCBcdWJlNGNcdWI1MjlcdWM3NzQgXHVjNzg4XHViMmU0XHViYTc0ICYjMzk7WCYjMzk7XHViODVjIFx1ZDQ1Y1x1YzJkY1x1ZDU1OFx1YWNlMCwgXHVhZTM4XHVjNzc0XHViNzdjXHViYTc0ICYjMzk7LiYjMzk7XHVjNzNjXHViODVjIFx1ZDQ1Y1x1YzJkY1x1ZDU1Y1x1YjJlNC4gXHViYWE4XHViNGUwIFx1Y2U3OFx1Yzc0MCBcdWJlNGNcdWI1MjkgXHViNjEwXHViMjk0IFx1YWUzOFx1Yzc3NFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzViNFx1YjVhNCBcdWFlMzggXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjJlNFx1YmE3NCwgXHVhZGZjXHVjYzk4IFx1YjEyNCBcdWJjMjlcdWQ1YTUoXHVjNzA0LFx1YzU0NFx1Yjc5OCxcdWM2MjRcdWI5NzhcdWNhYmQsXHVjNjdjXHVjYWJkKVx1Yzc1OCBcdWFlMzhcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YmU0Y1x1YjUyOVx1YzczY1x1Yjg1Y1x1YjI5NCBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YjljOFx1Yzc0NFx1YzVkMCBcdWI5YzlcdWIyZTRcdWI5NzggXHVhZTM4XHVjNzc0IFx1YzVjNlx1YjJlNFx1YmE3NCwgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWQ1NWMgXHVhZTM4XHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU3NFx1YzExYywgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNWI0XHViNWE0IFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM2YzBcdWM5YzFcdWM3NzRcdWIzNTRcdWI3N2NcdWIzYzQsIFx1YzcyMFx1ZDEzNFx1Yzc0NCBcdWQ1NThcdWM5YzAgXHVjNTRhXHVhY2UwIFx1YWRmOCBcdWM3MDRcdWNlNThcdWI4NWMgXHViM2NjXHVjNTQ0XHVjNjJjIFx1YzIxOCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiAoXHVjNzIwXHVkMTM0XHVjNzQwIFx1YmMyOVx1ZDVhNVx1Yzc0NCBcdWM3NzRcdWIzZDkgXHViYzI5XHVkNWE1XHVjNzc0IDE4MFx1YjNjNFx1Yjg1YyBcdWJjMTRcdWFmYjhcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gOTBcdWIzYzRcdWI4NWMgMlx1YmM4OCBcdWJjMTRcdWFmYjhcdWIyOTQgXHVhYzgzXHViM2M0IDE4MFx1YjNjNCBcdWM3NzRcdWIyZTQpPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjljOFx1Yzc0NFx1Yzc1OCBcdWQwNmNcdWFlMzAgUlx1YWNmYyBDXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDMgJmxlOyBSLCBDICZsZTsgMTApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBSXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI5YzhcdWM3NDRcdWM3NTggXHVjOWMwXHViM2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YWUzOFx1Yzc0MCBcdWMxMWNcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHViNjEwLCBcdWI5YzhcdWM3NDRcdWM1ZDBcdWIyOTQgXHVjODAxXHVjNWI0XHViM2M0IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVhZTM4XHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjljOFx1Yzc0NFx1YzVkMCBcdWI5YzlcdWIyZTRcdWI5NzggXHVhZTM4XHVjNzc0IFx1YzVjNlx1YjJlNFx1YmE3NCAwXHVjNzQ0LCBcdWFkZjhcdWI4MDdcdWM5YzAgXHVjNTRhXHViMmU0XHViYTc0IDFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWI5Y2NcdWM1N2QsIFx1YjljOFx1Yzc0NFx1Yzc1OCBcdWM5YzBcdWIzYzRcdWFjMDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YjJlNFx1YmE3NCwgXHVjNzIwXHVkMTM0IFx1YzVjNlx1Yzc3NCBcdWI5YzhcdWM3NDRcdWM3NDQgXHViM2NjXHVjNTQ0XHViMmU0XHViMmQwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbi4uLlhYWC4uLlxyXG4uWC4uLi4uWC5cclxuLi4uWFhYLi4uPFwvcHJlPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI4MjMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJPS1JFVCIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gaGFzIGJlZW4gbGVhcm5pbmcgdG8gZHJpdmUsIGJ1dCBoZSBzdGlsbCBjYW5ub3QgbWFrZSBhIFUtdHVybiBpbiBhIG5hcnJvdyBzdHJlZXQuIFRoYXQmcnNxdW87cyB3aHkgaGUgaGFzIGRlY2lkZWQgdG8gZ28gcHJhY3RpY2UgaW4gYSB0b3duIHdoZXJlIFUtdHVybnMgYXJlIGZvcmJpZGRlbiBldmVyeXdoZXJlLiBUaGlzIHByb2hpYml0aW9uIGNhbiBiZSBtYXJrZWQgYnkgdGhlIGZvbGxvd2luZyBzaWduOiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3V0dXJuLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjU5cHg7IHdpZHRoOjc0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+TWlya28gaGFzIHNvb24gZmlndXJlZCBvdXQgdGhhdCBoaXMgaWRlYWwgdG93biBtdXN0IG5vdCBjb250YWluIGRlYWQtZW5kIHN0cmVldHMsIHNpbmNlIGl0IGlzIGltcG9zc2libGUgdG8gZXhpdCBzdWNoIGEgc3RyZWV0IHdpdGhvdXQgYSBVLXR1cm4gKGxldCB1cyBhc3N1bWUgdGhhdCBNaXJrbyBjYW5ub3QgZHJpdmUgaW4gcmV2ZXJzZSBlaXRoZXIpLiBXcml0ZSBhIHByb2dyYW0gdG8gYW5hbHlzZSBhIHRvd24gbWFwIGFuZCBkZXRlcm1pbmUgd2hldGhlciB0aGUgdG93biBpcyBzdWl0YWJsZSBmb3IgTWlya28gKGkuZS4gd2hldGhlciB0aGUgdG93biBoYXMgYW55IGRlYWQtZW5kIHN0cmVldHMpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgdG93biBtYXAgaXMgYSB0YWJsZSB3aXRoIFIgeCBDIGNlbGxzLCB3aGVyZSBlYWNoIGNlbGwgaXMgYSBidWlsZGluZyBzZWdtZW50IChkZW5vdGVkIGJ5IFgpIG9yIGEgcm9hZCBzdXJmYWNlIChkZW5vdGVkIGJ5IGEgZG90KS4gRnJvbSBhIHJvYWQgc3VyZmFjZSBjZWxsLCBNaXJrbyBjYW4gbW92ZSB0byBhbnkgb2YgdGhlIHN1cnJvdW5kaW5nIGZvdXIgY2VsbHMgKHVwLCBkb3duLCBsZWZ0LCBvciByaWdodCksIHByb3ZpZGVkIHRoYXQgaXQgaXMgYWxzbyBhIHJvYWQgc3VyZmFjZSAoaS5lLiBub3QgYSBidWlsZGluZykuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvcm1hbGx5LCB3ZSB3aWxsIGRldGVybWluZSB0aGF0IGEgdG93biBpcyBmcmVlIG9mIGRlYWQtZW5kIHN0cmVldHMgaWYsIHN0YXJ0aW5nIGZyb20gYW55IHJvYWQgc3VyZmFjZSBjZWxsIGFuZCBnb2luZyBpbiBhbnkgb2YgdGhlIHBvc3NpYmxlIGRpcmVjdGlvbnMsIHdlIGNhbiByZXR1cm4gdG8gdGhlIHN0YXJ0aW5nIGNlbGwgd2l0aG91dCBtYWtpbmcgYSAxODAgZGVncmVlcyB0dXJuIChjaGFuZ2luZyBvdXIgZGlyZWN0aW9uIHRvIHRoZSBvcHBvc2l0ZSBvbmUpLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXJzIFIgYW5kIEMgKDMgJmxlOyBSLCBDICZsZTsgMTApLCB0aGUgZGltZW5zaW9ucyBvZiB0aGUgdG93bi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCBSIGxpbmVzIGNvbnRhaW5zIEMgY2hhcmFjdGVycywgd2l0aCBlYWNoIGNoYXJhY3RlciBlaXRoZXIgJmxkcXVvO1gmcmRxdW87IG9yICZsZHF1bzsuJnJkcXVvOy4gVGhlc2UgUiB4IEMgY2hhcmFjdGVycyByZXByZXNlbnQgdGhlIHRvd24gbWFwIGFzIGRlc2NyaWJlZCBpbiB0aGUgdGV4dCBhYm92ZS4gQXQgbGVhc3QgdHdvIGNlbGxzIHdpbGwgYmUgcm9hZCBzdXJmYWNlcywgYW5kIGFsbCByb2FkIHN1cmZhY2VzIHdpbGwgYmUgY29ubmVjdGVkIChpLmUuIG11dHVhbGx5IHJlYWNoYWJsZSkuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiAwIGlmIHRoZSB0b3duIGlzIGZyZWUgb2YgZGVhZC1lbmQgc3RyZWV0cywgb3RoZXJ3aXNlIGl0IG11c3QgY29udGFpbiAxLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

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