알고리즘43 [백준/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. [백준/C++] #2146 다리 만들기 (Flood Fill / BFS) 문제https://www.acmicpc.net/problem/2146 알고리즘: BFS 이용한 Flood Fill 알고리즘은 쉬웠는데, 조건 때문에 조금 헤매어서 시간이 걸렸다.ㅠbfs를 섬에 번호 매길때 한번, 섬들 간 최단 거리 구할 때 한번 사용했다. 다음에는 dfs로도 풀어봐야겠다. 그리고 fill, memset 초기화 함수에 대해서도 잘 알아두자!! 코드 + 풀이1. 섬 찾아 섬을 이루는 땅들에 동일한 번호 붙이기 -> findLand() 2. 섬들간의 최단 거리 구하기 -> bfs()#include #include #include #include #define MAX 101#define INF 987654321// 2146/*섬과 섬을 잇는 짧은 다리 지도가 주어질 때, "가장 짧은 다리 .. 2024. 7. 2. [백준/C++] #1168 요세푸스 문제 2 (Segment Tree) 문제https://www.acmicpc.net/problem/1158: 큐를 이용여 풀리는 가장 기본적인 요세푸스 문제 https://www.acmicpc.net/problem/1168: 세그먼트 트리를 이용하여 시간복잡도를 줄여야 하는 요세푸스 문제개념: Segment Tree 코드 + 풀이1. 큐를 이용한 풀이 (1158번): 특정 "번째"의 사람이 올 때까지 큐의 원소를 push, pop 반복한다. #include#includeusing namespace std;int n, k;queueq;int main(void){ int i; cin >> n >> k; for (i = 1; i "; return 0;} 2. 세그먼트 트리 이용한 풀이 (1168번): 요세푸스 문제의 핵심은 몇 번째에 있는 사람을.. 2024. 7. 1. 이전 1 ··· 8 9 10 11 다음
