flood fill2 [백준/C++] #10026 적록색약 (BFS/DFS - Flood Fill) 문제https://www.acmicpc.net/problem/10026 구상기본적 flood fill문제였다. 몇개의 섬이 있는지 판단하면 되는, 정말 간단한 문제였다. 그냥 문제 읽자마자 flood fill이라는 걸 알 수 있었다. 그리고, 아래를 보면 알 수 있다 싶이 bfs로 풀게 되면 메모리 초과가 났다. dfs로 풀어야 한정된 메모리 안에서 풀렸다. 코드 + 풀이1) 메모리초과 난 BFS 풀이BFS가 너비 우선 탐색으로 인해 많은 노드를 메모리(큐)에 저장해야 해서 노드의 연결이 많을 경우, 저장되는 노드 수가 많아져, 메모리 초과의 가능성이 있다. #include#include#include#define MAX 101#define endl "\n"using namespace std;/*1.. 2024. 7. 31. [백준/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 다음
