Algorithm/BFS (71) 썸네일형 리스트형 (Python3) - LeetCode (Medium) : 1765. Map of Highest Peak https://leetcode.com/problems/map-of-highest-peakbfs로 해결한 문제였습니다.📕 풀이방법📔 입력 및 초기화다음 변수를 선언합니다.📑 행 길이 rowLength📑 열 길이 colLength📑 인접 방향을 탐색할 배열 dr, dc 및 deque dq📑 순회를 마쳤을 때 배열 정답 변수 grid, 방문여부 ck📔 풀이과정📑 water인 지점에서 얼만큼 떨어져 있는지의 거리가 높이와 같으므로 bfs로 해결가능합니다. bfs함수를 구현합니다.📑 isWater를 이차원으로 순회하며 물인 지점을 먼저 방문하며 각 행,열을 먼저 순회하기 위해 dq에 append합니다.📑 dq에 대해 순회하며 인접한 좌표를 확인하며 범위를 넘지 않으며 방문하지 않았다면 이전 거.. (Python3) - LeetCode (Medium) : 515. Find Largest Value in Each Tree Row https://leetcode.com/problems/find-largest-value-in-each-tree-rowlevel별 탐색하는 BFS 문제였습니다.📕 풀이방법📔 입력 및 초기화1. 탐색을 진해할 deque변수 dq를 선언 후 root를 넣어줍니다. 2. level별 최댓값을 반환할 max_values를 선언 후 빈 배열로 초기화해줍니다.📔 풀이과정dq에 원소가 존재하는 동안 while loop를 수행하며 다음을 진행합니다.1. 현 dq의 size를 구해줍니다. 이는 즉 자식의 node 개수를 의미합니다. 2. 각 자식들이 가지는 원소들을 비교해 최댓값을 저장할 변수 max_value를 선언해줍니다. 3. size만큼 for loop를 수행하며 자식 노드들의 원소를 비교하며 dq에서 po.. (Python3) - LeetCode (Hard) : 3203. Find Minimum Diameter After Merging Two Trees https://leetcode.com/problems/find-minimum-diameter-after-merging-two-trees트리의 지름을 구하는 문제였습니다.📕 풀이방법📔 입력 및 초기화인접리스트 graph1, graph2를 구해줍니다.📔 풀이과정* 트리의 지름은 bfs를 두 번 수행해 구할 수 있습니다.* n개의 노드에 대해 n-1개의 간선이 보장되므로 노드번호 띄엄띄엄 포함된 간선이 입력으로 들어오는 경우가 없습니다.1. 첫 번째 bfs로 끝 노드를 구한 뒤 해당 노드를 시작점으로 두 번째 bfs를 수행한다면 트리의 지름이 나옵니다. 2. 해당 부분을 bfs_diameter라는 함수를 선언해 bfs를 두 번 수행한 결과로 구한 지름 diameter를 구하고 반환합니다. 3. 트리를 .. (Python3) - LeetCode (Medium) : 2471. Minimum Number of Operations to Sort a Binary Tree by Level https://leetcode.com/problems/minimum-number-of-operations-to-sort-a-binary-tree-by-levelO(n)으로 사이클을 통한 최소 swap 개수를 구하는 BFS 문제였습니다.📕 풀이방법📔 입력 및 초기화정답 변수 totalSwap과 bfs를 위한 deque dq를 선언 후 적절히 초기화해줍니다.📔 풀이과정1. 트리의 레벨별 bfs를 순회하도록 구현해줍니다. 현재 dq의 길이를 size로 두고 size만큼 dq의 원소를 popleft하며 순회하면 구할 수 있습니다. 이를 values배열에 append해줍니다. 2. 레벨별 values를 인자로 받아 최소 사이클의 개수를 반환하는 함수 minCicle을 구현해줍니다. 해당 함수는 다음과 같이.. (Python3) - LeetCode (Medium) : 2415. Reverse Odd Levels of Binary Tree https://leetcode.com/problems/reverse-odd-levels-of-binary-treelevel별 순회하는 bfs 문제였습니다.📕 풀이방법📔 입력 및 초기화1. deque선언 후 root를 넣어줍니다. 2. level 선언 후 0으로 초기화합니다.📔 풀이과정dq에 원소가 있는 동안 while loop로 다음을 진행합니다.1. 현재 레벨에서 순회가능한 node 수는 dq의 크기입니다. 따라서 dq의 크기만큼 for loop를 수행하며 넣을 수 있는 다음 왼쪽, 오른쪽 서브 트리의 노드들을 넣어줍니다. 2. 완전 이진 트리이므로 왼쪽과 오른쪽 서브 트리에는 말단을 제외하고 항상 원소가 존재합니다. 서브트리가 존재하면 dq에 원소들을 넣어주고, 다음 레벨이 홀수라면 원소들을 뒤.. (Python3) - LeetCode (Easy) : 1971. Find if Path Exists in Graph https://leetcode.com/problems/find-if-path-exists-in-graph/BFS 문제였습니다.📕 풀이방법📔 입력 및 초기화1. 삽입삭제에 O(1)이 걸리는 deque를 사용하기 위해 변수 dq, 방문 여부 판단을 위한 check배열, 인접리스트 형태로 간선을 저장할 edges_map을 선언 후 적절히 초기화합니다. 2. 인접리스트 만들 때 양 방향 그래프인 점 유의하며 넣어줍니다.📔 풀이과정1. 시작점은 source이므로 dq에 source를 넣어주고 방문처리해줍니다. 2. dq가 비어 있는 동안 원소를 pop해 destination인지 비교하고 맞다면 도착가능하므로 True를 바로 반환합니다. 아니라면 인접리스트에 방문 가능한 다음 node를 찾아 dq에 app.. (Python3) - LeetCode (Hard) : 2290. Minimum Obstacle Removal to Reach Corner https://leetcode.com/problems/minimum-obstacle-removal-to-reach-corner/?envType=daily-question&envId=2024-11-280-1 bfs로 풀어본 문제였습니다.📕 풀이방법📔 입력 및 초기화높이 height, 너비 width, 방향 탐색을 위한 배열 dr, dc를 선언 후 적절히 초기화합니다.📔 풀이과정bfs함수를 구현합니다.1. 탐색에 우선순위를 주기 위해 push pop이 상수 시간 복잡도를 가지는 deque변수 dq를 선언 후 사용합니다. 2. 재방문하지 않기 위한 checked배열을 width * height만큼 2차원으로 선언해줍니다. 3. 시작점 0행0열 0번 벽을 부숨을 의미하는 tuple (0,0,0)을 dq에.. (C++, Python3) - 백준(BOJ) : 벽 부수고 이동하기 2 https://www.acmicpc.net/problem/14442bfs 문제였습니다.📕 풀이방법📔 입력 및 초기화1. n행 m열 부술 수 있는 벽 k를 입력받습니다. 2. 2차원 map_input에 지도를 입력받습니다.📔 풀이과정bfs함수를 수행하며 다음을 진행합니다. 1. i행 j열에 방문해 부순 벽의 개수 k개를 검사하기 위해 queue를 선언 후 행,열,부순 벽의 개수를 tuple형태로 push해줍니다.* python의 경우 일반적인 배열로 queue처럼 사용하면 pop때마다 O(n)이 소요되므로 deque를 사용해줍니다. 2. i행 j열에 k개의 벽을 부쉈을 때 최단경로 check배열을 3차원으로 선언 후 각 원소를 0으로 저장합니다. 2. 인접 4방향에 대해 loop를 수행하며 다음을.. 이전 1 2 3 4 ··· 9 다음