GOLD25 [백준/C++] #16946 벽 부수고 이동하기 4 (Flood Fill / BFS) 문제https://www.acmicpc.net/problem/16946알고리즘: Flood Fill / bfs 구상처음에는 단순하게 bfs를 통해 얼마나 많은 칸으로 이동할 수 있는지 구하는 줄 알고, 엥 왜 골드 3이지? 하고 풀었는데, 배열 크기가 최대 1000*1000까지 커질 수 있기에 시간초과가 났다.. 그래서 긴 탐색 시간을 줄여야한다고 생각했다. 하지만, 각각의 벽에서 이동할 수 있는 칸의 개수를 알아내야 했기에 이땐 변함없이 이중 for문이 필요했다. 그래서 떠오른게, 이동할 수 있는 칸들은 뭉텅이로 존재하는데, 뭉텅이의 크기를 파악하면, 벽의 상하좌우에 위치한 뭉텅이들의 크기만 고려할 수 있지 않을까?였다. 즉, 어떤 칸과 연결된 영역을 찾는 알고리즘인 flood fill을 통해 전처리만.. 2024. 7. 3. 이전 1 2 3 4 5 다음
