본문 바로가기
반응형

BFS11

[알고리즘] 스타트 택시 포인트 bfs 를 다룬다면 문제없이 해결할 수 있는 문제입니다. 첫번째 bfs 는 user 를 정렬하기 위한 bfs 2번째 bfs 는 각 점마다 최솟값을 구하기 위한 bfs 입니다. 🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. python from collections import deque n, m, k = map(int, input().split()) data = [list(map(int, input().split())) for _ in range(n)] sx, sy = map(int, input().split()) sx -= 1 sy -= 1 user = [list(map(int, input().split())) for _ in range(m)] dx = [0, 0, 1, -1] dy =.. 2021. 10. 4.
[알고리즘] 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.
[알고리즘] 가장 먼 노드 포인트 1. 가장 먼 노드 의미는 무엇인가? 어떻게 보면 2가지로 해석을 할 수 있다. 1. BFS를 해서 제일 마지막 거리에 있는 노드들 2. 다익스트라 알고리즘을 써서 최단 거리가 max 인 것들의 노드들 2. 따라서 2가지 방법으로 풀 수 있습니다. 🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. BFS #include #include #include #include #include using namespace std; vector map[20010]; int dist[20010]; int bfs() { memset(dist, -1, sizeof (dist)); int max_value = 0; queue q; q.push ({ 1, 0 }); dist[1] = 0; //거리를 이용하여 b.. 2021. 3. 9.
[알고리즘] 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.
반응형