문제
프로그래밍 경진대회 하는데 느닷없이 화석 캐는 사람들..
4k+1의 변의 길이를 가진 정사각형 크기의 달팽이 형태 화석이 있으며 중심은 (2k+1, 2k+1)이다.
여기서 달팽이 화석을 찾아 출력에 해당 화석의 중심 위치와 한 변의 길이, 화석의 방향을 출력하면 된다.
방향은 위에 나온 것처럼 8가지로 구분할 수 있다. 어디에서 출발해서 어떤 방향으로 가느냐가 관건인데, DFS를 시작하면서 나오는 방향에 따라 재귀함수로 넘겨줄 때 함께 넘겨주면 될 것 같다.
이 문제는 어차피 화석이 항상 제대로 묻혀있다는 가정 하에 푸는 문제이기 때문에 딱히 해당 화석이 제대로 된 화석인지에 대해서는 따로 검증은 필요없을 것 같다. 하지만 변의 길이는 제대로 알아야 한다.
일단 먼저 DFS로 돌면서, 맨 처음 화석이 발견한 곳을 찾으면 재귀 함수로 DFS 탐색을 시작한다. 탐색을 하면서 시작점과 중앙을 인자로 넘겨주면 이를 통해 한 변의 길이를 구할 수 있을 것 같고, 방향의 경우 어디 방향으로 나아가는지를 맨 처음부터 구별해서 주변 될 것 같다.