본문 바로가기

dfs5

[자료구조] FloodFill 파이썬 (BFS, queue) BFS from collections import deque def solution(n, m, image): cnt = 0 visited = [[False] * m for _ in range(n)] # visited table (col(m) x row(n)) dir = [[1,0], [0,1], [-1,0], [0,-1]] # 4-direction for i in range(n): for j in range(m): if not visited[i][j]: q = deque() # BFS-queue q.append([i,j]) visited[i][j] = True color = image[i][j] while q: x, y = q.popleft() for dx, dy in dir: xx, yy = x+dx,.. 2021. 4. 23.
[LeetCode] Binary Tree Paths 파이썬 (Binary Tree, LCA, DFS) class Solution(object): # @param {TreeNode} root # @return {string[]} def binaryTreePaths(self, root): result, path = [], [] self.binaryTreePathsRecu(root, path, result) return result def binaryTreePathsRecu(self, node, path, result): if node is None: return if node.left is node.right is None: ans = "" for n in path: ans += str(n.val) + "->" result.append(ans + str(node.val)) if node.left: path... 2021. 4. 7.
[LeetCode] Same Tree 파이썬 (TreeNode, recursion) class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: # @param p, a tree node # @param q, a tree node # @return a boolean def isSameTree(self, p, q): if p is None and q is None: return True if p is not None and q is not None: return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) return False 출처: github.com.. 2021. 3. 31.
[프로그래머스] 여행경로 파이썬(DFS) from collections import defaultdict def solution(tickets): # 특정 티켓의 인접 리스트를 구하는 함수 def init_graph(): routes = defaultdict(list) for key, value in tickets: routes[key].append(value) return routes # 스택을 사용한 DFS def dfs(): stack = ["ICN"] path = [] # 가려고하는 경로를 저장하는 변수 while len(stack) > 0: # stack이 비어있을 때까지 top = stack[-1] # 특정 공항에서 출발하는 표가 없다면 또는 있지만 티켓을 다 써버린 경우 if top not in routes or len(routes.. 2021. 3. 17.
[프로그래머스] 타겟 넘버 (BFS/DFS) 파이썬 다른 사람의 풀이 from collections import deque def solution(numbers, target): answer = 0 queue = deque([(0, 0)]) # sum, level while queue: s, l = queue.popleft() if l > len(numbers): break elif l == len(numbers) and s == target: answer += 1 queue.append((s+numbers[l-1], l+1)) queue.append((s-numbers[l-1], l+1)) return answer sum, level이라는 2개의 tuple를 queue를 활용해서 만든풀이 queue에 들어가는 tuple를 append하는 코드를 보면, .. 2021. 3. 15.

티스토리툴바