LiDARism

All Paths From Source to Target - LeetCode DFS든 BFS든 상관 없고DFS는 할 거면 end state 아닐 때 pop하는 걸 기억해야하고,BFS는 그거랑 상관없이 path의 맨 뒤 node를 기준으로 해서 queueing하는 것 정도? ##### by DFSclass Solution: def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]: n = len(graph) target = n - 1 res = [] path = [] def dfs(node): ## do smthing p..

https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/description/ DFS를 할 때 버리는 돌에 대한 합계를 수집해야한다는 것을 염두해두고 함수를 만들어야한다. class Solution: def removeStones(self, stones: List[List[int]]) -> int: n = len(stones) visited = [False] * n def dfs(idx): visited[idx] = True xi, yi = stones[idx] size = 1 for j in range(..

https://leetcode.com/problems/maximum-depth-of-binary-tree/description/ Maximize하라는 얘기가 나오면 그냥 DFS를 한다는 걸 기억해야해...! # Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: if root is None..

https://leetcode.com/problems/cheapest-flights-within-k-stops/description/ Bellman-Ford로 푸는게 가장 간단하다고 한다?class Solution: def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int: """Bellman-Ford""" INF = 10**15 dist = [INF] * n dist[src] = 0 for _ in range(k + 1): tmp = dist[:] # use snapshot fo..

https://leetcode.com/problems/invert-binary-tree/description/ DFS를 애초에 하면서 뒤집어주기만 하면 된다. # Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if root is None: ..

https://leetcode.com/problems/path-sum/ DFS를 해서 leaf에 닿고 조건이 맞으면 True를 반환하도록 하면 된다. 이외의 case들은 False 처리. # Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool: if roo..

https://leetcode.com/problems/minimum-depth-of-binary-tree/description/ 최단 거리 구하기는 BFS로 하는 것이 정석이다.# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def minDepth(self, root: Optional[TreeNode]) -> int: if root is None: retur..

https://leetcode.com/problems/alphabet-board-path/description/ 그냥... 그냥 풀면 된다.하지만 난 못풀었지 class Solution: def alphabetBoardPath(self, target: str) -> str: r = c = 0 out = [] for ch in target: tr, tc = divmod(ord(ch) - ord('a'), 5) dr, dc = tr - r, tc - c if dr 0: out.append('D' * dr) if dc > 0: o..

https://leetcode.com/problems/shortest-bridge/description/ BFS/DFS의 queue/stack 내부에 counter를 넣어서 문제를 해결할 수 있다. class Solution: def shortestBridge(self, grid: List[List[int]]) -> int: m = len(grid) n = len(grid[0]) dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)] ## directions? vis = [[False]*n for _ in range(m)] ## visited ??? queue = [] def dfs(r, c): ..

https://leetcode.com/problems/detonate-the-maximum-bombs/ adjacent를 표현하는 그래프를 먼저 그리고 그에 맞도록 DFS를 해주면 된다. 그리고 한 칸 이동 = stack pop 할 때마다 카운터 +1 하면 된다. class Solution: def maximumDetonation(self, bombs: List[List[int]]) -> int: n = len(bombs) adj = [[] for _ in range(n)] # Make Graph: i can bomb out j? for i in range(n): xi, yi, ri = bombs[i] r..