Algorithm/DFS BFS (6) 썸네일형 리스트형 [BFS/DFS] 백트래킹 4가지 유형 ✅ DFS가 최적해를 찾는 4가지 유형 구현 DFS는 최적해를 찾는 문제에서 자주 활용되며,특히 백트래킹(Pruning)과 함께 사용하면 불필요한 탐색을 줄일 수 있음.아래 4가지 유형을 세부 설명과 함께 C++ 코드로 정리하겠습니다.1️⃣ N-Queens 문제 (백트래킹 활용)📌 문제 개요N×N 체스판 위에 N개의 퀸을 서로 공격하지 않도록 배치하는 방법의 수를 찾는 문제한 행에 하나의 퀸을 놓으면서 조건을 만족하는지 확인📌 최적해 찾는 방식DFS + 백트래킹을 활용퀸을 놓을 때마다 유효한 위치인지 확인(Pruning)가능한 경우만 탐색하며 최적해를 찾음📌 C++ 코드#include #include using namespace std;int N, solutions = 0;vector board; .. [BFS/DFS] 여행 경로 접근위의 문제는 모든 나열된 경우의 수를 파악해야하기 때문에 1)완전탐색이 필요하고 그래프 형태로 표시할 수 있기때문에 2)DFS로 접근한다. 또한 명확한 최적의 해가 존재하기에 3)BackTracking 기법을 사용한다. BFS와 백트래킹 알고리즘 구현시 필요 조건 1) BFS의 필요조건최종 출력값방문 여부 확인용 변수현재 노드방문 가능 조건동작방문 가능하다면 방문.종료 조건에 도달시 종료 (특정 지점에 도달 및 etc) 2) 백트래킹의 필요 조건 최종 출력값방문 여부 확인용 변수현재 노드방문 가능 조건동작 방문 가능하다면 방문.조건에 만족되지 않는 경우 되돌아오기. -> 되돌아오는 return값 유형별로 확인하기.되돌아올때, 방문 여부 확인용 변수와 최종 출력값을 되돌려줘야 한다. 구현최종 출력값 .. [BFS/DFS]네트워크 접근네트워크 = 그래프모든 서브 그래프의 수를 구하는 문제. 해결방법1) 모든 노드를 방문 할 때까지 BFS를 몇번 수행해야하는지 확인. 코드#include #include #include #include using namespace std;void BFS(vector> computers,int node, vector& is_visited){ queue q; q.push(node); while(!q.empty()) { auto cur_node = q.front(); q.pop(); is_visited[cur_node]=true; //cur_node와 연결되어있고 방문 안했으면 방문. computers[cur_node] .. [DFS/백트래킹]DFS와 백트래킹의 차이점 DFS와 백트래킹의 차이점 BFS/DFS를 공부할때, DFS는 트리의 특정 노드의 깊이 순서대로 방문하고 방문한 노드의 깊이가 최대 깊이일시 부모 노드로 올라가는 형식으로 작업된다. 이는 백트래킹 알고리즘의 조건에 만족하지 않으면 되돌아가는 성격과 유사하다고 판단되었다.하지만 둘을 동일하게 STACK을 사용하여 구현시 달랐다. 어떤부분에서 차이가 있고 같은것일까? 1. DFS개념DFS는 그래프 탐색 알고리즘으로, 한 경로를 따라 가능한 깊이까지 탐색한 후, 다른 경로를 탐색하는 방식.기본적으로 모든 경로를 탐색하며, 최단 거리나 최적해를 구하는 것이 아니라 단순히 모든 노드에 방문하는 것이 주된 목표.특징완전탐색 방법론의 하나로, 모든 가능성을 고려.최적화 없이, 모든 가능한 경우를 다 시도.주로 재귀.. [DFS/BFS] 단어 변환 * 풀이 방법 1) 우선, 설명에서 시작점과 끝점이 존재하고 시작에서 끝까지 도달한다 = 그래프 순회 생각할것.2) 이동시, 깊이나 레벨을 기준으로 이동한다면 BFS를 고려해야함3) 최적 거리를 파악해야한다 = BFS를 생각할것 * BFS 구현 방법 1) BFS 구현 필요 조건 - 방문 여부 변수 (ex) visited 변수)- 방문 방법 ( ex) 동서남북, 좌우측...)- 방문 가능 조건 ( ex) 인접행렬시, 1)- 현재 방문 표시용 인덱스 (ex) 좌표, idx) 2) 구현 - 방문 표시용 인덱스를 받는 queue 선언. - 방문 방법만큼 이동후, 방문 가능 조건 판단. - 조건 만족시, 방문 여부 변수 update & 방문 표시용 인덱스 증가. => q.empty() 될때까지 반복. - 만.. [DFS/BFS]게임 맵 최단거리 ** 알게 된 내용 1) 그래프 순회 문제를 풀때, 최단 거리를 알기 위해선 BFS로 문제를 해결해야한다. - DFS는 단순히 깊이를 우선으로 탐색하기 때문에, 모든 경로를 탐색하면서도 최단 경로를 보장 할 수 없다.BFS의 경우 탐색할떄 거리가 짧은 경로부터 차례로 탐색하기 때문에 도착점에 처음 도착한 순간이 곧 최단거리이다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요. * 제한사항 .. 이전 1 다음
