본문 바로가기

BFS18

[leetcode][133] Clone Graph 문제 : leetcode.com/problems/clone-graph/ 모든 노드들이 연결된 방향성 없는 그래프가 주어진다. 이를 깊은 복사한 트리를 생성한 뒤 반환하라. 트리 노드부터 탐색해가면서 노드를 붙여나가는 BFS 방식으로 풀었다. 생성된 노드들에 대한 정보를 저장하기 위한 map 을 추가했다. 해당 map의 key는 node.val이 고유하다고 명시되어 있기 때문에 이를 사용하고 map의 value는 Node*을 저장한다. 탐색 중인 노드의 neighbors 들 중 생성되지 않은 노드가 있다면 생성한 뒤 map에 저장, 탐색 중인 노드의 clone 노드에 생성한 노드를 neighbors로 등록. 이미 생성된 노드라면 map에서 해당 노드를 가져온 뒤 clone 노드의 neighbors로 등록하.. 2020. 10. 21.
[programmers][월간 코드 챌린지 시즌1] 트리 트리오 중간값 문제 : programmers.co.kr/learn/courses/30/lessons/68937 트리의 지름을 구하는 문제의 심화과정. 임의의 노드(let, v1)에서 dfs를 한 번 돌려서 가장 먼 노드(let, v2)를 구한다. (첫번째 BFS) v2 노드에서 가장 먼 노드들을 구한다. (두번째 BFS) 이 때 구한 가장 먼 노드들과 v2 노드의 거리가 트리의 지름이 된다. 만약 가장 먼 노드들이 복수 개(let, d1, d2)라면 f(v2, d1, d2)를 선택하면 이들의 중앙값은 트리의 지름이 되므로 정답은 트리의 지름이 된다. v2 노드에서 가장 먼 노드(let, v3)가 한 개라면 한 번 더 BFS를 돌려야한다. 왜냐하면 v2를 지름의 끝으로 트리의 지름을 만드는 노드들을 구했을 때는 v3 노.. 2020. 10. 18.
[programmers][찾아라 프로그래밍 마에스터] 게임 맵 최단거리 문제 : programmers.co.kr/learn/courses/30/lessons/1844 0과 1로 이루어진 게임 맵이 2차원 배열로 주어진다. 0은 벽, 1은 통로를 의미한다. 시작 위치에서 종료지점으로 가고자 할 때 최단거리를 구해라. 종료지점으로 갈 수 없다면 -1을 반환해라. 전형적인 BFS 문제. 시작 지점에서 상하좌우((-1,0), (1,0),(0,-1),(0,1))로 이동하면서 이동횟수를 저장한다. 이동한 위치가 벽(0)이라면 탐색을 종료하고 통로(1)라면 해당위치에서 상하좌우로 탐색을 계속한다. 너비우선탐색으로 탐색하며 가장 먼저 도착지 (n, m)에 도착했을 때 이동횟수가 정답이 된다. (n,m)에 도착하지 않고 탐색이 종료되었다면 -1을 반환한다. 시간복잡도는 게임맵 크기인 O(N.. 2020. 9. 13.
[leetcode] 1162. As Far from Land as Possible 문제 : https://leetcode.com/problems/as-far-from-land-as-possible/ BFS로 풀었다. 먼저 grid를 모두 돌면서 land인 부분을 찾아서 queue에 x, y를 저장한다. queue가 빌 때 까지 돌면서 distance를 갱신한다. 탐색 시 x, y 위치에 현재까지 저장된 land와의 거리 + 1로 상하좌우 cell에 갱신가능한지 보아야 한다. 이 때 distance는 가장 가까운 land와의 거리이므로 거리가 아직 세팅되지 않은 경우(아직 어떠한 land와도 거리가 갱신되지 않음)와 거리가 세팅되었다면 이미 세팅된 거리보다 가까운 경우에만 갱신된다. 거리가 갱신된 경우 다시 queue에 현재 위치를 넣어준다. queue가 비었으면 cell의 거리 갱신이.. 2019. 8. 31.
너비 우선 탐색(BFS: Breadth First Search) 그래프를 탐색하는 보편적인 방법은 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)이 있습니다. 이번 시간에는 그 중 너비 우선 탐색에 대해 알아보겠습니다. 너비 우선 탐색은 그래프를 넓게 탐색하는 방법입니다. 예를 들어 보겠습니다. 너비 우선 탐색의 알고리즘은 1. 노드와 연결된 탐색하지 않은 모든 이웃 노드를 탐색한다. 2. 방금 탐색한 노드들에 1번 과정을 실행한다. 입니다. 즉, 1번 2번을 모든 노드가 탐색될 때까지 번갈아가며 실행합니다. 이해를 돕기위해 위의 예시 그래프를 너비 우선 탐색(BFS)으로 탐색해 보겠습니다. 시작 노드는 1번으로 하겠습니다. 일단 시작 노드인 1번 노드를 탐색합니다. 그리고 1번 노드의 이웃 노드 중 탐색하지 않았던 노드들을 우선 모두 탐색합니다. 즉, 2번 3번.. 2019. 8. 28.
[leetcode][994] Rotting Oranges 문제 : https://leetcode.com/problems/rotting-oranges/ BFS로 풀었다.백준의 토마토와 비슷한 문제. 큐에 x, y, minutes를 저장한다.배열을 한 번씩 탐색하면서 썩은 오렌지인 경우 큐에 (x, y ,0)을 저장한다.그리고 오렌지(fresh + rotten)의 개수를 저장한다. 배열 탐색이 끝나면 큐가 빌때까지 오렌지 썩음을 전염시킨다.큐에서 요소를 빼낼 때 rotten 오렌지의 개수를 구한다.큐의 앞의 요소부터 탐색하면서 상하좌우 배열을 탐색한다. 만약 탐색한 grid 값이 fresh한 오렌지라면 큐에 넣는다. 이 때 minutes는 +1 해준다.큐에서 마지막으로 꺼낸 요소의 minutes가 정답이 된다.만약 총 오렌지 개수와 rotten 오렌지 개수가 같지.. 2019. 2. 17.

티스토리툴바