BFS3 [백준/C++] #1525 퍼즐 (BFS) 문제https://www.acmicpc.net/problem/1525 구상빈칸을 움직여서 배열의 상태가 원하는 상태로 나오게끔 하는데, 이때의 최소 이동 횟수를 구하는 문제였다. 최소 이동 횟수를 구하는 것이다 보니 bfs를 이용하는 문제라는 건 인지했지만, 원하는 상태로 바꾸는 데에 있어서 빈칸을 언제까지 움직여볼 것인가에 대한 고민이 들었다. 단순하게 방문했는지의 여부를 판단하기에는 빈칸을 움직이는 순서에 따라서 상황이 다양하게 바뀔 수 있었다. 그래서 그 이전에 해당 상황에 도달한 적이 없다면, 큐에 넣는 방식을 택했다. *map의 find(key) 결과값이 map.end()값과 같다면, 원소가 없다는 뜻이다. *만일 원소가 있다면, map::iterator 를 반환하고, iterator는 -> 연.. 2024. 9. 1. [백준/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++] #16933 벽 부수고 이동하기 2, 3 (BFS) 문제https://www.acmicpc.net/problem/16933 구상백준 14442번 벽 부수고 이동하기 문제에다가 낮/밤 조건이 추가된 문제였다. 이런 문제는 깊이 우선 탐색(DFS)로 풀기가 어렵다. 이유는 다음과 같다. 최단 경로 보장: DFS는 특정 경로를 완전히 탐색한 후에야 다른 경로를 탐색하기 때문에, 탐색 초기에 찾은 경로가 반드시 최단 경로라고 보장할 수 없다. 반면 BFS(Breadth-First Search)는 모든 경로를 동시에 탐색하며, 처음으로 목표에 도달하는 경로가 최단 경로임을 보장한다.낮과 밤의 전환: 이 문제에서는 낮과 밤이 번갈아가면서 바뀌는 조건이 있다. BFS는 단계별로 탐색하기 때문에 이 조건을 자연스럽게 처리할 수 있는데, DFS에서는 상태를 추적하며 .. 2024. 7. 31. 이전 1 다음
