BFS
-
[백준] MooTube알고리즘 2021. 8. 10. 21:47
문제 https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net Approach 동영상 유사도 정보로 그래프를 만든 후 쿼리로 주어진 동영상을 시작점으로 하여 BFS를 돌려 각 동영상들의 유사도를 측정 이전 정보와 비교하여 더 낮은 유사도로 유사도(dist) 배열 업데이트 이 후 유사도 배열을 탐색해 K보다 유사도가 높은 것만 탐색 Code https://github.com/chi3236/algorith..
-
[LeetCode] Jump Game2알고리즘 2020. 8. 30. 20:32
문제 Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps. Example: Input: [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, the..
-
[LeetCode] Surrounded Regions알고리즘 2019. 12. 7. 04:12
문제 Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region. Example: X X X X X O O X X X O X X O X X After running your function, the board should be: X X X X X X X X X X X X X O X X Explanation: Surrounded regions shouldn’t be on the border, which means that any 'O' on the border..
-
[LeetCode] Word Ladder알고리즘 2019. 12. 6. 02:40
문제 Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that: Only one letter can be changed at a time. Each transformed word must exist in the word list. Note that beginWord is not a transformed word. Note: Return 0 if there is no such transformation sequence. All words have the same length. Al..
-
[LeetCode] Binary Tree Maximum Path Sum알고리즘 2019. 12. 5. 01:53
문제 Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root. Example 1: Input: [1,2,3] 1 / \ 2 3 Output: 6 Example 2: Input: [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 ..
-
[LeetCode] Populating Next Right Pointers in Each Node알고리즘 2019. 12. 4. 16:35
문제 You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:struct Node { int val; Node *left; Node *right; Node *next; } Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL...
-
[LeetCode] Maximum Depth of Binary Tree알고리즘 2019. 12. 3. 01:54
문제 Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Note: A leaf is a node with no children. Example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its depth = 3. Approach DFS를 활용한 inorder traversal로 depth를 측정하거나 BFS를 활용한 level order traversal로 depth를 측정하면 된다. Co..
-
[LeetCode] Binary Tree Zigzag Level Order Traversal알고리즘 2019. 12. 2. 22:38
문제 Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its zigzag level order traversal as: [ [3], [20,9], [15,7] ] Approach Level Order Traversal인데 기존과 다른 점은 지그재그인것 기존 구현과 비슷한데 차이점은 왼쪽으로 읽을 때는 vec..