반응형 너비 우선 탐색7 [알고리즘] Max Area of Island 포인트 주어진 지도에서 섬들이 여러 개가 있다. 이 중에 제일 큰 섬의 크기를 구하라. 가 쟁점입니다. 그러면 섬의 크기는 어떻게 구할까요? 섬의 크기는 BFS 알고리즘을 이용하여 1 인 지점을 순회를 하면서 방문 배열의 표시를 해주면서 섬의 크기를 늘려가는 방식으로 구해줍니다. 어떻게 보면 너비 우선 탐색에 제일 기본형일고 할 수 있습니다. 🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. python class Solution: def bfs(self, row: int, col: int, visited: list, n: int, m: int, grid: list) -> int: q = deque() q.append([row, col]) visited[row][col] = 1 cnt = 1 dx .. 2021. 6. 1. [알고리즘] c++ cpp 양치기 꿍 포인트 1. BFS (너비 우선 탐색)을 구현하는 문제입니다 한 구역에 탐색을 BFS로 진행을 합니다. 구역 탐색을 마치고 양의 숫자와 늑대의 숫자를 비교해서 한 친구(양이나 늑대)를 0으로 만들어준 후 결과 값에 더해줍니다. 🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. #include #include #include using namespace std; int n, m; char map[255][255]; bool visited[255][255]; int dx[4] = {0,0,1,-1}; int dy[4] = {1,-1,0,0}; pair bfs(int a, int b){ queue q; q.push({a, b}); visited[a][b] = 1; int c = 0; int d = 0; .. 2020. 12. 4. [알고리즘] DFS (깊이 우선 탐색), BFS(너비 우선 탐색) 포인트 깊이 우선 탐색은 재귀를 주로 사용합니다. 저는 용어를 나누어서 사용해서 헷갈리는 부분이 많았던 것 같습니다. 깊이 우선 탐색과 너비 우선 탐색은 그렇게 다르지 않다. 사실 계속해서 알고리즘 공부를 하면서 생각이 나는 것은 사실 엄청 모르고 있는 것들이 깨어나간다라는 생각이 많이 든다. 🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. #include #include using namespace std; vector map; vector visited; int n, m; int u, v; void dfs(int x) { //기본적으로 재귀를 사용한다고 하면 생각하기 쉽다. visited[x] = true; //bfs 처럼 방문 배열 표시를 하고 cout n >> m; map.resize(n.. 2020. 12. 3. [알고리즘] c++ cpp 숨바꼭질 시리즈 (숨박꼭질4) 포인트 1. BFS (너비 우선 탐색) 2. 이번 조건은 방문했던 경로들을 기억을 할 수 있는가 이다. 🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. #include #include #include #include using namespace std; const int MAX = 100001; int parent[MAX]; //해당 지점 방문 직전 지점 저장 bool visited[MAX]; vector map; //경로 저장 int n, m; int bfs() { queue q; // 페어 큐를 만든다. q.push({n, 0}); visited[n] = 1; while (!q.empty()) { // 빌때 까지 반복 int x, time; tie(x, time) = q.front(); q... 2020. 10. 4. 이전 1 2 다음 반응형