floodfill
-
[백준] Python - 음식물 피하기메모/알고리즘 2022. 3. 25. 15:11
1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net FloodFill 알고리즘을 공부해보려고 문제 몇 개를 풀기로 했다. 새로운 알고리즘은 아니고 기존의 DFS/BFS 등을 통해서 풀 수 있는 쉬운 문제였다. 2차원 배열을 생성해서 각 좌표 별 정보를 저장한다. 현재 좌표 기준으로 상하좌우 좌표 중 2차원 배열의 범위 내에 있으면서 음식물이 존재한다면 한 덩어리로 간주하고 Deque에 추가한다. 기존의 BFS를 해결할 수 있는 방법을 통해서 가장 큰 덩어리의 사이즈를 구하..