시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 561 180 150 35.047%

문제

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

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

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

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

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

입력

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

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

출력

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

예제 입력

4 3
XXX
X.X
X.X
XXX

예제 출력

1

힌트

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

...XXX...
.X.....X.
...XXX...

출처

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

  • 문제의 오타를 찾은 사람: august14
  • 문제를 번역한 사람: baekjoon