BOJ 26989 The Grove
BOJ 26989 The Grove
문제 내용
사각 격자의 *로 표시된 칸에서 출발하여 X자로 칠해진 모든 칸을 감싸서 한 바퀴를 돈 뒤 출발점으로 돌아오려고 합니다.
X칸은 4방향 연결성을 기준으로 하나의 연결 요소를 이룹니다.
한 번의 이동으로 가로, 세로, 또는 대각선 방향으로 이웃한 칸으로 이동할 수 있을 때, 최소 이동 횟수를 구하세요.
입력
첫 줄에 행의 개수 과 열의 개수 가 주어집니다. ()
다음 줄에는 격자의 상태가 주어집니다.
문제 풀이
스포일러
먼저, #23770 Dyson Circle 의 Dyson circle을 구하는 것을 생각해 볼 수 있습니다. 이때 X는 strictly 내부에 포함해야 하고 *는 테두리에 있을 수도 있음에 유의합니다. 크기가 크지 않으므로 그러한 경로의 모든 칸을 기록해 둘 수 있습니다.
이 경로 위에 시작점이 있다면, 그 길이가 그대로 정답이 됩니다.
그렇지 않다면 시작점은 Dyson circle의 내부에 있고, 시작점에서 출발하여 Dyson circle의 어떤 점으로 진입한 뒤에 한 바퀴를 돌고, Dyson circle의 다른 어떤 점에서 시작점으로 돌아오는 경로가 최적입니다. 이를 구하기 위해서는 시작점에서부터 BFS를 한 번 돌려 Dyson circle 상의 각 칸으로 연결되는 최단 거리를 구하고, 모든 Dyson circle 상의 두 칸의 조합에 대해 시작점 - X - Y - 시작점의 경로의 길이를 구하여 그 중 최소를 출력하면 됩니다.
Last updated on