목록그래프 탐색 (1)

FeelingXD

[백준-16946] 벽 부수고 이동하기 4 🧱🔨

❓ Problem 🤔 How 기존 이동가능 한 통로(0) 은 항상 0이다 반환해야 할 map 형태는 벽을 깬이후 이동할수있는 거리의 최대값 이다. 각 위치에서 최대 이동거리를 기록한다. 최적화 벽을 깬이후 해당 위치에서 상 하 좌 우 를 탐색하며 갈수있는거리를 구하는건 굉장히 비효율적이다. 이를 위해 미리 캐싱해두는 법이 필요하다. 이제 이를 이동 가능한 통로를 다음과 같이 그룹으로 묶어 줄 수 있다. 위의 그림에서는 연두색이 5칸, 분홍색이 4칸 주황색이 1칸 인 그룹으로 구분 된다. 이를 그룹별로 나누고 그룹의 크기가 얼마나 되는지 표시한 자료구조가 필요하다. 깰벽을 기준으로 상하 좌우 탐색을 하고 (기본값+1 : 깨진벽은 통로가 될수 있으므로) 과 상 하 좌 우를 탐색해서 만날수 있는 통로의 그룹을..
프로그래밍/문제풀이 2024. 1. 30. 20:17
이전 Prev 1 Next 다음