본문 바로가기

BFS5

[자료구조] 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.
[자료구조] 배달 파이썬 (BFS, queue, Dijkstra, heap) from math import inf from collections import defaultdict, deque from itertools import product def solution(N, roads, K): answer = [inf, 0] + [inf for i in range(N-1)] # print(answer) # why 처음이 0이 아니라 inf로 설정했을까? -> zero 인덱스 문제를 편하게 하려고 map = defaultdict(list) # 리스트 형태로 받겠다. dist_map = [[inf for _ in range(N+1)] for _ in range(N+1)] # print(dist_map) # for road in roads: a,b,dist = road map[a].ap.. 2021. 4. 23.
[프로그래머스] 네트워크 파이썬 (BFS) from collections import deque def solution(n, computers): answer = 0 bfs = deque() visited = [0]*n while 0 in visited:# visited 리스트의 모든 값에 방문 표시가 되어있을 때까지 반복 bfs.append(0) visited[0] = 1 while bfs: node = bfs.popleft() for i in range(n): if visited[i] == 0 and computers[node][i] == 1: bfs.append(i) visited[i] = 1 answer += 1# 한 네트워크의 탐색을 마치면 개수 추가 return answer 출처: cocojelly.github.io/algorithm/.. 2021. 3. 17.
[프로그래머스] 단어 변환 파이썬 (BFS/DFS) 고급 from collections import deque as queue transistable = lambda a,b: sum((1 if x!=y else 0) for x,y in zip(a,b)) == 1 def solution(begin,target,words): q, d = queue(), dict() q.append((begin, 0)) d[begin] = set(filter(lambda x:transistable(x,begin), words)) for w in words: d[w] = set(filter(lambda x:transistable(x,w), words)) while q: cur, level = q.popleft() if level > len(words): return 0 for .. 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.

티스토리툴바