메모/알고리즘
[백준] Python - 음식물 피하기
Floodnut
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를 해결할 수 있는 방법을 통해서 가장 큰 덩어리의 사이즈를 구하여 해결하였다.
GitHub - Floodnut/algorithm: 알고리즘 풀이 모음
알고리즘 풀이 모음. Contribute to Floodnut/algorithm development by creating an account on GitHub.
github.com